Теорема Семереди – Троттера. - Szemerédi–Trotter theorem

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

${ displaystyle O left (п ^ { frac {2} {3}} m ^ { frac {2} {3}} + n + m right),}$

эту границу нельзя улучшить, кроме как с точки зрения неявных констант. Что касается неявных констант, то это было показано Янош Пах, Радош Радойчич, Габор Тардос и Геза Тот^[1] что верхняя граница ${ displaystyle 2.5n ^ {2/3} m ^ {2/3} + n + m}$ держит. (С тех пор известны лучшие константы из-за лучшего пересечения констант леммы; текущее наилучшее значение - 2,44). С другой стороны, Пах и Тот показали, что утверждение не выполняется, если заменить коэффициент 2,5 на 0,42.^[2]

Эквивалентная формулировка теоремы следующая. Данный п точки и целое число k ≥ 2, количество строк, которые проходят не менее k точек

${ displaystyle O left ({ frac {n ^ {2}} {k ^ {3}}} + { frac {n} {k}} right).}$

Оригинальное доказательство Эндре Семереди и Уильям Т. Троттер было несколько сложно, с использованием комбинаторной техники, известной как разложение клеток.^[3][4] Позже Ласло Секели обнаружил гораздо более простое доказательство, используя пересечение числового неравенства за графики.^[5] (См. ниже.)

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

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

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

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

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

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

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

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

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

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

${ 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 м = О (п ^ {2} / к ^ {3} + п / к)}$ по желанию.

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

За исключением константы, граница инцидентности Семереди – Троттера не может быть улучшена. Чтобы увидеть это, рассмотрим любое положительное целое число 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} верно}.}$

Ясно, ${ displaystyle | P | = 2N ^ {3}}$ и ${ Displaystyle | L | = N ^ {3}}$. Поскольку каждая линия относится к N баллов (т.е. один раз за каждую ${ Displaystyle х в {1, cdots, N }}$), количество случаев ${ displaystyle N ^ {4}}$ что соответствует верхней границе.^[6]

Обобщение на р^d

Одно обобщение этого результата на произвольную размерность, р^d, нашли Агарвал и Аронов.^[7] Учитывая набор п точки, S, а набор м гиперплоскости, ЧАС, каждая из которых покрыта S, количество случаев между S и ЧАС ограничен сверху

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

Эквивалентно количество гиперплоскостей в ЧАС содержащий k или более точек ограничено сверху

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

Конструкция Эдельсбруннера показывает, что эта граница является асимптотически оптимальной.^[8]

Йожеф Солимоши и Теренс Тао получены около точных верхних оценок числа инцидентностей между точками и алгебраическими многообразиями в более высоких размерностях, когда точки и многообразия удовлетворяют «некоторым аксиомам типа псевдолинейных линий». В их доказательстве используется Полиномиальная теорема о сэндвиче Хэма.^[9]

Аналоги по другим отраслям

Был определенный интерес к доказательству аналогов теоремы Семереди – Троттера в плоскостях над полями, отличными от р. Все известные доказательства теоремы Семереди – Троттера над р в решающей степени полагаются на топологию евклидова пространства, поэтому их нелегко распространить на другие области. Тем не менее были получены следующие результаты:

• Тот успешно обобщил исходное доказательство Семереди и Троттера на комплексную плоскость. C² путем внесения дополнительных идей.^[10] Этот результат также был получен Залом независимо и другим методом.^[11]

Рекомендации