Křížení číselné nerovnosti

Průsečíková číselná nerovnost neboli průnikové lemma udává infimum minimálního počtu průsečíků daného grafu jako funkce počtu hran a vrcholů grafu. Lema říká, že pro grafy, kde je počet hran e dostatečně velký ve srovnání s počtem vrcholů n , je počet průsečíků alespoň úměrný e 3 / n 2 .

Nerovnice má aplikace ve vývoji VLSI a v kombinatorické geometrii . Nerovnost objevili Aitai, Chvatal, Newborn a Semeredi [1] a nezávisle také Layton [2] .

Výpis a historie

Průsečík číselná nerovnost říká, že pro neorientovaný jednoduchý graf G s n vrcholy a e hranami tak, že e > 7 n , číslo průsečíku v cr( G ) vyhovuje nerovnosti.

Konstanta 29 je zatím nejlepší a je způsobena Ackermanem [3] . Dřívější výsledky se slabšími konstantami viz práce Pacha a Totha [4] , Pacha Radojiče, Tardose a Totha [5] .

Konstantu 7 lze snížit na 4 , ale za cenu toho je konstanta 29 nahrazena horší konstantou 64 .

Aplikace

Důvod, který přiměl Laytona ke studiu počtu křižovatek, byl v aplikacích na vývoj VLSI [2] .

Později si Szekei uvědomil, že tato nerovnost poskytuje velmi jednoduchý důkaz některých důležitých teorémů v geometrii dopadu . Například Szemeredi–Trotterova věta , horní hranice počtu možných výskytů mezi daným počtem bodů a čar v rovině, vyplývá z konstrukce grafu, jehož vrcholy jsou dané body a jehož hrany jsou úsečky spojující body. Pokud by došlo k více incidentům, než připouští Szemeredi–Trotterova věta, měl by tento graf více průsečíků, než je celkový počet dvojic čar, což je nemožné. Nerovnici lze také použít k prokázání Beckova teorému , který říká, že pokud konečná množina bodů nemá lineární počet kolineárních bodů, pak tato množina určuje kvadratický počet zřetelných čar [6] . Podobně Tamal Day použil nerovnost k prokázání horních odhadů pro geometrické k - množiny [7] .

Důkaz

Nejprve uvedeme předběžný odhad — pro každý graf G s n vrcholy a e hranami máme

Abychom to dokázali, představte si nakreslení grafu G , který má přesně průsečíky cr( G ) . Každý z těchto průsečíků lze odstranit odstraněním hrany z G . Pak můžeme najít graf s alespoň e − cr( G ) hranami a n vrcholy, který nemá žádné průsečíky, a proto je tento graf rovinný . Ale z Eulerova vzorce pak musíme mít e − cr( G ) ≤ 3 n , odkud plyne požadovaný výrok. (Ve skutečnosti máme e − cr( G ) ≤ 3 n − 6 pro n ≥ 3 ).

K získání skutečné nerovnosti čísel průsečíku nyní používáme pravděpodobnostní uvažování . Nechť 0 < p < 1 je pravděpodobnostní parametr, který později zvolíme. Sestrojme náhodný podgraf H podgrafu G , ve kterém každý vrchol grafu G spadá do H nezávisle s pravděpodobností p a hrana grafu G spadá do grafu H právě tehdy, když do grafu padnou dva vrcholy. H . Nechť eH , n H a cr H označují počet hran, vrcholů a počet průsečíků v grafu H. Protože H je podgrafem G , výkres G obsahuje výkres H. Podle předběžné průnikové nerovnosti máme

Uvažujme matematická očekávání těchto veličin, která získáme

Protože každý z n vrcholů grafu G spadá s pravděpodobností p do grafu H , máme E [ n H ] = pn . Podobně každá z hran G má pravděpodobnost p 2 být v H , protože oba konce grafu musí být v H . Tedy E [ eH ] = p2e . _ _ Konečně, každý průsečík ve výkresu grafu G má pravděpodobnost p 4, že je v grafu H , protože každý průsečík vyžaduje čtyři vrcholy. Abychom to ukázali, představte si nakreslení grafu G s průsečíky cr( G ) . Můžeme předpokládat, že jakékoli dvě hrany na tomto výkresu se společným vrcholem se neprotínají, jinak tvoří něco blízkého písmenu alfa (viz obrázek) a můžeme prohodit části oblouků až k průsečíku a snížit počet průsečíků . Pak má jakýkoli průsečík v kresbě grafu čtyři různé vrcholy grafu G . Tedy E [cr H ] = p 4 cr( G ) a dostáváme

Nyní, když položíme p = 4 n / e < 1 (předpokládali jsme, že e > 4 n ), po některých algebraických výpočtech dostaneme

Mírné zlepšení tohoto přístupu nám umožňuje nahradit 64 33,75 pro e > 7,5 n [3] .

Variace

U grafů s obvodem větším než 2 r a počtem hran e ≥ 4 n zlepšili Pach, Spencer a Toth tuto nerovnost na [8] .

Poznámky

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

Literatura