Теорема Семереді — Троттера

Теорема Семереді — Троттера — результат комбінаторної геометрії. Теорема стверджує, що якщо дано n точок та m прямих на площині, кількість інциденцій (тобто, кількість пар точка/пряма, в яких точка лежить на прямій) дорівнює

${\displaystyle O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right),}$

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

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

${\displaystyle O\left({\frac {n^{2}}{k^{3}}}+{\frac {n}{k}}\right).}$

Початкове доведення Семереді та Троттера^[en][1] було складним і спиралось на комбінаторну техніку, відому як поділ комірок. Пізніше Секей виявив значно простіше доведення, що використовує нерівність числа схрещень для графів[2] (див. нижче).

Теорема Семереді — Троттера має кілька наслідків, серед яких теорема Бека^[en] в геометрії інцидентності.

Доведення першого формулювання

Ми можемо відкинути прямі, що містять дві і менше точок, оскільки вони можуть дати максимум 2m інциденцій. Отже, можна вважати, що будь-яка пряма містить принаймні три точки.

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

${\displaystyle e=O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right).}$

Розглянемо тепер граф, утворений n точками як вершинами і e відрізками як реберами. Оскільки кожен відрізок лежить на якійсь із m прямих і дві прямі перетинаються максимум в одній точці, число схрещень цього графа не перевищує m^2. З нерівності числа схрещень робимо висновок, що або e ≤ 7.5n або m^2 ≥ e^3 / 33.75n^2. В будь-якому випадку e ≤ 3.24(nm)^2/3 + 7.5n і ми маємо необхідну межу

${\displaystyle e=O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right).}$

Доведення другого формулювання

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

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

${\displaystyle mk=O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right),}$

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

Оптимальність

Якщо не зважати на сталі множники, межу числа інциденцій Семереді — Троттера не можна покращити. Щоб це побачити, розглянемо для будь-якого додатного цілого числа N ∈ Z^+ множину точок цілісної ґрати

${\displaystyle P=\left\{(a,b)\in \mathbf {Z} ^{2}\ :\ 1\leq a\leq N;1\leq b\leq 2N^{2}\right\},}$

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

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

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

Узагальнення для R^d

Узагальнення цього результату для довільної розмірності R^d знайшли Агавал та Аронов[4]. Якщо дано множину S, що містить n точок, і множину H, що містить m гіперплощин, число інциденцій точок із S і гіперплощин із H обмежено зверху числом

${\displaystyle O\left(m^{\frac {2}{3}}n^{\frac {d}{3}}+n^{d-1}\right).}$

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

${\displaystyle O\left({\frac {n^{d}}{k^{3}}}+{\frac {n^{d-1}}{k}}\right).}$

Побудова Едельбруннера показує, що межа асимптотично оптимальна[5].

Шоймоші та Тао отримали майже точну верхню межу для числа інциденцій між точками та алгебричними многовидами в просторах високої розмірності. У доведенні вони використали теорему про бутерброд[6].

Програми

Теорема Семереді — Троттера знаходить багато застосувань у адитивній[7][8][9] та арифметичній комбінаториці (наприклад, для доведення теореми сум-добутків[10]).

Примітки

1. Szemerédi, Trotter, 1983, с. 381–392.
2. Székely, 1997, с. 353–358.
3. Tao, 2011.
4. Agarwal, Aronov, 1992, с. 359–369.
5. Edelsbrunner, 1987.
6. Solymosi, Tao, 2012.
7. Tomasz Schoen, Ilya Shkredov, «On Sumsets of Convex Sets»
8. A. Iosevich, S. Konyagin, M. Rudnev, and V. Ten, «On combinatorial complexity of convex sequences», July 19, 2004
9. Elekes, Nathanson, Ruzsa, «Convexity and sumsets» (PDF). Архів оригіналу (PDF) за 12 червня 2018. Процитовано 19 листопада 2018.
10. G. Elekes, On the number of sums and products, Acta Arith. 81 (1997), 365—367.

Література

• Endre Szemerédi, William T. Trotter. Extremal problems in discrete geometry // Combinatorica. — 1983. — Т. 3, вип. 3–4. — С. 381–392. — DOI:10.1007/BF02579194.
• László A. Székely. Crossing numbers and hard Erdős problems in discrete geometry // Combinatorics, Probability and Computing. — 1997. — Т. 6, вип. 3. — С. 353–358. — DOI:10.1017/S0963548397002976.
• Terence Tao. An incidence theorem in higher dimensions. — 2011. Процитовано 26 серпня 2012.
• Pankaj Agarwal, Boris Aronov. Counting facets and incidences // Discrete and Computational Geometry. — Springer, 1992. — Т. 7, вип. 1. — С. 359–369. — DOI:10.1007/BF02187848.
• Herbert Edelsbrunner. 6.5 Lower bounds for many cells // Algorithms in Combinatorial Geometry. — Springer-Verlag, 1987. — ISBN 3-540-13722-X.
• J. Solymosi, Terence Tao. An incidence theorem in higher dimensions // Discrete and Computational Geometry. — 2012. — Т. 48, вип. 2. — DOI:10.1007/s00454-012-9420-x.

Додаткова література

• Фёдор Нилов, Александр Полянский, Никита Полянский,. 26-я летняя конференция международного математического Турнира городов (02.08.2014-11.08.2014). — Калининград-Ушаково, 2014.