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

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

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

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

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

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

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

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

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

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

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

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

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

$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 інциденцій, а тоді за першим варіантом теореми Семереді — Троттера маємо

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Програми

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

Література

• 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.