Пересечение числового неравенства

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

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

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

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

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

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

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

Приложения

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

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

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

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

$\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. содержит По предварительному неравенству числа пересечений имеем

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

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

$\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 ² е . Наконец, каждое пересечение диаграммы G имеет вероятность p ⁴ остаться в H , поскольку каждое пересечение включает четыре вершины. Чтобы убедиться в этом, рассмотрим диаграмму G с пересечениями cr( G ) . Мы можем считать, что любые два ребра на этой диаграмме с общей вершиной не пересекаются, иначе мы могли бы поменять местами пересекающиеся части двух ребер и уменьшить число пересечений на единицу. Таким образом, каждое пересечение на этой диаграмме включает в себя четыре различные вершины G. графа Следовательно, E [cr _H ] = p ⁴ cr( G ), и мы имеем

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

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

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

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

Вариации

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

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

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

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