Szemeredi-Trotterova věta

Szemeredi-Trotterova věta je výsledkem kombinatorické geometrie . Věta říká, že daných n bodů a m čar v rovině je počet výskytů (tj. počet dvojic bod/přímka, kde bod leží na přímce)

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

a tuto hranici nelze zlepšit.

Ekvivalentní formulace věty je následující. Je-li dáno n bodů a celé číslo k > 2 , je počet čar procházejících alespoň k bodů

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

Původní důkaz Szemerediho a Trottera [1] byl složitý a používal kombinatorickou techniku známou jako buněčné dělení . Později Szekei objevil mnohem jednodušší důkaz pomocí průnikové číselné nerovnosti pro grafy [2] (viz níže).

Szemeredi-Trotterova věta má několik důsledků, včetně Beckovy [ věty v geometrii dopadu .

Důkaz prvního tvrzení

Můžeme vyřadit čáry obsahující dva nebo méně bodů, protože mohou poskytovat maximálně 2 m dopadů. Můžeme tedy předpokládat, že jakákoli úsečka obsahuje alespoň tři body.

Pokud úsečka obsahuje k bodů, pak obsahuje k − 1 úseček spojujících dva z n bodů. Konkrétně bude čára obsahovat alespoň k /2 takových segmentů, protože jsme předpokládali k ≥ 3 . Sečtením všech takových výskytů podél všech m čar zjistíme, že počet takto získaných segmentů se rovná alespoň polovině počtu všech výskytů. Označíme-li e počet takových segmentů, stačí to ukázat

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

Uvažujme nyní graf tvořený n body jako vrcholy a e segmenty jako hranami. Protože každý segment leží na jedné z m přímek a dvě přímky se protínají nejvýše v jednom bodě, počet průsečíků tohoto grafu nepřesahuje m 2 . Z průsečíkové číselné nerovnosti usuzujeme, že buď e ≤ 7,5 n nebo m 2 ≥ e 3 / 33,75 n 2 . V každém případě e ≤ 3,24( nm ) 2/3 + 7,5 n a dostaneme požadovanou vazbu

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

Důkaz druhé formulace

Protože jakýkoli pár bodů může být spojen nejvýše jednou přímkou, může být nejvýše n ( n − 1)/2 l čar, které mohou spojit k nebo více bodů, protože k ≥ 2 . Tato vazba dokazuje větu pro malé k (například pokud k ≤ C pro nějakou absolutní konstantu C ). Proto má smysl uvažovat pouze případy, kdy k je velké, řekněme k ≥ C.

Předpokládejme, že existuje m čar, z nichž každá obsahuje alespoň k bodů. Tyto čáry tvoří nejméně mk incidenci a pak první variantou Szemerédy-Ttrotterovy věty máme

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

a alespoň jedna rovnost z nebo je splněna . Třetí možnost jsme zavrhli, protože jsme předpokládali, že k je velké, takže první dvě zůstávají. Ale v obou případech po jednoduchých algebraických výpočtech dostaneme , což je vyžadováno. $mk=O(n^{2/3}m^{2/3}),mk=O(n)$ $mk=O(m)$ $m=O(n^{2}/k^{3}+n/k)$

Optimality

Pokud se neberou v úvahu konstantní faktory, nelze Szemeredy-Trotterovu incidenční hranici zlepšit. Abyste to viděli, uvažujte pro jakékoli kladné celé číslo N ∈ Z + množinu bodů celočíselné mřížky

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

a sadu čar

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

Je jasné, že a . Protože každá přímka je incidentní s N body (tj. jednou pro každý ), počet výskytů je roven , což odpovídá horní hranici [3] . $|P|=2N^{3}$ $|L|=N^{3}$ $x\in \{1,\cdots ,N\}$ ${\displaystyle N^{4))$

Zobecnění pro R d

Zobecnění tohoto výsledku pro libovolnou dimenzi R d našli Agaval a Aronov [4] . Je-li dána množina S obsahující n bodů a množina H obsahující m nadrovin, je počet výskytů bodů z S a nadrovin z H omezen výše počtem

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

Ekvivalentně je počet nadrovin v H obsahujících k nebo více bodů omezen výše počtem

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

Edelbrunnerova konstrukce ukazuje, že hranice je asymptoticky optimální [5] .

Soimoshi a Tao získali téměř přesnou horní hranici pro počet výskytů mezi body a algebraickými varietami ve vysokorozměrných prostorech. Jejich důkaz využívá polynomiální sendvičovou větu [6] .

Aplikace

Szemeredy-Trotterova věta nachází mnoho aplikací v aditivní [7] [8] [9] a aritmetické kombinatorice (například k prokázání věty o součtu součinu [10] ).

Poznámky

↑ Szemerédi, Klusák, 1983 , str. 381–392.
↑ Szekely, 1997 , str. 353–358.
↑ Tao, 2011 .
↑ Agarwal, Aronov, 1992 , str. 359–369.
↑ Edelsbrunner, 1987 .
↑ Solymosi, Tao, 2012 .
↑ Tomasz Schoen, Ilja Shkredov, „O množinách konvexních množin“ . Získáno 19. listopadu 2018. Archivováno z originálu 12. června 2018. (neurčitý)
↑ A. Iosevich, S. Konyagin, M. Rudnev a V. Ten, "O kombinatorické složitosti konvexních sekvencí", 19. července 2004 . Získáno 19. listopadu 2018. Archivováno z originálu 12. června 2018. (neurčitý)
↑ Elekes, Nathanson, Ruzsa, "Konvexita a součty" (odkaz není k dispozici) . Získáno 19. listopadu 2018. Archivováno z originálu 12. června 2018. (neurčitý)
↑ G. Elekes, O počtu součtů a součinů, Acta Arith. 81 (1997), 365-367. . Datum přístupu: 19. listopadu 2018. Archivováno z originálu 7. února 2019. (neurčitý)

Literatura

Endre Szemerédi, William T. Trotter. Extrémní problémy v diskrétní geometrii // Combinatorica. - 1983. - T. 3 , no. 3–4 . — S. 381–392 . - doi : 10.1007/BF02579194 .
László A. Szekely. Křížení čísel a tvrdé Erdősovy problémy v diskrétní geometrii // Kombinatorika, pravděpodobnost a výpočetní technika . - 1997. - T. 6 , no. 3 . — S. 353–358 . - doi : 10.1017/S0963548397002976 .
Terence Tao. Věta o incidenci ve vyšších dimenzích. — 2011.
Pankaj Agarwal, Boris Aronov. Počítání faset a dopadů // Diskrétní a výpočetní geometrie . - Springer, 1992. - V. 7 , no. 1 . — S. 359–369 . - doi : 10.1007/BF02187848 .
Herbert Edelsbrunner. 6.5 Dolní hranice pro mnoho buněk // Algoritmy v kombinatorické geometrii . - Springer-Verlag, 1987. - ISBN 3-540-13722-X .
J. Solymosi, Terence Tao. Věta o incidenci ve vyšších dimenzích // Diskrétní a výpočetní geometrie . - 2012. - T. 48 , č. 2 . - doi : 10.1007/s00454-012-9420-x .

Další čtení

Fedor Nilov, Alexander Polyansky, Nikita Polyansky 26. letní konference Mezinárodního matematického turnaje měst (02.08.2014-11.08.2014). — Kaliningrad-Ushakovo, 2014.