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

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

[math]\displaystyle{ O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right ), }[/math]

и эта граница не может быть улучшена.

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

[math]\displaystyle{ O \left( \frac{n^2}{k^3} + \frac{n}{k} \right ). }[/math]

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

Теорема Семереди – Троттера имеет несколько следствий, включая теорему Бека в геометрии инцидентности.

Доказательство первой формулировки

Мы можем отбросить прямые, содержащие две и менее точек, так как они могут дать максимум 2m инциденций. Таким образом, мы можем считать, что любая прямая содержит по меньшей мере три точки.

Если прямая содержит k точек, то она содержит k − 1 отрезков, соединяющих две из n точек. В частности, прямая будет содержать по меньшей мере k/2 таких отрезков, поскольку мы предположили k ≥ 3. Складывая все такие инциденции по всем m прямым, мы получим, что число отрезков, полученных таким образом, по меньшей мере равно половине числа всех инциденций. Если мы обозначим через e число таких отрезков, достаточно показать, что

[math]\displaystyle{ e = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right). }[/math]

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

[math]\displaystyle{ e = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right ). }[/math]

Доказательство второй формулировки

Поскольку любая пара точек может быть соединена максимум одной прямой, может быть максимум n(n − 1)/2 l прямых, которые могут соединять k или более точек, поскольку k ≥ 2. Эта граница доказывает теорему при малых k (например, если k ≤ C для некоторой абсолютной константы C). Таким образом, имеет смысл рассматривать только случаи, когда k велико, скажем, k ≥ C.

Предположим, что имеется m прямых, каждая из которых содержит по меньшей мере k точек. Эти прямые образуют по меньшей мере mk инциденций, а тогда по первому варианту теоремы Семереди – Троттера мы имеем

[math]\displaystyle{ mk = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right ), }[/math]

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

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

Если не учитывать постоянные множители, граница инциденций Семереди – Троттера не может быть улучшена. Чтобы это увидеть, рассмотрим для любого положительного целого числа N ∈ Z⁺ множество точек целочисленной решётки

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

и набор прямых

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

Ясно, что [math]\displaystyle{ |P| = 2N^3 }[/math] и [math]\displaystyle{ |L| = N^3 }[/math]. Поскольку каждая прямая инцидентна N точкам (т.е. один раз для каждого [math]\displaystyle{ x \in \{1, \cdots, N\} }[/math]), число инциденций равно [math]\displaystyle{ N^4 }[/math], что соответствует верхней границе.

Обобщение для R^d

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

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

Эквивалентно, число гиперплоскостей из H, содержащих k и более точек, ограничено сверху числом

[math]\displaystyle{ O\left( \frac{n^d}{k^3} + \frac{n^{d-1}}{k} \right ). }[/math]

Построение Эдельбруннера показывает, что граница асимптотически оптимальна.

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

Приложения

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

Литература

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