Перегляд вихідного коду сторінки Теорема Семереді — Троттера

'''Теорема Семереді&nbsp;— Троттера'''&nbsp;— результат [[Комбінаторна геометрія|комбінаторної геометрії]]. Теорема стверджує, що якщо дано {{Mvar|n}} точок та {{Mvar|m}} прямих на площині, кількість [[Інцидентність (геометрія)|інциденцій]] (тобто, кількість пар точка/пряма, в яких точка лежить на прямій) дорівнює

: <math>O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right ),</math>

і цю межу неможливо покращити.

Еквівалентне формулювання теореми таке. Якщо дано {{Mvar|n}} точок та ціле число {{Math|''k'' > 2}}, число прямих, що проходять принпаймні через {{Mvar|k}} точок, дорівнює

: <math>O \left( \frac{n^2}{k^3} + \frac{n}{k} \right ).</math>

Початкове доведення [[Ендре Семереді|Семереді]] та {{Не перекладено|Вільям Томас Троттер|Троттера|en|William T. Trotter}}{{Sfn|Szemerédi, Trotter|1983|с=381–392}} було складним і спиралось на комбінаторну техніку, відому як ''поділ комірок''. Пізніше Секей виявив значно простіше доведення, що використовує [[нерівність числа схрещень]] для [[Граф (математика)|графів]]{{Sfn|Székely|1997|с=353–358}} (див. нижче).

Теорема Семереді&nbsp;— Троттера має кілька наслідків, серед яких {{Не перекладено|теорема Бека||en|Beck's theorem (geometry)}} в [[Геометрія інцидентності|геометрії інцидентності]].

== Доведення першого формулювання ==
Ми можемо відкинути прямі, що містять дві і менше точок, оскільки вони можуть дати максимум {{Math|2''m''}} інциденцій. Отже, можна вважати, що будь-яка пряма містить принаймні три точки.

Якщо пряма містить {{Mvar|k}} точок, то вона містить {{Math|''k'' − 1}} відрізків, що з'єднують дві з {{Mvar|n}} точок. Зокрема, пряма міститиме принаймні {{Math|''k'' / 2}} таких відрізків, оскільки ми припустили, що {{Math|''k'' ≥ 3}}. Підрахувавши всі такі інциденції за всіма {{Mvar|m}} прямими, маємо, що число відрізків, отриманих у такий спосіб, принаймні дорівнює половині числа всіх інциденцій. Якщо позначити через {{Mvar|e}} число таких відрізків, достатньо показати, що

: <math>e = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right).</math>

Розглянемо тепер [[Граф (математика)|граф]], утворений {{Mvar|n}} точками як вершинами і ''e'' відрізками як реберами. Оскільки кожен відрізок лежить на якійсь із {{Mvar|m}} прямих і дві прямі перетинаються максимум в одній точці, [[число схрещень]] цього графа не перевищує {{Math|''m''<sup>2</sup>}}. З [[Нерівність числа схрещень|нерівності числа схрещень]] робимо висновок, що або {{Math|''e'' ≤ 7.5''n''}} або {{Math|''m''<sup>2</sup> ≥ ''e''<sup>3</sup> / 33.75''n''<sup>2</sup>}}. В будь-якому випадку {{Math|''e'' ≤ 3.24(''nm'')<sup>2/3</sup> + 7.5''n''}} і ми маємо необхідну межу

: <math>e = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right ).</math>

== Доведення другого формулювання ==
Оскільки будь-яку пару точок можна з'єднати максимум однією прямою, може бути максимум {{Math|''n''(''n'' − 1)/2}} l прямих, які можуть з'єднувати {{Mvar|k}} або більше точок, оскільки {{Math|''k'' ≥ 2}}. Ця межа доводить теорему за малих {{Mvar|k}} (наприклад, якщо {{Math|''k'' ≤ ''C''}} для деякої абсолютної сталої {{Mvar|C}}). Таким чином, є сенс розглядати лише випадки, коли {{Mvar|k}} велике, скажімо, {{Math|''k'' ≥ ''C''}}.

Припустимо, що є {{Mvar|m}} прямих, кожна з яких містить принаймні {{Mvar|k}} точок. Ці прямі утворюють принаймні{{Mvar|mk}} інциденцій, а тоді за першим варіантом теореми Семереді&nbsp;— Троттера маємо

: <math>mk = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right ),</math>

і принаймні виконується одна рівність із <math>mk = O( n^{2/3} m^{2/3} ), mk = O(n)</math> або <math>mk = O(m)</math>. Третю можливість відкидаємо, оскільки ми припустили, що {{Mvar|k}} велике, тому залишаються дві перші. Але в обох випадках після нескладних алгебричних викладок отримаємо <math>m = O( n^2 / k^3 + n/k )</math> що й було потрібно.

== Оптимальність ==
Якщо не зважати на сталі множники, межу числа інциденцій Семереді&nbsp;— Троттера не можна покращити. Щоб це побачити, розглянемо для будь-якого додатного цілого числа {{Math|''N'' ∈ '''Z'''<sup>+</sup>}} множину точок цілісної [[Ґратка (геометрія)|ґрати]]

: <math>P = \left \{ (a, b) \in \mathbf{Z}^2 \ : \ 1 \leq a \leq N; 1 \leq b \leq 2N^2 \right \},</math>

та набір прямих

: <math>L = \left \{ (x, mx + b) \ : \ m, b \in \mathbf{Z}; 1 \leq m \leq N; 1 \leq b \leq N^2 \right \}.</math>

Зрозуміло, що <math>|P| = 2N^3</math> і <math>|L| = N^3</math>. Оскільки кожна пряма інцидентна {{Mvar|N}} точкам (тобто один раз для кожного <math>x \in \{1, \cdots, N\}</math>), число інциденцій дорівнює <math>N^4</math>, що відповідає верхній межі{{Sfn|Tao|2011}}.

== Узагальнення для {{Math|'''R'''<sup>''d''</sup>}} ==
Узагальнення цього результату для довільної розмірності {{Math|'''R'''<sup>''d''</sup>}} знайшли Агавал та Аронов{{Sfn|Agarwal, Aronov|1992|с=359–369}}. Якщо дано множину {{Mvar|S}}, що містить {{Mvar|n}} точок, і множину {{Mvar|H}}, що містить {{Mvar|m}} гіперплощин, число інциденцій точок із {{Mvar|S}} і гіперплощин із {{Mvar|H}} обмежено зверху числом

: <math>O \left (m^{\frac{2}{3}}n^{\frac{d}{3}}+n^{d-1} \right ).</math>

Еквівалентно, кількість гіперплощин із {{Mvar|H}}, що містять {{Mvar|k}} і більше точок, обмежена зверху числом

: <math>O\left( \frac{n^d}{k^3} + \frac{n^{d-1}}{k} \right ).</math>

Побудова Едельбруннера показує, що межа асимптотично оптимальна{{Sfn|Edelsbrunner|1987}}.

Шоймоші та Тао отримали майже точну верхню межу для числа інциденцій між точками та алгебричними многовидами в просторах високої розмірності. У доведенні вони використали [[Теорема про бутерброд|теорему про бутерброд]]{{Sfn|Solymosi, Tao|2012}}.

== Програми ==
Теорема Семереді&nbsp;— Троттера знаходить багато застосувань у [[Адитивна комбінаторика|адитивній]]<ref>[https://www.researchgate.net/publication/51892217_On_Sumsets_of_Convex_Sets Tomasz Schoen, Ilya Shkredov, «On Sumsets of Convex Sets»]</ref><ref>[https://www.researchgate.net/publication/220452502_Combinatorial_Complexity_of_Convex_Sequences A. Iosevich, S. Konyagin, M. Rudnev, and V. Ten, «On combinatorial complexity of convex sequences», July 19, 2004]</ref><ref>{{Cite web|url=https://core.ac.uk/download/pdf/81958410.pdf|title=Elekes, Nathanson, Ruzsa, «Convexity and sumsets»|accessdate=2018-11-19|archivedate=2018-06-12|archiveurl=https://web.archive.org/web/20180612152847/https://core.ac.uk/download/pdf/81958410.pdf|deadurl=yes}}</ref> та [[Арифметична комбінаторика|арифметичній комбінаториці]] (наприклад, для доведення [[Теорема сум-добутків|теореми сум-добутків]]<ref>[http://matwbn.icm.edu.pl/ksiazki/aa/aa81/aa8145.pdf G. Elekes, On the number of sums and products, Acta Arith. 81 (1997), 365—367.]</ref>).

== Примітки ==
{{Reflist|2}}

== Література ==
* {{Стаття|author=Endre Szemerédi, William T. Trotter|ref=Szemerédi, Trotter|рік=1983|title=Extremal problems in discrete geometry|видання=Combinatorica|том=3|doi=10.1007/BF02579194|pages=381–392|issue=3–4}}
* {{Стаття|author=László A. Székely|ref=Székely|рік=1997|title=Crossing numbers and hard Erdős problems in discrete geometry|видання=[[Combinatorics, Probability and Computing]]|том=6|issue=3|pages=353–358|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.125.1484|doi=10.1017/S0963548397002976}}
* {{Стаття|url=http://terrytao.wordpress.com/tag/szemeredi-trotter-theorem/|author=Terence Tao|ref=Tao|title=An incidence theorem in higher dimensions|рік=2011|accessdate=26 серпня 2012}}
* {{Стаття|author=Pankaj Agarwal, Boris Aronov|ref=Agarwal, Aronov|title=Counting facets and incidences|рік=1992|видання=[[Discrete and Computational Geometry]]|publisher=Springer|том=7|issue=1|pages=359–369|doi=10.1007/BF02187848}}
* {{Книга
|заголовок = Algorithms in Combinatorial Geometry
|посилання = https://archive.org/details/algorithmsincomb00edel
|автор = Herbert Edelsbrunner
|ref = Edelsbrunner
|видавництво = Springer-Verlag
|рік = 1987
|частина = 6.5 Lower bounds for many cells
|ISBN = 3-540-13722-X
}}
* {{Стаття|author=J. Solymosi, Terence Tao|ref=Solymosi, Tao|title=An incidence theorem in higher dimensions|рік=2012|видання=[[Discrete and Computational Geometry]]|issue=2|том=48|doi=10.1007/s00454-012-9420-x}}

== Додаткова література ==
* {{Стаття|author=Фёдор Нилов, Александр Полянский, Никита Полянский,|ref=Нилов, Полянский, Полянский,|title=26-я летняя конференция международного математического Турнира городов (02.08.2014-11.08.2014)|place=Калининград-Ушаково|url=http://www.turgor.ru/lktg/2014/7/7-2ru.pdf|рік=2014}}
[[Категорія:Теореми комбінаторики]]
[[Категорія:Теореми дискретної геометрії]]
[[Категорія:Планіметрія]]