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

Ограничение на число инциденций между точками и прямыми на плоскости

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

$${\displaystyle O\left(n^{2/3}m^{2/3}+n+m\right).}$$

Эту границу нельзя улучшить, за исключением случаев использования неявных констант.

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

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

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

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

Теорема Семереди–Троттера имеет ряд следствий, включая теорему Бека в геометрии инцидентности и задачу суммы-произведения Эрдёша–Семереди в аддитивной комбинаторике .

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

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

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

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

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

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

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

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

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

$${\displaystyle mk=O\left(n^{2/3}m^{2/3}+n+m\right),}$$

и поэтому по крайней мере одно из утверждений , или верно. Третья возможность исключается, поскольку k предполагалось большим, поэтому у нас остаются первые два. Но в любом из этих двух случаев некоторая элементарная алгебра даст желаемую границу. ${\displaystyle mk=O(n^{2/3}m^{2/3}),mk=O(n)}$ ${\displaystyle mk=O(m)}$ ${\displaystyle m=O(n^{2}/k^{3}+n/k)}$

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

За исключением своей константы, граница инцидентности Семереди–Троттера не может быть улучшена. Чтобы увидеть это, рассмотрим для любого положительного целого числа набор точек на целочисленной решетке ${\displaystyle N\in \mathbb {N} }$

$${\displaystyle P=\left\{(a,b)\in \mathbb {Z} ^{2}\ :\ 1\leq a\leq N;1\leq b\leq 2N^{2}\right\},}$$

и набор линий

$${\displaystyle L=\left\{(x,mx+b)\ :\ m,b\in \mathbb {Z} ;1\leq m\leq N;1\leq b\leq N^{2}\right\}.}$$

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

Обобщение к R d {\displaystyle \mathbb {R} ^{d}}

Одно обобщение этого результата на произвольную размерность, было найдено Агарвалом и Ароновым. ^[8] Если задано множество из n точек, S , и множество из m гиперплоскостей, H , каждая из которых охватывается S , то число инцидентностей между S и H ограничено сверху величиной ${\displaystyle \mathbb {R} ^{d}}$

$${\displaystyle O\left(m^{2/3}n^{d/3}+n^{d-1}\right),}$$

при условии . Эквивалентно, число гиперплоскостей в H, содержащих k или более точек, ограничено сверху ${\displaystyle n^{d-2}<m<n^{d}}$

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

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

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

В C 2 {\displaystyle \mathbb {C} ^{2}}

Многие доказательства теоремы Семереди–Троттера в решающей степени опираются на топологию евклидова пространства , поэтому их нелегко распространить на другие области . Например, оригинальное доказательство Семереди и Троттера; доказательство полиномиального разбиения и доказательство числа пересечений не распространяются на комплексную плоскость . ${\displaystyle \mathbb {R} }$

Тот успешно обобщил оригинальное доказательство Семереди и Троттера на комплексную плоскость, введя дополнительные идеи. ^[11] Этот результат был также получен независимо и другим методом Залем. ^[12] Неявная константа в оценке не является той же самой в комплексных числах : в доказательстве Тота константу можно принять равной ; константа не является явной в доказательстве Заля. ${\displaystyle \mathbb {C} ^{2}}$ ${\displaystyle 10^{60}}$

Когда множество точек является декартовым произведением , Солимози и Тардос показывают, что граница Семереди-Троттера верна, используя гораздо более простое рассуждение. ^[13]

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

Пусть будет поле . ${\displaystyle \mathbb {F} }$

Граница Семереди-Троттера в общем случае невозможна из-за следующего примера, приведенного здесь в : пусть будет множеством всех точек, а пусть будет множеством всех прямых на плоскости. Поскольку каждая прямая содержит точки, есть инцидентности. С другой стороны, граница Семереди-Троттера дала бы инцидентности. Этот пример показывает, что тривиальная, комбинаторная граница инцидентности является плотной. ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle {\mathcal {P}}=\mathbb {F} _{p}\times \mathbb {F} _{p}}$ ${\displaystyle p^{2}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle p^{2}}$ ${\displaystyle p}$ ${\displaystyle p^{3}}$ ${\displaystyle O((p^{2})^{2/3}(p^{2})^{2/3}+p^{2})=O(p^{8/3})}$

Бургейн , Кац и Тао ^[14] показывают, что если исключить этот пример, то можно достичь границы инцидентности, которая является улучшением тривиальной границы.

Границы инцидентности над конечными полями бывают двух типов: (i) когда по крайней мере один из множества точек или линий является «большим» с точки зрения характеристики поля; (ii) как множество точек, так и множество линий являются «малыми» с точки зрения характеристики.

Границы большого набора случаев

Пусть будет нечетной степенью простого числа . Тогда Винь ^[15] показал, что число инцидентностей между точками и прямыми в не более ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle \mathbb {F} _{q}^{2}}$

$${\displaystyle {\frac {nm}{q}}+{\sqrt {qnm}}.}$$

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

Малые установленные границы инцидентности

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

$${\displaystyle O\left(m^{11/15}n^{11/15}\right)}$$

при условии в положительной характеристике. (В поле характеристики ноль это условие не является необходимым.) Эта граница лучше тривиальной оценки инцидентности, когда . ${\displaystyle m^{-2}n^{13}\leq p^{15}}$ ${\displaystyle m^{7/8}<n<m^{8/7}}$

Если множество точек является декартовым произведением, то они показывают улучшенную границу инцидентности: пусть будет конечным множеством точек с и пусть будет множеством прямых на плоскости. Предположим, что и в положительной характеристике, что . Тогда число инцидентностей между и равно ${\displaystyle {\mathcal {P}}=A\times B\subseteq \mathbb {F} ^{2}}$ ${\displaystyle |A|\leq |B|}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle |A||B|^{2}\leq |{\mathcal {L}}|^{3}}$ ${\displaystyle |A||{\mathcal {L}}|\leq p^{2}}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle {\mathcal {L}}}$

$${\displaystyle O\left(|A|^{3/4}|B|^{1/2}|{\mathcal {L}}|^{3/4}+|{\mathcal {L}}|\right).}$$

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

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

Ссылки

1. Пач, Янош ; Радойчич, Радош; Тардос, Габор ; Тот, Геза (2006). «Улучшение леммы о пересечении путем поиска большего количества пересечений в разреженных графах». Дискретная и вычислительная геометрия . 36 (4): 527–552. дои : 10.1007/s00454-006-1264-9 .
2. Акерман, Эял (декабрь 2019 г.). «О топологических графах с максимум четырьмя пересечениями на ребро». Computational Geometry . 85 : 101574. arXiv : 1509.01932 . doi :10.1016/j.comgeo.2019.101574. ISSN  0925-7721. S2CID  16847443.
3. Пах, Янош ; Тот, Геза (1997). «Графики, построенные с небольшим количеством пересечений на ребре». Комбинаторика . 17 (3): 427–439. CiteSeerX 10.1.1.47.4690 . дои : 10.1007/BF01215922 . S2CID  20480170. 
4. Семереди, Эндре ; Троттер, Уильям Т. (1983). «Экстремальные задачи в дискретной геометрии». Combinatorica . 3 (3–4): 381–392. doi : 10.1007/BF02579194 . MR  0729791. S2CID  1750834.
5. Семереди, Эндре ; Троттер, Уильям Т. (1983). «Комбинаторное различие между евклидовой и проективной плоскостями» (PDF) . Европейский журнал комбинаторики . 4 (4): 385–394. doi : 10.1016/S0195-6698(83)80036-5 .
6. Секели, Ласло А. (1997). «Числа пересечения и сложные задачи Эрдёша в дискретной геометрии». Комбинаторика, теория вероятностей и вычисления . 6 (3): 353–358. CiteSeerX 10.1.1.125.1484 . дои : 10.1017/S0963548397002976. MR  1464571. S2CID  36602807. 
7. Теренс Тао (17 марта 2011 г.). "Теорема инцидентности в высших измерениях" . Получено 26 августа 2012 г.
8. Агарвал, Панкадж ; Аронов, Борис (1992). «Подсчет граней и инцидентностей». Дискретная и вычислительная геометрия . 7 (1): 359–369. doi : 10.1007/BF02187848 .
9. Эдельсбруннер, Герберт (1987). "6.5 Нижние границы для многих ячеек". Алгоритмы в комбинаторной геометрии . Springer-Verlag. ISBN 978-3-540-13722-1.
10. Solymosi, József ; Tao, Terence (сентябрь 2012 г.). «Теорема инцидентности в высших измерениях». Дискретная и вычислительная геометрия . 48 (2): 255–280. arXiv : 1103.2926 . doi : 10.1007/s00454-012-9420-x . MR  2946447. S2CID  17830766.
11. Тот, Чаба Д. (2015). «Теорема Семереди-Троттера в комплексной плоскости». Комбинаторика . 35 (1): 95–126. arXiv : math/0305283 . дои : 10.1007/s00493-014-2686-2 . S2CID  13237229.
12. Заль, Джошуа (2015). «Теорема типа Семереди-Троттера в ℝ4». Дискретная и вычислительная геометрия . 54 (3): 513–572. arXiv : 1203.4600 . дои : 10.1007/s00454-015-9717-7 . S2CID  16610999.
13. Солимоси, Йожеф; Тардос, Габор (2007). «О числе k-богатых преобразований». Труды двадцать третьего ежегодного симпозиума по вычислительной геометрии - SCG '07 . SCG '07. Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 227–231. doi :10.1145/1247069.1247111. ISBN 978-1-59593-705-6. S2CID  15928844.
14. Бургейн, Жан; Кац, Нетс; Тао, Теренс (2004-02-01). «Оценка суммы-произведения в конечных полях и ее применение». Геометрический и функциональный анализ . 14 (1): 27–57. arXiv : math/0301343 . doi : 10.1007/s00039-004-0451-1 . ISSN  1016-443X. S2CID  14097626.
15. Винь, Ле Ань (ноябрь 2011 г.). «Теорема типа Семереди–Троттера и оценка суммы-произведения в конечных полях». European Journal of Combinatorics . 32 (8): 1177–1181. arXiv : 0711.4427 . doi : 10.1016/j.ejc.2011.06.008 . ISSN  0195-6698. S2CID  1956316.
16. Стивенс, Софи; де Зеув, Франк (2017-08-03). «Улучшенная граница инцидентности точки и прямой над произвольными полями». Бюллетень Лондонского математического общества . 49 (5): 842–858. arXiv : 1609.06284 . doi :10.1112/blms.12077. ISSN  0024-6093. S2CID  119635655.
17. Руднев, Миша; Шкредов, Илья Д. (июль 2022 г.). «О скорости роста в SL_2(F_p), аффинной группе и импликациях типа суммы-произведения». Mathematika . 68 (3): 738–783. arXiv : 1812.01671 . doi :10.1112/mtk.12120. S2CID  248710290.