Teorema Szemeredi-Trotter

Teorema Szemeredi-Trotter este un rezultat al geometriei combinatorii . Teorema afirmă că date n puncte și m linii dintr-un plan, numărul de incidențe (adică numărul de perechi punct/linie în care un punct se află pe o dreaptă) este

iar această legătură nu poate fi îmbunătățită.

O formulare echivalentă a teoremei este următoarea. Având n puncte și un număr întreg k > 2 , numărul de linii care trec prin cel puțin k puncte este

Dovada originală a lui Szemeredi și Trotter [1] a fost complexă și a folosit o tehnică combinatorie cunoscută sub numele de diviziune celulară . Mai târziu, Szekei a descoperit o demonstrație mult mai simplă folosind inegalitatea numerelor de intersecție pentru grafice [2] (vezi mai jos).

Teorema Szemeredi–Trotter are mai multe consecințe, inclusiv teorema lui Beck în geometria incidenței .

Dovada primei afirmații

Putem renunța liniile care conțin două sau mai puține puncte, deoarece pot da incidențe de maximum 2 m . Astfel, putem presupune că orice linie conține cel puțin trei puncte.

Dacă o linie conține k puncte, atunci conține k − 1 segmente de linie care leagă două dintre cele n puncte. În special, linia va conține cel puțin k /2 astfel de segmente, deoarece am presupus k ≥ 3 . Adunând toate astfel de incidențe de-a lungul tuturor m liniilor, aflăm că numărul de segmente obținute în acest fel este cel puțin egal cu jumătate din numărul tuturor incidențelor. Dacă notăm cu e numărul de astfel de segmente, este suficient să arătăm că

Considerăm acum un grafic format din n puncte ca vârfuri și e segmente ca muchii. Deoarece fiecare segment se află pe una dintre cele m drepte și două drepte se intersectează cel mult într-un punct, numărul de intersecții ale acestui grafic nu depășește m 2 . Din inegalitatea numerelor de intersecție, concluzionăm că fie e ≤ 7,5 n , fie m 2 ≥ e 3 / 33,75 n 2 . În orice caz, e ≤ 3,24( nm ) 2/3 + 7,5 n și obținem limita necesară

Dovada celei de-a doua formulări

Deoarece orice pereche de puncte poate fi conectată prin cel mult o linie, pot exista cel mult n ( n − 1)/2 l linii care pot conecta k sau mai multe puncte deoarece k ≥ 2 . Această limită demonstrează teorema pentru k mic (de exemplu, dacă k ≤ C pentru o constantă absolută C ). Astfel, are sens doar să luăm în considerare cazurile în care k este mare, să spunem k ≥ C.

Să presupunem că există m linii, fiecare conținând cel puțin k puncte. Aceste linii formează cel puțin mk incidențe și apoi, prin prima variantă a teoremei Szemerédy–Trotter, avem

şi cel puţin o egalitate din sau este satisfăcută . Renunțăm la a treia posibilitate deoarece am presupus că k este mare, deci primele două rămân. Dar în ambele cazuri, după calcule algebrice simple, obținem , ceea ce este necesar.

Optimitatea

Dacă factorii constanți nu sunt luați în considerare, limita de incidență Szemeredy-Trotter nu poate fi îmbunătățită. Pentru a vedea acest lucru, luați în considerare pentru orice număr întreg pozitiv N ∈ Z + mulțimea de puncte a rețelei întregi

și un set de linii

Este clar că și . Deoarece fiecare linie este incidentă la N puncte (adică o dată pentru fiecare ), numărul de incidențe este egal cu , ceea ce corespunde limitei superioare [3] .

Generalizare pentru R d

O generalizare a acestui rezultat pentru o dimensiune arbitrară R d a fost găsită de Agaval și Aronov [4] . Având în vedere o mulțime S care conține n puncte și o mulțime H care conține m hiperplane, numărul de incidențe ale punctelor din S și hiperplanurilor din H este mărginit mai sus de numărul

În mod echivalent, numărul de hiperplanuri din H care conțin k sau mai multe puncte este mărginit deasupra de numărul

Construcția Edelbrunner arată că limita este optimă asimptotic [5] .

Soimoshi și Tao au obținut o limită superioară aproape exactă pentru numărul de apariții între puncte și varietăți algebrice în spații de dimensiuni mari. Demonstrarea lor folosește teorema polinomială sandwich [6] .

Aplicații

Teorema Szemeredy-Trotter găsește multe aplicații în combinatorie aditivă [7] [8] [9] și aritmetică (de exemplu, pentru a demonstra teorema produsului sumă [10] ).

Note

  1. ↑ Szemerédi, Trotter, 1983 , p. 381–392.
  2. ↑ Szekely, 1997 , p. 353–358.
  3. ↑ Tao, 2011 .
  4. ↑ Agarwal, Aronov, 1992 , p. 359–369.
  5. ↑ Edelsbrunner, 1987 .
  6. ↑ Solymosi, Tao, 2012 .
  7. ↑ Tomasz Schoen, Ilya Shkredov, „On Sumsets of Convex Sets” . Consultat la 19 noiembrie 2018. Arhivat din original la 12 iunie 2018.
  8. ↑ A. Iosevich, S. Konyagin, M. Rudnev și V. Ten, „On combinatorial complexity of convex sequences”, 19 iulie 2004 . Consultat la 19 noiembrie 2018. Arhivat din original la 12 iunie 2018.
  9. ↑ Elekes, Nathanson, Ruzsa, „Convexity and sumsets” (link nu este disponibil) . Consultat la 19 noiembrie 2018. Arhivat din original la 12 iunie 2018. 
  10. ↑ G. Elekes, Despre numărul de sume și produse, Acta Arith. 81 (1997), 365–367. . Data accesului: 19 noiembrie 2018. Arhivat din original pe 7 februarie 2019.

Literatură

Lectură suplimentară