Théorème de Szemerédi-Trotter

Théorème de Szemerédi-Trotter Le théorème de Szemerédi-Trotter est un résultat mathématique dans le domaine de la géométrie discrète. Il affirme que étant donné n points et m lignes dans le plan euclidien, le nombre d'incidents (c'est à dire., le nombre de paires point-ligne, telle que le point se situe sur la droite) est {style d'affichage Oleft(n^{frac {2}{3}}moi ^{frac {2}{3}}+n+mright).} Cette borne ne peut pas être améliorée, sauf en termes de constantes implicites.

Quant aux constantes implicites, il a été montré par János Pach, Radoš Radoičić, Gabor Tardos, et Géza Toth[1] que la borne supérieure {style d'affichage 2.5n^{2/3}moi ^{2/3}+n+m} détient. Depuis lors, de meilleures constantes sont connues grâce à de meilleures constantes de lemme de croisement; le meilleur actuel est 2.44.[2] D'autre part, Pach et Tóth ont montré que l'énoncé n'est pas vrai si l'on remplace le coefficient 2.5 avec 0.42.[3] Une formulation équivalente du théorème est la suivante. Étant donné n points et un entier k ≥ 2, le nombre de lignes qui passent par au moins k des points est {style d'affichage Oleft({frac {n^{2}}{k^{3}}}+{frac {n}{k}}droit).} L'épreuve originale d'Endre Szemerédi et William T. Trotter était un peu compliqué, en utilisant une technique combinatoire connue sous le nom de décomposition cellulaire.[4][5] Plus tard, László Székely a découvert une preuve beaucoup plus simple en utilisant l'inégalité des nombres croisés pour les graphes.[6] (Voir ci-dessous.) Le théorème de Szemerédi-Trotter a plusieurs conséquences, y compris le théorème de Beck en géométrie d'incidence et le problème du produit somme d'Erdős-Szemerédi en combinatoire additive.

Contenu 1 Preuve de la première formulation 2 Preuve de la deuxième formulation 3 Optimalité 4 Généralisation à '"`UNIQ--postMath-00000011-Qinu`"' 5 Dans '"`UNIQ--postMath-00000015-Qinu`"' 6 Dans les corps finis 6.1 Grands ensembles de limites d'incidence 6.2 Limites d'incidence de petit ensemble 7 References Proof of the first formulation We may discard the lines which contain two or fewer of the points, car ils peuvent contribuer au plus 2 millions d'incidences au nombre total. On peut donc supposer que chaque ligne contient au moins trois des points.

Si une ligne contient k points, alors il contiendra k − 1 segments de ligne qui relient deux points consécutifs le long de la ligne. Parce que k ≥ 3 après avoir supprimé les lignes à deux points, il s'ensuit que k − 1 ≥k/2, donc le nombre de ces segments de ligne sur chaque ligne est au moins la moitié du nombre d'incidences sur cette ligne. Sommation sur toutes les lignes, le nombre de ces segments de ligne est à nouveau au moins égal à la moitié du nombre total d'incidences. Ainsi, si e désigne le nombre de tels segments de droite, il suffira de montrer que {style d'affichage e=Oleft(n^{frac {2}{3}}moi ^{frac {2}{3}}+n+mright).} Considérons maintenant le graphe formé en utilisant les n points comme sommets, et les segments de ligne e comme arêtes. Puisque chaque segment de ligne se trouve sur l'une des m lignes, et deux droites quelconques se coupent en au plus un point, le nombre de croisements de ce graphique est au plus le nombre de points où deux droites se croisent, qui est au plus m(m- 1)/2. L'inégalité du nombre de croisements implique que soit e ≤ 7,5n, ou que m(m- 1)/2 ≥ e3 / 33.75n2. Dans les deux cas e ≤ 3.24(nm)2/3 + 7.5n, donnant la borne désirée {style d'affichage e=Oleft(n^{frac {2}{3}}moi ^{frac {2}{3}}+n+mright).} Proof of the second formulation Since every pair of points can be connected by at most one line, il peut y avoir au plus n(n- 1)/2 lignes qui peuvent se connecter en k points ou plus, puisque k ≥ 2. Cette borne prouvera le théorème lorsque k est petit (par exemple. si k ≤ C pour une constante absolue C). Ainsi, il suffit de considérer le cas où k est grand, dire k ≥ C.

Supposons qu'il existe m lignes contenant chacune au moins k points. Ces lignes génèrent au moins mk incidences, et donc par la première formulation du théorème de Szemerédi-Trotter, Nous avons {style d'affichage mk=Oleft(n^{frac {2}{3}}moi ^{frac {2}{3}}+n+mright),} et donc au moins une des déclarations {style d'affichage mk=O(n^{2/3}moi ^{2/3}),mk=O(n)} , ou {style d'affichage mk=O(m)} est vrai. La troisième possibilité est exclue puisque k est supposé être grand, il nous reste donc les deux premiers. Mais dans l'un ou l'autre de ces deux cas, une algèbre élémentaire donnera la borne {style d'affichage m=O(n^{2}/k^{3}+n/k)} comme voulu.

Optimality Except for its constant, la borne d'incidence de Szemerédi – Trotter ne peut pas être améliorée. Pour voir ça, considérer pour tout entier positif {style d'affichage Nin mathbb {N} } un ensemble de points sur le réseau entier {style d'affichage P=gauche{(un,b)en mathbb {Z} ^{2} : 1leq aleq N;1leq bleq 2N^{2}droit},} et un ensemble de lignes {style d'affichage L=gauche{(X,mx+b) : m,suis mathbb {Z} ;1leq mleq N;1leq bleq N^{2}droit}.} Clairement, {style d'affichage |P|=2N^{3}} et {style d'affichage |L|=N^{3}} . Puisque chaque droite est incidente à N points (c'est à dire., une fois pour chaque {style d'affichage xin {1,cdots ,N}} ), le nombre d'incidents est {displaystyle N^{4}} qui correspond à la borne supérieure.[7] Généralisation à {style d'affichage mathbb {R} ^{ré}} Une généralisation de ce résultat à une dimension arbitraire, {style d'affichage mathbb {R} ^{ré}} , a été trouvé par Agarwal et Aronov.[8] Soit un ensemble de n points, S, et l'ensemble des m hyperplans, H, qui sont chacun engendrés par S, le nombre d'incidences entre S et H est majoré par {style d'affichage Oleft(moi ^{frac {2}{3}}n^{frac {ré}{3}}+n^{j-1}droit).} De manière équivalente, le nombre d'hyperplans dans H contenant k points ou plus est majoré par {style d'affichage Oleft({frac {n^{ré}}{k^{3}}}+{frac {n^{j-1}}{k}}droit).} Une construction due à Edelsbrunner montre que celle-ci est asymptotiquement optimale.[9] József Solymosi et Terence Tao ont obtenu des bornes supérieures presque nettes pour le nombre d'incidences entre les points et les variétés algébriques en dimensions supérieures, lorsque les points et les variétés satisfont "certains axiomes de type pseudo-ligne". Leur preuve utilise le théorème polynomial du sandwich au jambon.[10] Dans {style d'affichage mathbb {C} ^{2}} De nombreuses preuves du théorème de Szemerédi-Trotter sur {style d'affichage mathbb {R} } s'appuient de manière cruciale sur la topologie de l'espace euclidien, donc ne pas s'étendre facilement à d'autres domaines. par exemple. la preuve originale de Szemerédi et Trotter; la preuve de partitionnement polynomial et la preuve du nombre de croisements ne s'étendent pas au plan complexe.

Tóth a généralisé avec succès la preuve originale de Szemerédi et Trotter au plan complexe {style d'affichage mathbb {C} ^{2}} en introduisant des idées supplémentaires.[11] Ce résultat a également été obtenu indépendamment et par une méthode différente par Zahl.[12] La constante implicite dans la borne n'est pas la même dans les nombres complexes: dans la preuve de Tóth, la constante peut être considérée comme étant {style d'affichage 10 ^{60}} ; la constante n'est pas explicite dans la preuve de Zahl.

Lorsque l'ensemble de points est un produit cartésien, Solymosi et Tardos montrent que la borne de Szemerédi-Trotter est vraie en utilisant un argument beaucoup plus simple.[13] In finite fields Let {style d'affichage mathbb {F} } être un champ.

Un bond Szemerédi-Trotter est impossible en général à cause de l'exemple suivant, indiqué ici dans {style d'affichage mathbb {F} _{p}} : laisser {style d'affichage {mathématique {P}}=mathbb {F} _{p}fois mathbb {F} _{p}} être l'ensemble de tous {style d'affichage p^{2}} points et laisser {style d'affichage {mathématique {L}}} être l'ensemble de tous {style d'affichage p^{2}} lignes dans l'avion. Comme chaque ligne contient {style d'affichage p} points, il y a {style d'affichage p^{3}} incidences. D'autre part, la borne Szemerédi-Trotter donnerait {style d'affichage O((p^{2})^{2/3}(p^{2})^{2/3}+p^{2})= O(p^{8/3})} incidences. Cet exemple montre que le trivial, la borne d'incidence combinatoire est étroite.

Bourgain, Katz et Tao[14] montrer que si cet exemple est exclu, alors une borne d'incidence qui est une amélioration de la borne triviale peut être atteinte.

Les bornes d'incidence sur les corps finis sont de deux types: (je) lorsqu'au moins l'un des ensembles de points ou de lignes est "grand" en termes de caractéristique du champ; (ii) l'ensemble de points et l'ensemble de lignes sont "petits" en termes de caractéristique.

Large set incidence bounds Let {style d'affichage q} être une puissance première impaire. Puis Vinh[15] a montré que le nombre d'incidences entre {displaystyle n} points et {style d'affichage m} lignes dans {style d'affichage mathbb {F} _{q}^{2}} est au plus {style d'affichage {frac {nm}{q}}+{sqrt {quelqu'un}}.} Notez qu'il n'y a pas de constante implicite dans cette borne.

Small set incidence bounds Let {style d'affichage mathbb {F} } être un champ de caractéristique {style d'affichage pneq 2} . Stevens et de Zeeuw[16] montrent que le nombre d'incidences entre {displaystyle n} points et {style d'affichage m} lignes dans {style d'affichage mathbb {F} ^{2}} est {style d'affichage Oleft(moi ^{frac {11}{15}}n^{frac {11}{15}}droit)} sous condition {style d'affichage m^{-2}n^{13}leq p^{15}} en caractéristique positive. (Dans un champ de caractéristique zéro, cette condition n'est pas nécessaire.) Cette borne est meilleure que l'estimation triviale de l'incidence lorsque {style d'affichage m^{7/8}Discrete & Computational Geometry. 36 (4): 527–552. est ce que je:10.1007/s00454-006-1264-9. ^ Ackermann, Eyal (Décembre 2019). "Sur les graphes topologiques avec au plus quatre croisements par arête". Géométrie computationnelle. 85: 101574. arXiv:1509.01932. est ce que je:10.1016/j.comgeo.2019.101574. ISSN 0925-7721. S2CID 16847443. ^ Odeur, John; Toth, Géza (1997). "Graphiques dessinés avec peu de croisements par arête". Combinatoire. 17 (3): 427–439. CiteSeerX 10.1.1.47.4690. est ce que je:10.1007/BF01215922. S2CID 20480170. ^ Szemeredi, Changer; Trotteur, Guillaume T.. (1983). "Problèmes extrêmes en géométrie discrète". Combinatoire. 3 (3–4): 381–392. est ce que je:10.1007/BF02579194. M 0729791. S2CID 1750834. ^ Szemeredi, Changer; Trotteur, Guillaume T.. (1983). "Une distinction combinatoire entre les plans euclidien et projectif" (PDF). Journal européen de combinatoire. 4 (4): 385–394. est ce que je:10.1016/S0195-6698(83)80036-5. ^ Szekeley, Laszlo A. (1997). "Nombres croisés et problèmes d'Erdős durs en géométrie discrète". Combinatoire, Probabilité et calcul. 6 (3): 353–358. CiteSeerX 10.1.1.125.1484. est ce que je:10.1017/S0963548397002976. M 1464571. S2CID 36602807. ^ Térence Tao (Mars 17, 2011). "Un théorème d'incidence en dimension supérieure". Récupéré en août 26, 2012. ^ Agarwal, Pankaj; Aronov, Boris (1992). "Compter les facettes et les incidences". Discrete & Computational Geometry. 7 (1): 359–369. est ce que je:10.1007/BF02187848. ^ Edelsbrunner, Herbert (1987). "6.5 Bornes inférieures pour de nombreuses cellules". Algorithmes en géométrie combinatoire. Springer Verlag. ISBN 978-3-540-13722-1. ^ Solymosis, Joseph; Tao, Térence (Septembre 2012). "Un théorème d'incidence en dimension supérieure". Discrete & Computational Geometry. 48 (2): 255–280. arXiv:1103.2926. est ce que je:10.1007/s00454-012-9420-x. M 2946447. S2CID 17830766. ^ Toth, Csaba D. (2015). "Le théorème de Szemerédi-Trotter dans le plan complexe". Combinatoire. 35 (1): 95–126. arXiv:mathématiques/0305283. est ce que je:10.1007/s00493-014-2686-2. S2CID 13237229. ^ nombre, Josué (2015). "Le théorème de type Szemerédi-Trotter en ℝ4". Discrete & Computational Geometry. 54 (3): 513–572. arXiv:1203.4600. est ce que je:10.1007/s00454-015-9717-7. S2CID 16610999. ^ Solymosis, Joseph; Ça dure, Gabor (2007). "Sur le nombre de transformations riches en k". Actes du vingt-troisième symposium annuel sur la géométrie computationnelle - SCG '07. SCG '07. New York, New York, Etats-Unis: Presse ACM: 227–231. est ce que je:10.1145/1247069.1247111. ISBN 978-1-59593-705-6. S2CID 15928844. ^ Bourgain, Jean; Katz, Filets; Tao, Térence (2004-02-01). "Une estimation de produit somme dans des champs finis, et applications". Analyse géométrique et fonctionnelle. 14 (1): 27–57. arXiv:mathématiques/0301343. est ce que je:10.1007/s00039-004-0451-1. ISSN 1016-443X. S2CID 14097626. ^ Vin, Le Anh (Novembre 2011). "Le théorème de type Szemerédi – Trotter et l'estimation somme-produit dans les corps finis". Journal européen de combinatoire. 32 (8): 1177–1181. arXiv:0711.4427. est ce que je:10.1016/j.ejc.2011.06.008. ISSN 0195-6698. S2CID 1956316. ^ Steven, Sophie; l'habitant de Zeeland, Franc (2017-08-03). "Une incidence de ligne ponctuelle améliorée liée sur des champs arbitraires". Bulletin de la London Mathematical Society. 49 (5): 842–858. arXiv:1609.06284. est ce que je:10.1112/blms.12077. ISSN 0024-6093. S2CID 119635655. ^ Roudnev, Micha; Chkredov, Ilya D. (2018). "Sur le taux de croissance en SL_2(F_p), les implications du groupe affine et du type somme-produit". arXiv:1812.01671 [math.CO]. hide vte Incidence structures Representation Incidence matrixIncidence graph Fields Combinatorics Block designSteiner systemGeometry IncidenceProjective planeGraph theory HypergraphStatistics Blocking Configurations Complete quadrangleFano planeMöbius–Kantor configurationPappus configurationHesse configurationDesargues configurationReye configurationSchläfli double sixCremona–Richmond configurationKummer configurationGrünbaum–Rigby configurationKlein configurationDual Theorems Sylvester–Gallai theoremDe Bruijn–Erdős theoremSzemerédi–Trotter theoremBeck's theoremBruck–Ryser–Chowla theorem Applications Design of experimentsKirkman's schoolgirl problem Categories: Géométrie plane euclidienneThéorèmes de géométrie discrèteThéorèmes de combinatoire