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

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

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

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

Эквивалентная формулировка теоремы следующая. Если задано Шаблон:Mvar точек и целое число Шаблон:Math, число прямых, проходящих по меньшей мере через Шаблон:Mvar точек, равно

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

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

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

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

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

Если прямая содержит Шаблон:Mvar точек, то она содержит Шаблон:Math отрезков, соединяющих две из Шаблон:Mvar точек. В частности, прямая будет содержать по меньшей мере k/2 таких отрезков, поскольку мы предположили Шаблон:Math. Складывая все такие инциденции по всем Шаблон:Mvar прямым, мы получим, что число отрезков, полученных таким образом, по меньшей мере равно половине числа всех инциденций. Если мы обозначим через Шаблон:Mvar число таких отрезков, достаточно показать, что

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

Рассмотрим теперь граф, образованный Шаблон:Mvar точками в качестве вершин и e отрезками в качестве рёбер. Поскольку каждый отрезок лежит на какой-либо из Шаблон:Mvar прямых и две прямые пересекаются максимум в одной точке, число пересечений этого графа не превосходит Шаблон:Math. Из неравенства числа пересечений мы заключаем, что либо Шаблон:Math, либо Шаблон:Math. В любом случае Шаблон:Math и мы получаем требуемую границу

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

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

Поскольку любая пара точек может быть соединена максимум одной прямой, может быть максимум Шаблон:Math l прямых, которые могут соединять Шаблон:Mvar или более точек, поскольку Шаблон:Math. Эта граница доказывает теорему при малых Шаблон:Mvar (например, если Шаблон:Math для некоторой абсолютной константы Шаблон:Mvar). Таким образом, имеет смысл рассматривать только случаи, когда Шаблон:Mvar велико, скажем, Шаблон:Math.

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

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

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

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

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

$P=\{(a,b)\in {𝐙}^2:1\le a\le N;1\le b\le 2N^2\},$

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

$L=\{(x,mx+b):m,b\in 𝐙;1\le m\le N;1\le b\le N^2\}.$

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

Обобщение для Шаблон:Math

Обобщение этого результата для произвольной размерностиШаблон:Math было найдено Агавалом и АроновымШаблон:Sfn. Если дано множество Шаблон:Mvar, содержащее Шаблон:Mvar точек, и множество Шаблон:Mvar, содержащее Шаблон:Mvar гиперплоскостей, число инциденций точек из Шаблон:Mvar и гиперплоскостей из Шаблон:Mvar ограничено сверху числом

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

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

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

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

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

Приложения

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья

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

• Шаблон:Статья