Krydsende antal ulighed

Skæringsnummeruligheden eller skæringslemmaet giver et infimum på minimumsantallet af skæringspunkter for en given graf som funktion af antallet af kanter og toppunkter i grafen. Lemmaet siger, at for grafer, hvor antallet af kanter e er stort nok i forhold til antallet af toppunkter n , er antallet af skæringspunkter mindst proportionalt med e 3 / n 2 .

Uligheden har anvendelser i udviklingen af ​​VLSI og i kombinatorisk geometri . Uligheden blev opdaget af Aitai, Chvatal, Newborn og Semeredi [1] og uafhængigt af Layton [2] .

Erklæring og historie

Skæringsnummeruligheden angiver, at for en urettet simpel graf G med n toppunkter og e kanter således, at e > 7 n , opfylder skæringstallet i cr( G ) uligheden

Den konstante 29 er den bedste hidtil og skyldes Ackerman [3] . For tidligere resultater med svagere konstanter, se artiklerne af Pach og Toth [4] , Pach Radojic, Tardos og Toth [5] .

Konstanten 7 kan sænkes til 4 , men på bekostning af at gøre det erstattes konstanten 29 med den dårligere konstant 64 .

Ansøgninger

Årsagen til, at Layton fik Layton til at studere antallet af kryds, var i applikationer til udviklingen af ​​VLSI [2] .

Senere indså Szekei, at denne ulighed giver et meget simpelt bevis på nogle vigtige teoremer i incidensgeometri . For eksempel følger Szemeredi-Trotter-sætningen , den øvre grænse for antallet af mulige forekomster mellem et givet antal punkter og linjer i et plan, fra konstruktionen af ​​en graf, hvis toppunkter er givet punkter, og hvis kanter er linjestykker, der forbinder point. Hvis der var flere hændelser end Szemeredi-Trotter-sætningen tillader, ville denne graf have flere skæringspunkter end det samlede antal linjepar, hvilket er umuligt. Uligheden kan også bruges til at bevise Becks sætning om, at hvis et endeligt sæt punkter ikke har et lineært antal kollineære punkter, så bestemmer dette sæt det kvadratiske antal af distinkte linjer [6] . På samme måde brugte Tamal Day uligheden til at bevise øvre grænser for geometriske k - sæt [7] .

Bevis

Først giver vi et foreløbigt skøn - for enhver graf G med n toppunkter og e kanter har vi

For at bevise dette, forestil dig en tegning af en graf G , der har præcis cr( G ) skæringspunkter. Hvert af disse skæringspunkter kan fjernes ved at fjerne en kant fra G . Så kan vi finde en graf med mindst e − cr( G ) kanter og n toppunkter, der ikke har nogen skæringspunkter, og derfor er denne graf plan . Men ud fra Eulers formel skal vi så have e − cr( G ) ≤ 3 n , hvorfra den påkrævede sætning følger. (Faktisk har vi e − cr( G ) ≤ 3 n − 6 for n ≥ 3 ).

For at opnå den faktiske skæringsnummerulighed bruger vi nu probabilistisk ræsonnement . Lad 0 < p < 1 være en sandsynlighedsparameter , som vi vælger senere. Lad os konstruere en tilfældig undergraf H af undergrafen G , hvor hvert hjørne af grafen G falder ind i H uafhængigt med sandsynlighed p , og kanten af ​​grafen G falder ind i grafen H , hvis og kun hvis to spidser falder ind i grafen H . Lad eH , n H og cr H angive antallet af henholdsvis kanter, toppunkter og antallet af skæringspunkter i grafen H . Da H er en undergraf af G , indeholder tegningen af ​​G tegningen af ​​H. Ifølge den foreløbige krydsulighed har vi

Overvej de matematiske forventninger til disse størrelser, vi opnår

Da hver af de n toppunkter i grafen G falder med sandsynlighed p ind i grafen H , har vi E [ n H ] = pn . På samme måde har hver af kanterne på G en sandsynlighed p 2 for at være i H , da begge ender af grafen skal være i H . Således er E [ eH ] = p2e . _ Endelig har hvert skæringspunkt i tegningen af ​​graf G en sandsynlighed p 4 for at være i graf H , da hvert skæringspunkt kræver fire hjørner. For at vise dette skal du forestille dig en tegning af en graf G med cr( G ) skæringspunkter. Vi kan antage, at alle to kanter i denne tegning med et fælles toppunkt ikke skærer hinanden, ellers danner de noget tæt på bogstavet alfa (se figur), og vi kan bytte dele af buerne op til skæringspunktet og reducere antallet af skæringspunkter . Så har ethvert skæringspunkt i graftegningen fire forskellige hjørner af grafen G . Således E [cr H ] = p 4 cr( G ), og vi får

Nu, hvis vi sætter p = 4 n / e < 1 (vi antog ovenfor, at e > 4 n ), efter nogle algebraiske beregninger, får vi

En lille forbedring af denne tilgang giver os mulighed for at erstatte 64 med 33,75 for e > 7,5 n [3] .

Variationer

For grafer med omkreds større end 2 r og antal kanter e ≥ 4 n har Pach, Spencer og Toth forbedret denne ulighed til [8] .

Noter

  1. ↑ Ajtai, Chvátal, Newborn, Szemerédi, 1982 , s. 9-12.
  2. ↑ 12 Leighton , 1983 .
  3. ↑ 12 Ackerman , 2013 .
  4. ↑ Pach, Toth, 1997 , s. 427-439.
  5. ↑ Pach, Radoičić, Tardos, Tóth, 2006 , s. 527-552.
  6. ↑ Szekely, 1997 , s. 353-358.
  7. ↑ Dey, 1998 , s. 373-382.
  8. ↑ Pach, Spencer, Tóth, 2000 , s. 623-644.

Litteratur