Введение

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

Это ограничение нельзя улучшить, за исключением имплицитных констант. Что касается этих констант, Янош Пач, Радош Радоичич, Габор Тардош и Геза Тот показали, что верхняя граница равна . С тех пор известны лучшие константы благодаря улучшенным константам в лемме о пересечениях; текущее лучшее значение равно 2,44. С другой стороны, Пач и Тот показали, что утверждение неверно, если заменить коэффициент 2,5 на 0,42. Эквивалентная формулировка теоремы следующая: для заданных n точек и целого числа k ≥ 2, число прямых, проходящих хотя бы через k точек, равно

Первоначальное доказательство Эндре Сземереди и Уильяма Троттера было несколько сложным, использовавшим комбинаторный метод, известный как декомпозиция на ячейки. Позже Ласло Секели обнаружил гораздо более простое доказательство, использующее неравенство о числе пересечений для графов. (См. ниже.) Теорема Сземереди — Троттера имеет ряд следствий, включая теорему Бека в инцидентной геометрии и проблему суммы-произведения Эрдоша — Сземереди в аддитивной комбинаторике.

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

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

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

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

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

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

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

Обобщение на

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

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

Построение, предложенное Эдельсбруннером, показывает, что эта граница асимптотически оптимальна. Йозеф Солимоси и Теренс Тао получили почти точные верхние оценки для числа инциденций между точками и алгебраическими многообразиями в более высоких размерностях, когда точки и многообразия удовлетворяют "определенным аксиомам, близким к свойствам прямой". Их доказательство использует теорему о полиномиальном сэндвиче.

В

Многие доказательства теоремы Семереди — Троттера над вещественными числами в решающей степени опираются на топологию евклидова пространства и поэтому нелегко обобщаются на другие поля. Например, оригинальное доказательство Семереди и Троттера, доказательство полиномиального разбиения и доказательство числа пересечений не распространяются на комплексную плоскость. Тот успешно обобщил оригинальное доказательство Семереди и Троттера на комплексную плоскость, внедрив дополнительные идеи. Этот результат также был получен независимо и другим методом Залем. Неявная константа в оценке различна для комплексных чисел: в доказательстве Тота константу можно взять равной ; в доказательстве Заля константа не является явной. Когда множество точек является декартовым произведением, Соломоши и Тардош показывают, что оценка Семереди — Троттера справедлива, используя гораздо более простой аргумент.

В конечных полях

Пусть будет поле. Ограничение Семереди — Троттера в общем случае невозможно из-за следующего примера, описанного здесь: пусть — множество всех точек, а — множество всех прямых на плоскости. Поскольку каждая прямая содержит точек, количество инцидентностей равно . С другой стороны, ограничение Семереди — Троттера дало бы инцидентностей. Этот пример показывает, что тривиальное комбинаторное ограничение на количество инцидентностей является точным. Бургейн, Кац и Тао показали, что если исключить этот пример, то можно получить ограничение на количество инцидентностей, которое является улучшением тривиального ограничения. Ограничения на количество инцидентностей над конечными полями бывают двух типов: (i) когда хотя бы одно из множеств точек или прямых является "большим" по отношению к характеристике поля; (ii) когда оба множества, точек и прямых, являются "малыми" по отношению к характеристике.

Большие пределы частоты

Пусть q — нечетная степень простого числа. Тогда Винх показал, что число инциденций между q точками и q линиями в PG(2, q) не превышает q².

Обратите внимание, что в этой оценке нет неявной константы.

Малые пределы частоты

Пусть будет поле характеристики $p$. Стивенс и де Зеу показывают, что число инциденций между $n$ точками и $m$ линиями в $\mathbb{F}_p^2$ равно

при условии $n, m \le p$ в положительной характеристике. (В поле характеристики ноль это условие не требуется.) Эта граница лучше, чем тривиальная оценка числа инциденций, когда $n, m > p$. Если множество точек является декартовым произведением, то они показывают улучшенную границу числа инциденций: пусть $P$ — конечное множество точек с $|P| = n$ и $L$ — множество линий в плоскости. Предположим, что $|L| = m$ и в положительной характеристике, что $n, m \le p$. Тогда число инциденций между $P$ и $L$ равно

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