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

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

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

Утверждение и история

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

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

Константа 29 является лучшей на настоящее время и принадлежит Акерману. О более ранних результатах с более слабыми константами смотрите статьи Паха и Тота, Паха Радожича, Тардоса и Тота.

Константа 7 может быть понижена до 4, но ценой этого константа 29 заменяется худшей константой 64.

Приложения

Причина, побудившая Лейтона к изучению числа пересечений, заключалась в приложениях к разработке СБИС.

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

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

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

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

Для доказательства этого представим рисунок графа G, который имеет в точности cr(G) пересечений. Каждое из этих пересечений может быть удалено путём удаления ребра из G. Тогда мы можем найти граф с по меньшей мере e − cr(G) рёбрами и n вершинами, не имеющий пересечений, а потому этот граф планарен. Но из формулы Эйлера мы должны тогда иметь e − cr(G) ≤ 3n, откуда следует требуемое. (Фактически мы имеем e − cr(G) ≤ 3n − 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²e. Наконец, каждое пересечение на рисунке графа G имеет вероятность p⁴ оказаться в графе H, поскольку каждое пересечение требует наличия четырёх вершин. Чтобы это показать, представим рисунок графа G с cr(G) пересечениями. Мы можем допустить, что любые два ребра на этом рисунке с общей вершиной не пересекаются, в противном случае они образуют что-то близкое к букве альфа (см. рисунок) и мы можем обменять местами части дуг до точки пересечения и уменьшить число пересечений. Тогда любое пересечение на рисунке графа имеет четыре различные вершины графа G. Таким образом, E[cr_H] = p⁴cr(G) и мы получаем

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

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

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

Небольшое улучшение этого подхода позволяет заменить 64 на 33.75 для e > 7.5n.

Вариации

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

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