Szemerédi–Trotter-tétel

A Szemerédi–Trotter-tétel a matematika, ezen belül a diszkrét geometria egyik fontos tétele. Pach János, Radoš Radoičić, Tóth Géza és Tardos Gábor megmutatták, hogy legfeljebb ${\displaystyle 2{,}5n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m}$ illeszkedés lehetséges.^[1] A jelenlegi ismert legjobb felső határ 2,44.^[2] A felső határ nem teljesül 0,42-os együttható esetén.^[3]

A tétel állítása

Ha a síkban adott n pont és m egyenes, akkor a köztük levő illeszkedések száma ${\displaystyle O(n^{2/3}m^{2/3}+n+m)}$.

A tétel másik formája

Ha a síkban adott n pont és k>2, akkor azon egyenesek száma, amelyek a pontok közül legalább k-t tartalmaznak, ${\displaystyle O(n^{2}/k^{3}+n/k)}$. Ezt Szemerédi és Trotter cellafelbontással bizonyították.^[4][5]

Jegyzetek

1. Pach János (2006). „Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs”. Discrete & Computational Geometry 36 (4), 527–552. o. DOI:10.1007/s00454-006-1264-9. 
2. Ackerman, Eyal (2019. december 1.). „On topological graphs with at most four crossings per edge”. Computational Geometry 85, 101574. o. DOI:10.1016/j.comgeo.2019.101574. ISSN 0925-7721. 
3. (1997) „Graphs drawn with few crossings per edge”. Combinatorica 17 (3), 427–439. o. DOI:10.1007/BF01215922. 
4. Szemerédi Endre (1983). „Extremal problems in discrete geometry”. Combinatorica 3 (3–4), 381–392. o. DOI:10.1007/BF02579194. 
5. Szemerédi Endre (1983). „A Combinatorial Distinction Between the Euclidean and Projective Planes”. European Journal of Combinatorics 4 (4), 385–394. o. DOI:10.1016/S0195-6698(83)80036-5.