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 $2,5n^{\frac{2}{3}}{m}^{\frac{2}{3}}+n+m$ illeszkedés lehetséges. A jelenlegi ismert legjobb felső határ 2,44. A felső határ nem teljesül 0,42-os együttható esetén.

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 $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, $O(n^2/k^3+n/k)$. Ezt Szemerédi és Trotter cellafelbontással bizonyították.