Voir la source de Théorème de Szemerédi-Trotter

{{Confusion|Théorème de Szemerédi}}
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<ref>{{article|lang=en|nom=Szemerédi|prénom=Endre|prénom2=William T.|nom2=Trotter|titre=Extremal problems in discrete geometry|lien périodique=Combinatorica|revue=Combinatorica|vol=3|numéro=3-4|année=1983|p.=381-392|doi=10.1007/BF02579194}}</ref>, qui donne la [[Comparaison asymptotique#Domination|majoration asymptotique]] (optimale) suivante :

pour ''n ''points et ''m ''droites du [[Plan affine|plan]], le nombre d'{{Lien|trad=Incidence (geometry)|Incidence (géométrie)|texte=incidences}} (c'est-à-dire le nombre de couples (point, droite) tels que le point appartient à la droite) est

<center><math>O(n^{2/3}m^{2/3}+n+m)</math></center>

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

<center><math>O(n^2/k^3+n/k).</math></center>

Ce théorème a de nombreux [[Corollaire (mathématiques)|corollaire]]s, dont le [[théorème de Beck]] en {{Lien|trad=Incidence geometry|géométrie d'incidence}}.

== Preuve de la première formulation ==
La preuve originelle était assez compliquée, utilisant une technique combinatoire appelée [[CW-complexe|décomposition en cellules]]. Par la suite, Székely a découvert la preuve bien plus simple suivante<ref>{{article|lang=en|nom=Székely|prénom=László A.|année=1997|titre=Crossing numbers and hard Erdős problems in discrete geometry|revue=Combinatorics, Probability and Computing|vol=6|numéro=3|p.=353-358|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.125.1484}}</ref>, qui utilise l'''inégalité du [[Nombre de croisements (théorie des graphes)|nombre de croisements]]<ref>{{chapitre|lang=en|lien auteur1=Miklós Ajtai|nom1=Ajtai|prénom1=M.|lien auteur2=Václav Chvátal|prénom2=V.|nom2=Chvátal|nom3=Newborn|prénom3=M.|nom4=Szemerédi|prénom4=E.|titre=Crossing-free subgraphs|titre ouvrage=Theory and Practice of Combinatorics|collection=North-Holland Mathematics Studies|numéro dans collection=60|année=1982|passage=9-12|url=https://books.google.fr/books?id=lcHcXrVhRUUC&pg=PA9}}</ref>{{,}}<ref>{{Ouvrage|langue=en|nom1={{Lien|F. Thomson Leighton|texte=T. Leighton}}|titre=Complexity Issues in VLSI|éditeur=[[MIT Press]]|collection=Foundations of Computing Series|année=1983|isbn=}}</ref> ''pour les [[Théorie des graphes|graphes]].

Comme les droites ne contenant que 0, 1 ou  2 des ''n ''points ne contribuent au total que par au plus 2''m'' 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

<center><math>e=O(n^{2/3}m^{2/3}+n+m).</math></center>

Considérons alors le [[graphe (mathématiques discrètes)|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''{{2}}. Or l'inégalité du nombre de croisements assure que si ''e ''> 7,5''n'', alors cr(''G'') ≥ ''e''{{3}}/33,75''n''{{2}}. On est donc dans l'un (au moins) des deux cas suivants : ''e ''≤ 7,5''n'' ou {{nobr|''e ''≤ (33,75''n''{{2}}cr(''G'')){{exp|1/3}} ≤ 3,24''n''{{exp|2/3}}''m''{{exp|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

<center><math>mk\le C\max(n^{2/3}m^{2/3},n,m)</math></center>

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

<center><math>m\le C^3n^2/k^3~\text{ou}~m\le Cn/k.</math></center>

Quant aux ''k ''compris entre 2 et ''C'', ils vérifient aussi le théorème car pour eux,
<center><math>m\le{n\choose2}<n^2\le C^3n^2/k^3.</math></center>

== Optimalité ==
Excepté la précision sur les constantes qui interviennent dans les « [[Comparaison asymptotique#Domination|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 ''≤ 2''N''{{2}} (donc ''n ''= 2''N''{{3}}) et les droites d'équations ''y = cx + d'' avec ''c ''et ''d ''entiers tels que 1 ≤ ''c ''≤ ''N ''et 1 ≤ ''d ''≤ ''N ''{{2}} (donc ''m = N''{{3}}). Chaque droite est incidente à ''N ''points (d'abscisses 1, 2, … , ''N'') donc le nombre d'incidences est ''N''{{4}}, ce qui correspond au majorant<ref name=ST>{{article|lang=en|prénom=Jozsef|nom=Solymosi|prénom2=Terence|nom2=Tao|lien auteur2=Terence Tao|titre=An incidence theorem in higher dimensions|revue=Discrete Comput. Geom.|vol=48|numéro=2|mois=9|année=2012|p.=255-280}}, {{arxiv2|1103.2926}} et [http://terrytao.wordpress.com/tag/szemeredi-trotter-theorem/ commentaires] sur le blog de T. Tao</ref>.

== Généralisation à ℝ{{exp|''d''}} ==
{{Lien|Pankaj K. Agarwal}} et {{Lien|Boris Aronov}}<ref>{{article|lang=en|nom=Agarwal|prénom=Pankaj|nom2=Aronov|prénom2=Boris|titre=Counting facets and incidences|année=1992|revue=Discrete Comput. Geom.|vol=7|numéro=1|p.=359-369|url=http://www.cs.duke.edu/~pankaj/publications/papers/incidences.pdf}}</ref> 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

<center><math>O(m^{2/3}n^{d/3}+n^{d-1})</math></center>

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

<center><math>O(n^d/k^3+n^{d-1}/k).</math></center>

Une construction due à {{Lien|Herbert Edelsbrunner}} montre qu'à nouveau, cette majoration asymptotique est optimale<ref>{{Ouvrage|langue=en|prénom1=Herbert|nom1=Edelsbrunner|titre=Algorithms in Combinatorial Geometry|éditeur=[[Springer Verlag|Springer]]|année=1987|pages totales=423|isbn=978-3-540-13722-1|lire en ligne=https://books.google.fr/books?id=mxugg47mzK4C&pg=PA113|numéro chapitre=6.5|titre chapitre=Lower bounds for many cells}}</ref>.

{{Lien|József Solymosi}} et [[Terence Tao]] ont obtenu des majorations fines voisines, pour le nombre d'incidences entre des points et des [[Variété algébrique|variétés algébriques]], en dimensions supérieures. Leur démonstration utilise une version polynomiale du [[théorème du sandwich au jambon]]<ref name=ST/>.

== Notes et références ==
{{Traduction/Référence|en|Szemerédi–Trotter theorem|509450398|type=note}}
{{reflist}}

{{Portail|mathématiques}}

{{DEFAULTSORT:Theoreme de Szemeredi-Trotter}}
[[Catégorie:Géométrie affine]]
[[Catégorie:Géométrie discrète]]
[[Catégorie:Théorème de combinatoire|Szemeredi-Trotter]]