A számegyenlőtlenség átlépése

A metszéspontszám-egyenlőtlenség, vagy metszéslemmája egy adott gráf metszéspontjainak minimális számára ad infimumot a gráf éleinek és csúcsainak számának függvényében. A lemma kimondja, hogy azoknál a gráfoknál, ahol az e élek száma elég nagy az n csúcsok számához képest, a metszéspontok száma legalább arányos e 3 / n 2 -vel .

Az egyenlőtlenség alkalmazható a VLSI fejlesztésében és a kombinatorikus geometriában . Az egyenlőtlenséget Aitai, Chvatal, Newborn és Semeredi [1] és egymástól függetlenül Layton [2] fedezte fel .

Nyilatkozat és előzmények

A metszésszám-egyenlőtlenség azt mondja ki, hogy egy irányítatlan egyszerű G gráfnál , amelynek n csúcsa és e éle van, és ahol e > 7 n , a cr( G ) metszéspontszáma kielégíti az egyenlőtlenséget .

A 29 -es konstans az eddigi legjobb, és Ackermannek köszönhető [3] . A gyengébb állandókkal rendelkező korábbi eredményeket lásd Pach és Toth [4] , Pach Radojic, Tardos és Toth [5] cikkében .

A 7 -es konstans lecsökkenthető 4 -re , de ennek az árán a 29 -es konstans helyébe a rosszabb 64 -es állandó kerül .

Alkalmazások

Az ok, ami miatt Layton a kereszteződések számának tanulmányozására késztette, a VLSI fejlesztésére vonatkozó alkalmazásokban keresendő [2] .

Később Szekei rájött, hogy ez az egyenlőtlenség nagyon egyszerű bizonyítékot ad néhány fontos beesési geometriai tételre . Például a Szemedi–Trotter tétel , amely egy síkban adott számú pont és egyenes között lehetséges beesések számának felső korlátja , egy olyan gráf felépítéséből következik, amelynek csúcsai adott pontok, élei pedig a gráfot összekötő szakaszok. pontokat. Ha több incidens lenne, mint amennyit a Szemedi–Trotter tétel megenged, akkor ennek a gráfnak több metszéspontja lenne, mint az egyenespárok teljes száma, ami lehetetlen. Az egyenlőtlenség felhasználható Beck tételének bizonyítására is , amely szerint ha egy véges ponthalmaznak nincs lineáris számú kollineáris pontja, akkor ez a halmaz határozza meg a különböző egyenesek másodfokú számát [6] . Ehhez hasonlóan Tamal Day az egyenlőtlenséget használta a geometriai k - halmazok felső határának bizonyítására [7] .

Bizonyítás

Először is adunk egy előzetes becslést – bármely n csúcsú és e élű G gráfra van

Ennek bizonyítására képzeljünk el egy G gráf rajzát, amelynek pontosan cr( G ) metszéspontjai vannak. Ezen metszéspontok mindegyike eltávolítható, ha eltávolítunk egy élt G -ből . Ekkor találhatunk egy legalább e − cr( G ) élű és n csúcsú gráfot, amelynek nincs metszéspontja, ezért ez a gráf sík . De az Euler-képletből e − cr( G ) ≤ 3 n kell, hogy legyen , ahonnan a szükséges állítás következik. (Valójában e − cr( G ) ≤ 3 n − 6 n ≥ 3 esetén ) .

A tényleges metszéspontszám-egyenlőtlenség meghatározásához most valószínűségi okoskodást használunk . Legyen 0 < p < 1 valószínűségi paraméter, amelyet később választunk . Szerkesszük meg a G részgráf egy véletlenszerű H részgráfját , amelyben a G gráf minden csúcsa egymástól függetlenül, p valószínűséggel esik H -ba , és a G gráf éle akkor és csak akkor esik a H gráfba , ha két csúcs esik a gráfba. H . Jelölje e H , n H és cr H a H gráf éleinek, csúcsainak és metszéspontjainak számát . Mivel H G részgráfja, G rajza tartalmazza H rajzát . Az előzetes kereszteződési egyenlőtlenség szerint megvan

Tekintsük ezeknek a mennyiségeknek a matematikai elvárásait , megkapjuk

Mivel a G gráf n csúcsa p valószínűséggel esik a H gráfba , így E [ n H ] = pn . Hasonlóképpen, G minden élének p 2 a valószínűsége , hogy H -ban van, mivel a gráf mindkét végének H -ban kell lennie . Így E [ e H ] = p 2 e . Végül a G gráf rajzában minden metszéspontnak p 4 a valószínűsége , hogy a H gráfban van , mivel minden metszésponthoz négy csúcsra van szükség. Ennek bemutatásához képzeljünk el egy G gráf rajzát cr( G ) metszéspontokkal . Feltételezhetjük, hogy ezen a rajzon bármelyik két közös csúcsú él nem metszi egymást, ellenkező esetben az alfa betűhöz közeli valamit alkotnak (lásd az ábrát), és az ívek részeit felcserélhetjük a metszéspontig, és csökkenthetjük a metszéspontok számát. . Ekkor egy gráf rajzában bármely metszéspontnak a G gráf négy különböző csúcsa van . Így E [cr H ] = p 4 cr( G ) és azt kapjuk

Ha most p = 4 n / e < 1 -et teszünk fel (feljebb azt feltételeztük, hogy e > 4 n ), néhány algebrai számítás után azt kapjuk, hogy

Ennek a megközelítésnek egy kis javítása lehetővé teszi, hogy a 64 -et 33,75 - re cseréljük e > 7,5 n esetén [3] .

Változatok

Azoknál a gráfoknál, amelyek kerülete nagyobb, mint 2 r , és az élek száma e ≥ 4 n , Pach, Spencer és Toth ezt az egyenlőtlenséget [8] -ra javította .

Jegyzetek

  1. ↑ Ajtai, Chvátal, Újszülött, Szemerédi, 1982 , p. 9–12.
  2. ↑ 12 Leighton , 1983 .
  3. ↑ 12 Ackerman , 2013 .
  4. ↑ Pach, Tóth, 1997 , p. 427–439.
  5. ↑ Pach, Radoičić, Tardos, Tóth, 2006 , p. 527–552.
  6. ↑ Székely, 1997 , p. 353–358.
  7. ↑ Dey, 1998 , p. 373–382.
  8. ↑ Pach, Spencer, Tóth, 2000 , p. 623–644.

Irodalom