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

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

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

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

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

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

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

Приложения

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

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

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

Сначала дадим предварительную оценку — для любого графа 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 . Таким образом, E [cr _H ] = p ⁴ cr( G ) и мы получаем

${\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 .

Вариации

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

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

Примечания

Литература