Théorème de Szemerédi-Trotter

Le théorème de Szemerédi-Trotter est un résultat de géométrie combinatoire, dû à Endre Szemerédi et William T. Trotter^[1], qui donne la majoration asymptotique (optimale) suivante :

pour n points et m droites du plan, le nombre d'incidences (en) (c'est-à-dire le nombre de couples (point, droite) tels que le point appartient à la droite) est

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

ou, de manière équivalente, pour n points et un entier k ≥ 2, le nombre de droites passant par au moins k de ces n points est

${\displaystyle O(n^{2}/k^{3}+n/k).}$

Ce théorème a de nombreux corollaires, dont le théorème de Beck en géométrie d'incidence (en).

Preuve de la première formulation

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.

Preuve de la seconde formulation

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

Optimalité

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

Généralisation à ℝd

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

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Szemerédi–Trotter theorem » (voir la liste des auteurs).

1. (en) Endre Szemerédi et William T. Trotter, « Extremal problems in discrete geometry », Combinatorica, vol. 3, n^os 3-4,‎ 1983, p. 381-392 (DOI 10.1007/BF02579194)
2. (en) László A. Székely, « Crossing numbers and hard Erdős problems in discrete geometry », Combinatorics, Probability and Computing, vol. 6, n^o 3,‎ 1997, p. 353-358 (lire en ligne)
3. (en) M. Ajtai, V. Chvátal, M. Newborn et E. Szemerédi, « Crossing-free subgraphs », dans Theory and Practice of Combinatorics, coll. « North-Holland Mathematics Studies » (n^o 60), 1982 (lire en ligne), p. 9-12
4. (en) T. Leighton (en), Complexity Issues in VLSI, MIT Press, coll. « Foundations of Computing Series », 1983
5. (en) Jozsef Solymosi et Terence Tao, « An incidence theorem in higher dimensions », Discrete Comput. Geom., vol. 48, n^o 2,‎ septembre 2012, p. 255-280, arXiv:1103.2926 et commentaires sur le blog de T. Tao
6. (en) Pankaj Agarwal et Boris Aronov, « Counting facets and incidences », Discrete Comput. Geom., vol. 7, n^o 1,‎ 1992, p. 359-369 (lire en ligne)
7. (en) Herbert Edelsbrunner, Algorithms in Combinatorial Geometry, Springer, 1987, 423 p. (ISBN 978-3-540-13722-1, lire en ligne), chap. 6.5 (« Lower bounds for many cells »)

• Portail des mathématiques