Théorème de Szemerédi-Trotter

La preuve originelle était assez compliquée, utilisant une technique combinatoire appelée décomposition en cellules. Par la suite, Székely a découvert la preuve bien plus simple suivante[2], qui utilise l'inégalité du nombre de croisements[3] - [4] pour les graphes.

Comme les droites ne contenant que 0, 1 ou 2 des n points ne contribuent au total que par au plus 2m incidences, on peut sans perte de généralité supposer qu'il n'y en a pas. Si une droite contient k des n points, alors elle contient k – 1 segments joignant deux de ces points et n'en contenant aucun autre, soit (puisque k ≥ 3) au moins k/2 segments. En sommant sur les m droites, on obtient ainsi que le nombre e de tous ces segments vaut au moins la moitié du nombre total d'incidences. Il suffit donc de montrer que

${\displaystyle e=O(n^{2/3}m^{2/3}+n+m).}$

Considérons alors le graphe simple G dont les sommets sont les n points et les arêtes les e segments. Comme tous les segments sont sur l'une des m droites, le nombre cr(G) de croisements de ce graphe est au plus m². Or l'inégalité du nombre de croisements assure que si e > 7,5n, alors cr(G) ≥ e³/33,75n². On est donc dans l'un (au moins) des deux cas suivants : e ≤ 7,5n ou e ≤ (33,75n²cr(G))^1/3 ≤ 3,24n^2/3m^2/3, ce qui fournit la majoration asymptotique souhaitée.

Soit m (fonction de n et k) le nombre maximum possible de droites passant par k des n points. Dans la configuration correspondante, il y a au moins mk incidences donc, d'après la première formulation, il existe une constante C telle que

${\displaystyle mk\leq C\max(n^{2/3}m^{2/3},n,m)}$

ce qui, pour les k > C, fournit la majoration souhaitée :

${\displaystyle m\leq C^{3}n^{2}/k^{3}~{\text{ou}}~m\leq Cn/k.}$

Quant aux k compris entre 2 et C, ils vérifient aussi le théorème car pour eux,

${\displaystyle m\leq {n \choose 2}<n^{2}\leq C^{3}n^{2}/k^{3}.}$

Excepté la précision sur les constantes qui interviennent dans les « O », le majorant de Szemerédi-Trotter ne peut pas être amélioré. Considérons en effet, pour un entier N > 0, les points (a , b) à coordonnées entières telles que 1 ≤ a ≤ N et 1 ≤ b ≤ 2N² (donc n = 2N³) et les droites d'équations y = cx + d avec c et d entiers tels que 1 ≤ c ≤ N et 1 ≤ d ≤ N ² (donc m = N³). Chaque droite est incidente à N points (d'abscisses 1, 2, … , N) donc le nombre d'incidences est N⁴, ce qui correspond au majorant[5].

Pankaj K. Agarwal (en) et Boris Aronov (en)[6] ont généralisé ce résultat en dimension quelconque d : le nombre d'incidences, entre n points et m hyperplans dont chacun est engendré par ces points, est

${\displaystyle O(m^{2/3}n^{d/3}+n^{d-1})}$

ou, ce qui est équivalent, le nombre de ces hyperplans qui contiennent au moins k de ces points est

${\displaystyle O(n^{d}/k^{3}+n^{d-1}/k).}$

Une construction due à Herbert Edelsbrunner (en) montre qu'à nouveau, cette majoration asymtotique est optimale[7].

József Solymosi (en) et Terence Tao ont obtenu des majorations fines voisines, pour le nombre d'incidences entre des points et des variétés algébriques, en dimensions supérieures. Leur démonstration utilise une version polynomiale du théorème du sandwich au jambon[5].