Теорема Семереди – Троттера - математический результат в области комбинаторной геометрии . Он утверждает, что для данных n точек и m прямых на евклидовой плоскости количество инцидентов ( т. Е. Количество пар точка-прямая, таких, что точка лежит на прямой) равно
эту границу нельзя улучшить, кроме как с точки зрения неявных констант. Что касается неявных констант, то Янош Пах , Радош Радойчич, Габор Тардос и Геза Тот [1] показали, что верхняя оценкадержит. (С тех пор известны лучшие константы из-за лучшего пересечения констант леммы; текущее наилучшее значение - 2,44.) С другой стороны, Пах и Тот показали, что утверждение не выполняется, если заменить коэффициент 2,5 на 0,42. [2]
Эквивалентная формулировка теоремы следующая. Для n точек и целого числа k ≥ 2 количество прямых, проходящих не менее чем через k точек, равно
Первоначальное доказательство Эндре Семереди и Уильяма Т. Троттера было несколько сложным с использованием комбинаторной техники, известной как разложение клеток . [3] [4] Позже Ласло Секели обнаружил гораздо более простое доказательство, использующее неравенство числа пересечений для графов . [5] (См. Ниже.)
Теорема Семереди – Троттера имеет ряд следствий, включая теорему Бека в геометрии инцидентности .
Доказательство первой формулировки
Мы можем отбросить строки, содержащие две или меньше точек, так как они могут давать не более 2 m инцидентов в общее количество. Таким образом, мы можем считать, что каждая линия содержит не менее трех точек.
Если линия содержит k точек, тогда она будет содержать k - 1 отрезков, которые соединяют две последовательные точки вдоль линии. Поскольку k ≥ 3 после отбрасывания двухточечных прямых, следует, что k - 1 ≥ k / 2 , поэтому количество этих отрезков на каждой прямой составляет по крайней мере половину числа инцидентностей на этой прямой. Суммируя по всем линиям, количество этих сегментов снова составляет, по крайней мере, половину общего количества случаев. Таким образом, если e обозначает количество таких отрезков прямой, достаточно показать, что
Теперь рассмотрим граф, образованный n точками как вершинами и e отрезками прямых как ребра. Поскольку каждый отрезок прямой лежит на одной из m прямых, а любые две прямые пересекаются не более чем в одной точке, число пересечений этого графика - не более чем количество точек пересечения двух прямых, которое не более m ( m - 1). / 2 . Неравенство числа пересечений следует , что либо е ≤ 7,5 л , или что м ( м - 1) / 2 ≥ е 3 / 33,75 л 2 . В любом случае e ≤ 3,24 ( нм ) 2/3 + 7,5 n , что дает желаемую оценку
Доказательство второй формулировки
Поскольку каждая пара точек может быть соединена не более чем одной линией, может быть не более n ( n - 1) / 2 прямых, которые могут соединяться в k или более точках, поскольку k ≥ 2 . Эта оценка докажет теорему, когда k мало (например, если k ≤ C для некоторой абсолютной постоянной C ). Таким образом, мы должны рассматривать только случай , когда к велико, скажем к ≥ C .
Предположим, что есть m прямых, каждая из которых содержит не менее k точек. Эти прямые порождают не менее mk инцидентностей, и поэтому согласно первой формулировке теоремы Семереди – Троттера имеем
и так хотя бы одно из утверждений , или же правда. Третья возможность исключена, так как k предполагалось большим, поэтому мы остались с первыми двумя. Но в любом из этих двух случаев некоторая элементарная алгебра даст оценку по желанию.
Оптимальность
За исключением константы, граница инцидентности Семереди – Троттера не может быть улучшена. Чтобы убедиться в этом, рассмотрим для любого натурального числа N ∈ Z + набор точек на целочисленной решетке
и набор линий
Четко, а также . Поскольку каждая линия инцидентна N точкам (т. Е. По одному разу для каждой), количество случаев что соответствует верхней границе. [6]
Обобщение на R d
Одно обобщение этого результата на произвольную размерность R d было найдено Агарвалом и Ароновым. [7] Для набора из n точек S и набора из m гиперплоскостей H , каждая из которых натянута на S , количество инцидентов между S и H ограничено сверху величиной
Эквивалентно, количество гиперплоскостей в H, содержащих k или более точек, ограничено сверху величиной
Конструкция Эдельсбруннера показывает, что эта граница является асимптотически оптимальной. [8]
Йожеф Солимози и Теренс Тао получили почти точные верхние границы для числа инцидентностей между точками и алгебраическими многообразиями в высших измерениях, когда точки и многообразия удовлетворяют «некоторым аксиомам типа псевдолинейных линий». В их доказательстве используется полиномиальная теорема о бутерброде Хэма . [9]
Аналоги по другим отраслям
Там был некоторый интерес доказать аналоги к теореме Семереди-Trotter в плоскостях по сравнению с другими , чем полем R . Все известные доказательства теоремы Семереди – Троттера над R решающим образом опираются на топологию евклидова пространства, поэтому их нелегко распространить на другие области. Тем не менее были получены следующие результаты:
Рекомендации
- ^ Пах, Янош ; Радойчич, Радош; Тардос, Габор ; Тот, Геза (2006). «Улучшение леммы о пересечениях путем поиска большего количества пересечений в разреженных графах» . Дискретная и вычислительная геометрия . 36 (4): 527–552. DOI : 10.1007 / s00454-006-1264-9 .
- ^ Пах, Янош ; Тот, Геза (1997). «Графики нарисованы с небольшим количеством пересечений на ребро». Combinatorica . 17 (3): 427–439. CiteSeerX 10.1.1.47.4690 . DOI : 10.1007 / BF01215922 .
- ^ Семереди, Эндре ; Троттер, Уильям Т. (1983). «Экстремальные задачи дискретной геометрии». Combinatorica . 3 (3–4): 381–392. DOI : 10.1007 / BF02579194 . Руководство по ремонту 0729791 .
- ^ Семереди, Эндре ; Троттер, Уильям Т. (1983). «Комбинаторное различие между евклидовой и проективной плоскостями» (PDF) . Европейский журнал комбинаторики . 4 (4): 385–394. DOI : 10.1016 / S0195-6698 (83) 80036-5 .
- ^ Секели, Ласло А. (1997). «Пересечение чисел и трудные задачи Эрдеша в дискретной геометрии». Комбинаторика, теория вероятностей и вычисления . 6 (3): 353–358. CiteSeerX 10.1.1.125.1484 . DOI : 10.1017 / S0963548397002976 . Руководство по ремонту 1464571 .
- ^ Теренс Тао (17 марта 2011 г.). «Теорема инцидентности в высших измерениях» . Проверено 26 августа 2012 года .
- ^ Агарвал, Панкадж ; Аронов, Борис (1992). «Подсчет граней и падений» . Дискретная и вычислительная геометрия . 7 (1): 359–369. DOI : 10.1007 / BF02187848 .
- ^ Эдельсбруннер, Герберт (1987). «6.5 Нижние границы для многих ячеек». Алгоритмы комбинаторной геометрии . Springer-Verlag. ISBN 978-3-540-13722-1.
- ^ Солимози, Йожеф ; Тао, Теренс (сентябрь 2012 г.). «Теорема инцидентности в высших измерениях». Дискретная и вычислительная геометрия . 48 (2): 255–280. arXiv : 1103.2926 . DOI : 10.1007 / s00454-012-9420-х . Руководство по ремонту 2946447 .
- ^ Тот, Чаба Д. (2015). "Теорема Семереди-Троттера на комплексной плоскости". Combinatorica . 35 (1): 95–126. arXiv : math / 0305283 . DOI : 10.1007 / s00493-014-2686-2 .
- ^ Захл, Джошуа (2015). "Теорема типа Семереди-Троттера в §4". Дискретная и вычислительная геометрия . 54 (3): 513–572. arXiv : 1203.4600 . DOI : 10.1007 / s00454-015-9717-7 .