Теорема Семереди — Троттера — результат комбинаторной геометрии . Теорема утверждает, что если даны 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).}$

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

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

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

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

Если прямая содержит 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 ² . Из неравенства числа пересечений мы заключаем, что либо e ≤ 7.5 n , либо m ² ≥ e ³ / 33.75 n ² . В любом случае e ≤ 3.24( nm ) ^2/3 + 7.5 n и мы получаем требуемую границу

${\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}}$ , что соответствует верхней границе .

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

Обобщение этого результата для произвольной размерности R ^d было найдено Агавалом и Ароновым . Если дано множество 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).}$

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

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

Приложения

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

Примечания

Литература

• Endre Szemerédi, William T. Trotter. Extremal problems in discrete geometry // Combinatorica. — 1983. — Т. 3 , вып. 3–4 . — С. 381–392 . — doi : .
• László A. Székely. Crossing numbers and hard Erdős problems in discrete geometry // . — 1997. — Т. 6 , вып. 3 . — С. 353–358 . — doi : .
• Terence Tao. An incidence theorem in higher dimensions. — 2011.
• Pankaj Agarwal, Boris Aronov. Counting facets and incidences // . — Springer, 1992. — Т. 7 , вып. 1 . — С. 359–369 . — doi : .
• Herbert Edelsbrunner. 6.5 Lower bounds for many cells // . — Springer-Verlag, 1987. — ISBN 3-540-13722-X .
• J. Solymosi, Terence Tao. An incidence theorem in higher dimensions // . — 2012. — Т. 48 , вып. 2 . — doi : .

Дополнительная литература

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