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 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 .

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, . Ezt Szemerédi és Trotter cellafelbontással bizonyították. Jegyzetek

Kategória:Matematikai tételek Kategória:Diszkrét geometriai tételek Kategória:Kombinatorikai tételek