Szemerédi – Trotterova věta - Szemerédi–Trotter theorem

The Szemerédi – Trotterova věta je matematický mít za následek v oboru kombinatorická geometrie. Tvrdí, že vzhledem k tomu n body a m řádky v Euklidovské letadlo, počet výskyty (tj., počet dvojic bod-čára, takže bod leží na přímce) je

${ displaystyle O left (n ^ { frac {2} {3}} m ^ { frac {2} {3}} + n + m right),}$

tuto vazbu nelze vylepšit, s výjimkou implicitních konstant. Pokud jde o implicitní konstanty, ukázalo se to János Pach, Radoš Radoičić, Gábor Tardos a Géza Tóth^[1] že horní hranice ${ displaystyle 2.5n ^ {2/3} m ^ {2/3} + n + m}$ drží. (Od té doby jsou lepší konstanty známé díky lepšímu překročení konstant lemmatu; aktuální nejlepší je 2,44.) Na druhou stranu Pach a Tóth ukázali, že tvrzení neplatí, pokud nahradíme koeficient 2,5 0,42.^[2]

Ekvivalentní formulace věty je následující. Dáno n body a celé číslo k ≥ 2, počet řádků, které projdou alespoň k bodů je

${ displaystyle O left ({ frac {n ^ {2}} {k ^ {3}}} + { frac {n} {k}} right).}$

Původní doklad o Endre Szemerédi a William T. Trotter bylo poněkud komplikované pomocí kombinatorické techniky známé jako buněčný rozklad.^[3][4] Později László Székely objevil mnohem jednodušší důkaz pomocí nerovnost křížení čísel pro grafy.^[5] (Viz. níže.)

Věta Szemerédi – Trotter má řadu důsledků, včetně Beckova věta v geometrie dopadu.

Důkaz první formulace

Můžeme zahodit řádky, které obsahují dva nebo méně bodů, protože mohou přispět maximálně 2m dopady na celkový počet. Můžeme tedy předpokládat, že každý řádek obsahuje alespoň tři body.

Pokud řádek obsahuje k body, pak to bude obsahovat k − 1 úsečky, které spojují dva po sobě jdoucí body podél čáry. Protože k ≥ 3 po vyřazení dvoubodových čar z toho vyplývá k − 1 ≥ k/2, takže počet těchto úseček na každé linii je alespoň poloviční než počet výskytů na této linii. Sečtením všech řádků je počet těchto úseček opět alespoň polovina z celkového počtu výskytů. Tedy pokud E označuje počet takových úseček, postačí to ukázat

${ displaystyle e = O left (n ^ { frac {2} {3}} m ^ { frac {2} {3}} + n + m right).}$

Nyní zvažte graf vytvořen pomocí n body jako vrcholy a E úsečky jako hrany. Protože každý úsečka leží na jednom z m čáry a jakékoli dvě čáry se protínají maximálně v jednom bodě, číslo křížení tohoto grafu je maximálně počet bodů, kde se protínají dvě čáry, což je maximálně m(m − 1)/2. The nerovnost křížení čísel to znamená E ≤ 7.5nnebo tak m(m − 1)/2 ≥ E³ / 33.75n². V obou případech E ≤ 3.24(nm)^2/3 + 7.5n, což dává požadovanou vazbu

${ displaystyle e = O left (n ^ { frac {2} {3}} m ^ { frac {2} {3}} + n + m right).}$

Důkaz druhé formulace

Protože každý pár bodů lze spojit nejvýše jednou linií, může jich být maximálně n(n − 1)/2 linky, které se mohou připojit na k nebo více bodů, protože k ≥ 2. Tato vazba prokáže teorém, když k je malý (např k ≤ C pro nějakou absolutní konstantu C). Musíme tedy zvážit pouze případ, kdy k je velký, řekněme k ≥ C.

Předpokládejme, že existují m řádky, které každý obsahuje alespoň k bodů. Tyto řádky generují alespoň mk výskyty, a tak máme první formulaci Szemerédi – Trotterovy věty

${ displaystyle mk = O left (n ^ { frac {2} {3}} m ^ { frac {2} {3}} + n + m right),}$

a tak alespoň jedno z tvrzení ${ displaystyle mk = O (n ^ {2/3} m ^ {2/3}), mk = O (n)}$nebo ${ displaystyle mk = O (m)}$ je pravda. Třetí možnost je od té doby vyloučena k Předpokládalo se, že je velký, takže nám zůstávají první dva. Ale v kterémkoli z těchto dvou případů dá určitá elementární algebra vazbu ${ displaystyle m = O (n ^ {2} / k ^ {3} + n / k)}$ podle přání.

Optimalita

S výjimkou konstanty nelze vázanou incidenci Szemerédi – Trotter zlepšit. Chcete-li to vidět, zvažte jakékoli kladné celé číslo N ∈ Z⁺ množina bodů na celé číslo mříž

${ displaystyle P = left {(a, b) in mathbf {Z} ^ {2} : 1 leq a leq N; 1 leq b leq 2N ^ {2} right },}$

a sada řádků

${ displaystyle L = left {(x, mx + b) : m, b in mathbf {Z}; 1 leq m leq N; 1 leq b leq N ^ {2} že jo}.}$

Jasně, ${ displaystyle | P | = 2N ^ {3}}$ a ${ displaystyle | L | = N ^ {3}}$. Protože každý řádek je incidentem N body (tj. jednou za každý ${ displaystyle x in {1, cdots, N }}$), počet výskytů je ${ displaystyle N ^ {4}}$ který odpovídá horní hranici.^[6]

Zobecnění na R^d

Jedno zobecnění tohoto výsledku do libovolné dimenze, R^d, byl nalezen Agarwalem a Aronovem.^[7] Vzhledem k souboru n body, Sa soubor m hyperplanes, H, z nichž každý je překlenut S, počet výskytů mezi S a H je ohraničen výše

${ displaystyle O left (m ^ { frac {2} {3}} n ^ { frac {d} {3}} + n ^ {d-1} right).}$

Ekvivalentně, počet hyperplánů v H obsahující k nebo více bodů je ohraničeno výše

${ displaystyle O left ({ frac {n ^ {d}} {k ^ {3}}} + { frac {n ^ {d-1}} {k}} right).}$

Konstrukce díky Edelsbrunneru ukazuje, že tato vazba je asymptoticky optimální.^[8]

József Solymosi a Terence Tao získáno v blízkosti ostrých horních mezí pro počet výskytů mezi body a algebraickými odrůdami ve vyšších dimenzích, když body a odrůdy splňují „určité axiomy pseudořádkového typu“. Jejich důkaz používá Polynomiální šunková sendvičová věta.^[9]

Analogy přes jiná pole

Existoval určitý zájem o prokázání analogií k Szemerédiho-Trotterově teorému v rovinách nad jinými poli než R. Všechny známé důkazy Szemerédiho-Trotterovy věty skončily R spoléhejte se rozhodujícím způsobem na topologii euklidovského prostoru, takže se nerozšiřujte snadno na další pole. Přesto byly získány následující výsledky:

• Tóth úspěšně zobecnil původní důkaz Szemerédiho a Trottera na složitou rovinu C² zavedením dalších nápadů.^[10] Tento výsledek také získal nezávisle a jinou metodou Zahl.^[11]

Reference