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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

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

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

Мы можем отбросить прямые, содержащие две и менее точек, так как они могут дать максимум 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 прямых и две прямые пересекаются максимум в одной точке, число пересечений этого графа не превосходит m2. Из неравенства числа пересечений мы заключаем, что либо e ≤ 7.5n, либо m2e3 / 33.75n2. В любом случае 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 (например, если kC для некоторой абсолютной константы C). Таким образом, имеет смысл рассматривать только случаи, когда k велико, скажем, kC.

Предположим, что имеется 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], что и требовалось.

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

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

[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], что соответствует верхней границе[3].

Обобщение для Rd

Обобщение этого результата для произвольной размерностиRd было найдено Агавалом и Ароновым[4]. Если дано множество 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]

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

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

Приложения

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

Примечания

  1. Szemerédi, Trotter, 1983, с. 381–392.
  2. Székely, 1997, с. 353–358.
  3. Tao, 2011.
  4. Agarwal, Aronov, 1992, с. 359–369.
  5. Edelsbrunner, 1987.
  6. Solymosi, Tao, 2012.
  7. Tomasz Schoen, Ilya Shkredov, «On Sumsets of Convex Sets». Дата обращения: 19 ноября 2018. Архивировано 12 июня 2018 года.
  8. A. Iosevich, S. Konyagin, M. Rudnev, and V. Ten, «On combinatorial complexity of convex sequences», July 19, 2004. Дата обращения: 19 ноября 2018. Архивировано 12 июня 2018 года.
  9. Elekes, Nathanson, Ruzsa, «Convexity and sumsets» (недоступная ссылка). Дата обращения: 19 ноября 2018. Архивировано 12 июня 2018 года.
  10. G. Elekes, On the number of sums and products, Acta Arith. 81 (1997), 365–367.. Дата обращения: 19 ноября 2018. Архивировано 7 февраля 2019 года.

Литература

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

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