Русская Википедия:Теорема Семереди — Троттера
Теорема Семереди — Троттера — результат комбинаторной геометрии. Теорема утверждает, что если даны Шаблон:Mvar точек и Шаблон:Mvar прямых на плоскости, число инциденций (т.е. число пар точка/прямая, в которых точка лежит на прямой) равно
- <math>O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right ),</math>
и эта граница не может быть улучшена.
Эквивалентная формулировка теоремы следующая. Если задано Шаблон:Mvar точек и целое число Шаблон:Math, число прямых, проходящих по меньшей мере через Шаблон:Mvar точек, равно
- <math>O \left( \frac{n^2}{k^3} + \frac{n}{k} \right ).</math>
Первоначальное доказательство Семереди и Шаблон:Не переведено 5 Шаблон:Sfn было сложным и использовало комбинаторную технику, известную как разделение ячеек. Позднее Секей обнаружил существенно более простое доказательство, использующее неравенство числа пересечений для графов Шаблон:Sfn (см. ниже).
Теорема Семереди – Троттера имеет несколько следствий, включая Шаблон:Не переведено 5 в геометрии инцидентности.
Доказательство первой формулировки
Мы можем отбросить прямые, содержащие две и менее точек, так как они могут дать максимум Шаблон:Math инциденций. Таким образом, мы можем считать, что любая прямая содержит по меньшей мере три точки.
Если прямая содержит Шаблон:Mvar точек, то она содержит Шаблон:Math отрезков, соединяющих две из Шаблон:Mvar точек. В частности, прямая будет содержать по меньшей мере k/2 таких отрезков, поскольку мы предположили Шаблон:Math. Складывая все такие инциденции по всем Шаблон:Mvar прямым, мы получим, что число отрезков, полученных таким образом, по меньшей мере равно половине числа всех инциденций. Если мы обозначим через Шаблон:Mvar число таких отрезков, достаточно показать, что
- <math>e = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right).</math>
Рассмотрим теперь граф, образованный Шаблон:Mvar точками в качестве вершин и e отрезками в качестве рёбер. Поскольку каждый отрезок лежит на какой-либо из Шаблон:Mvar прямых и две прямые пересекаются максимум в одной точке, число пересечений этого графа не превосходит Шаблон:Math. Из неравенства числа пересечений мы заключаем, что либо Шаблон:Math, либо Шаблон:Math. В любом случае Шаблон:Math и мы получаем требуемую границу
- <math>e = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right ).</math>
Доказательство второй формулировки
Поскольку любая пара точек может быть соединена максимум одной прямой, может быть максимум Шаблон:Math l прямых, которые могут соединять Шаблон:Mvar или более точек, поскольку Шаблон:Math. Эта граница доказывает теорему при малых Шаблон:Mvar (например, если Шаблон:Math для некоторой абсолютной константы Шаблон:Mvar). Таким образом, имеет смысл рассматривать только случаи, когда Шаблон:Mvar велико, скажем, Шаблон:Math.
Предположим, что имеется m прямых, каждая из которых содержит по меньшей мере Шаблон:Mvar точек. Эти прямые образуют по меньшей мере Шаблон:Mvar инциденций, а тогда по первому варианту теоремы Семереди – Троттера мы имеем
- <math>mk = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right ),</math>
и по меньшей мере выполняется одно равенство из <math>mk = O( n^{2/3} m^{2/3} ), mk = O(n)</math> или <math>mk = O(m)</math>. Третью возможность отбрасываем, поскольку мы предположили, что Шаблон:Mvar велико, так что остаются два первых. Но в обоих случаях после несложных алгебраических выкладок получим <math>m = O( n^2 / k^3 + n/k )</math>, что и требовалось.
Оптимальность
Если не учитывать постоянные множители, граница инциденций Семереди – Троттера не может быть улучшена. Чтобы это увидеть, рассмотрим для любого положительного целого числа Шаблон:Math множество точек целочисленной решётки
- <math>P = \left \{ (a, b) \in \mathbf{Z}^2 \ : \ 1 \leq a \leq N; 1 \leq b \leq 2N^2 \right \},</math>
и набор прямых
- <math>L = \left \{ (x, mx + b) \ : \ m, b \in \mathbf{Z}; 1 \leq m \leq N; 1 \leq b \leq N^2 \right \}.</math>
Ясно, что <math>|P| = 2N^3</math> и <math>|L| = N^3</math>. Поскольку каждая прямая инцидентна Шаблон:Mvar точкам (т.е. один раз для каждого <math>x \in \{1, \cdots, N\}</math>), число инциденций равно <math>N^4</math>, что соответствует верхней границеШаблон:Sfn.
Обобщение для Шаблон:Math
Обобщение этого результата для произвольной размерностиШаблон:Math было найдено Агавалом и АроновымШаблон:Sfn. Если дано множество Шаблон:Mvar, содержащее Шаблон:Mvar точек, и множество Шаблон:Mvar, содержащее Шаблон:Mvar гиперплоскостей, число инциденций точек из Шаблон:Mvar и гиперплоскостей из Шаблон:Mvar ограничено сверху числом
- <math>O \left (m^{\frac{2}{3}}n^{\frac{d}{3}}+n^{d-1} \right ).</math>
Эквивалентно, число гиперплоскостей из Шаблон:Mvar, содержащих Шаблон:Mvar и более точек, ограничено сверху числом
- <math>O\left( \frac{n^d}{k^3} + \frac{n^{d-1}}{k} \right ).</math>
Построение Эдельбруннера показывает, что граница асимптотически оптимальнаШаблон:Sfn.
Шоймоши и Тао получили почти точную верхнюю границу для числа инциденций между точками и алгебраическими многообразиями в пространствах высокой размерности. Их доказательство использует Шаблон:Не переведено 5Шаблон:Sfn.
Приложения
Теорема Семереди-Троттера находит множество приложений в аддитивной[1][2][3] и арифметической комбинаторике (например, для доказательства теоремы сумм-произведений[4]).
Примечания
Литература
Дополнительная литература
