Неравенство числа пересечений

Рисунки плотных графов имеют много пересечений

В математике рисования графов неравенство числа пересечений или лемма о пересечениях дает нижнюю границу минимального числа пересечений ребер в плоском рисунке заданного графа как функцию числа ребер и вершин графа. Она утверждает, что для графов, где число ребер e достаточно больше числа вершин n , число пересечений по крайней мере пропорционально e ³ / n ² .

Он применяется в проектировании СБИС и комбинаторной геометрии и был открыт независимо друг от друга Аджати , Хваталом , Ньюборном и Семереди ^[1] , а также Лейтоном ^[2] .

Заявление и история

Неравенство числа пересечений утверждает, что для неориентированного простого графа G с n вершинами и e ребрами, такими что e > 7 n , число пересечений cr( G ) подчиняется неравенству

${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.}$

Константа 29 является наиболее известной на сегодняшний день и принадлежит Акерману. ^[3] Более ранние результаты с более слабыми константами см. в работах Pach & Tóth (1997) и Pach et al. (2006). ^{[4] [5]} Константу 7 можно понизить до 4 , но за счет замены 29 на худшую константу 64 .

Важно различать число пересечений cr( G ) и число парных пересечений pair-cr( G ) . Как отметили Пач и Тот (2000), число парных пересечений относится к минимальному числу пар ребер, каждое из которых определяет одно пересечение, тогда как число пересечений просто относится к минимальному числу пересечений. (Это различие необходимо, поскольку некоторые авторы предполагают, что в правильном рисунке никакие два ребра не пересекаются более одного раза.) ^[6] ${\displaystyle {\text{pair-cr}}(G)\leq {\text{cr}}(G)}$

Приложения

Мотивацией Лейтона при изучении чисел пересечения были приложения к проектированию СБИС в теоретической информатике. ^[2]

Позже, Секей (1997) понял, что это неравенство дало очень простые доказательства некоторых важных теорем в геометрии инцидентности . Например, теорема Семереди–Троттера , верхняя граница числа инцидентностей, которые возможны между заданным числом точек и прямых на плоскости, следует из построения графа, вершинами которого являются точки, а ребрами — отрезки прямых между точками инцидентности. Если бы инцидентностей было больше, чем граница Семереди–Троттера, этот граф обязательно имел бы больше пересечений, чем общее число пар прямых, что невозможно. Неравенство также можно использовать для доказательства теоремы Бека , что если конечное множество точек не имеет линейного числа коллинеарных точек, то оно определяет квадратичное число различных прямых. ^[7] Аналогично, Тамал Дей использовал его для доказательства верхних границ геометрических k -множеств . ^[8]

Доказательство

Сначала дадим предварительную оценку: для любого графа G с n вершинами и e ребрами имеем

${\displaystyle \operatorname {cr} (G)\geq e-3n.}$

Чтобы доказать это, рассмотрим диаграмму G , которая имеет ровно cr( G ) пересечений. Каждое из этих пересечений можно удалить, удалив ребро из G . Таким образом, мы можем найти граф с по крайней мере e − cr( G ) ребрами и n вершинами без пересечений, и, таким образом, это планарный граф . Но из формулы Эйлера мы должны тогда иметь e − cr( G ) ≤ 3 n , и утверждение следует. (На самом деле мы имеем e − cr( G ) ≤ 3 n − 6 для n ≥ 3 ).

Чтобы получить фактическое неравенство числа пересечений, мы теперь используем вероятностный аргумент . Мы позволяем 0 < p < 1 быть вероятностным параметром, который будет выбран позже, и строим случайный подграф H графа G , позволяя каждой вершине G лежать в H независимо с вероятностью p и позволяя ребру G лежать в H тогда и только тогда, когда его две вершины были выбраны лежащими в H. Пусть e _H , n _H и cr _H обозначают количество ребер, вершин и пересечений H соответственно. Поскольку H является подграфом G , диаграмма G содержит диаграмму H . По предварительному неравенству числа пересечений мы имеем

${\displaystyle \operatorname {cr} _{H}\geq e_{H}-3n_{H}.}$

Принимая ожидания, получаем

${\displaystyle \mathbf {E} [\operatorname {cr} _{H}]\geq \mathbf {E} [e_{H}]-3\mathbf {E} [n_{H}].}$

Так как каждая из n вершин в G имеет вероятность p нахождения в H , то мы имеем E [ n _H ] = pn . Аналогично, каждое из ребер в G имеет вероятность p ² остаться в H , так как обе конечные точки должны оставаться в H , поэтому E [ e _H ] = p ² e . Наконец, каждое пересечение в диаграмме G имеет вероятность p ⁴ остаться в H , так как каждое пересечение включает четыре вершины. Чтобы увидеть это, рассмотрим диаграмму G с cr( G ) пересечениями. Мы можем предположить, что любые два ребра в этой диаграмме с общей вершиной не пересекаются, в противном случае мы могли бы поменять местами пересекающиеся части двух ребер и уменьшить число пересечений на единицу. Таким образом, каждое пересечение в этой диаграмме включает четыре различные вершины G . Диаграмма, которую мы получили, может быть не оптимальной с точки зрения количества пересечений, но она, очевидно, имеет по крайней мере cr _H пересечений. Следовательно,

${\displaystyle p^{4}\operatorname {cr} (G)\geq \mathbf {E} [\operatorname {cr} _{H}]}$

и у нас есть

${\displaystyle p^{4}\operatorname {cr} (G)\geq p^{2}e-3pn.}$

Теперь, если мы положим p = 4 n / e < 1 (так как мы предположили, что e > 4 n ), то после некоторых алгебраических преобразований получим

${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{64n^{2}}}.}$

Небольшое уточнение этого аргумента позволяет заменить 64 на 33,75 для e > 7,5 n . ^[3]

Вариации

Для графов с обхватом больше 2r и e ≥ 4n Пач , Спенсер и Тот (2000) продемонстрировали улучшение этого неравенства до ^[9]

${\displaystyle \operatorname {cr} (G)\geq c_{r}{\frac {e^{r+2}}{n^{r+1}}}.}$

Адипрасито показал обобщение на более высокие размерности: ^[10] Если — симплициальный комплекс, который кусочно-линейно отображается в , и он имеет -мерные грани и -мерные грани такие, что , то число попарно пересекающихся -мерных граней не менее ${\displaystyle \Delta }$ ${\displaystyle \mathbf {R} ^{2d}}$ ${\displaystyle f_{d}(\Delta )\ \ d}$ ${\displaystyle f_{d-1}(\Delta )\ \ (d-1)}$ ${\displaystyle f_{d}(\Delta )>(d+3)f_{d-1}(\Delta )}$ ${\displaystyle d}$

${\displaystyle {\frac {f_{d}^{d+2}(\Delta )}{(d+3)^{d+2}f_{d-1}^{d+1}(\Delta )}}.}$

Ссылки

1. Ajtai, M. ; Chvátal, V. ; Newborn, MM; Szemerédi, E. (1982), "Crossing-free subgraphs", Теория и практика комбинаторики , North-Holland Mathematics Studies, т. 60, North-Holland, Амстердам, стр. 9–12, MR  0806962.
2. Лейтон, Т. (1983), Проблемы сложности в СБИС , Серия «Основы вычислений», Кембридж, Массачусетс: Издательство MIT.
3. Ackerman, Eyal (2019), «О топологических графах с максимум четырьмя пересечениями на ребро», Computational Geometry , 85 : 101574, 31, arXiv : 1509.01932 , doi : 10.1016/j.comgeo.2019.101574, MR  4010251, S2CID  16847443.
4. Пах, Янош ; Тот, Геза (1997), «Графы, нарисованные с небольшим количеством пересечений на ребро», Combinatorica , 17 (3): 427–439, doi :10.1007/BF01215922, MR  1606052, S2CID  20480170.
5. Pach, János ; Radoičić, Radoš; Tardos, Gábor; Tóth, Géza (2006), «Улучшение леммы о пересечении путем нахождения большего количества пересечений в разреженных графах», Discrete and Computational Geometry , 36 (4): 527–552, doi : 10.1007/s00454-006-1264-9 , MR  2267545.
6. Пах, Янош; Тот, Геза (2000), «Какое же это число пересечения?», Журнал комбинаторной теории, Серия B , 80 (2): 225–246, doi : 10.1006/jctb.2000.1978.
7. Székely, LA (1997), «Пересекающиеся числа и сложные проблемы Эрдёша в дискретной геометрии», Комбинаторика, вероятность и вычисления , 6 (3): 353–358, doi :10.1017/S0963548397002976, MR  1464571, S2CID  36602807.
8. Дей, TK (1998), «Улучшенные оценки для плоских k- множеств и связанных с ними проблем», Дискретная и вычислительная геометрия , 19 (3): 373–382, doi : 10.1007/PL00009354 , MR  1608878.
9. Pach, J. ; Spencer, J. ; Tóth, G. (2000), "Новые границы для чисел пересечений", Discrete and Computational Geometry , 24 (4): 623–644, doi : 10.1007/s004540010011 , MR  1799605.
10. Адипрасито, Карим (2018-12-26), «Комбинаторные теоремы Лефшеца за пределами положительности», arXiv : 1812.10454v3 [math.CO].