Неравенство числа пересечений или лемма о пересечениях даёт нижнюю грань минимального числа пересечений данного графа как функцию от числа рёбер и вершин графа. Лемма утверждает, что для графов, у которых число рёбер достаточно велико по сравнению с числом вершин , число пересечений по меньшей мере пропорционально .
Неравенство имеет приложения при разработке СБИС и в комбинаторной геометрии. Неравенство открыли Аитаи, Хватал, Ньюборн и Семереди и, независимо, Лейтон.
Утверждение и история Неравенство числа пересечений утверждает, что для неориентированного простого графа с вершинами и рёбрами, такого, что , число пересечений в графе удовлетворяет неравенству
Константа является лучшей на настоящее время и принадлежит Акерману. О более ранних результатах с более слабыми константами смотрите статьи Паха и Тота, Паха Радожича, Тардоса и Тота.
Константа может быть понижена до , но ценой этого константа заменяется худшей константой .
Приложения Причина, побудившая Лейтона к изучению числа пересечений, заключалась в приложениях к разработке СБИС.
Позднее Секей понял, что это неравенство даёт очень простое доказательство некоторых важных теорем в геометрии инцидентности. Например, теорема Семереди – Троттера, верхняя грань числа инциденций, возможных между данным числом точек и прямых на плоскости, следует из построения графа, вершинами которого служат заданные точки, а рёбрами — отрезки на прямых, соединяющие точки. Если бы имелось больше инциденций, чем позволяет теорема Семереди – Троттера, этот граф имел бы больше пересечений, чем общее число пар прямых, что невозможно. Неравенство также можно использовать для доказательства , утверждающей, что если конечное множество точек не имеет линейного числа коллинеарных точек, то это множество определяет квадратичное число различных прямых. Похожим образом Тамал Дей использовал неравенство для доказательства верхних границ .
Доказательство Сначала дадим предварительную оценку — для любого графа с вершинами и рёбрами имеем
Для доказательства этого представим рисунок графа , который имеет в точности пересечений. Каждое из этих пересечений может быть удалено путём удаления ребра из . Тогда мы можем найти граф с по меньшей мере рёбрами и вершинами, не имеющий пересечений, а потому этот граф планарен. Но из формулы Эйлера мы должны тогда иметь , откуда следует требуемое. (Фактически мы имеем для ).
Для получения фактического неравенства числа пересечений, мы теперь используем вероятностные доводы. Пусть является вероятностным параметром, который выберем позже. Построим случайный подграф подграфа , в котором каждая вершина графа попадает в независимо с вероятностью , а ребро графа попадает в граф тогда и только тогда, когда две вершины попадают в граф . Пусть и обозначают число рёбер, вершин и числа пересечений в графе соответственно. Поскольку является подграфом графа , рисунок графа содержит рисунок графа . Согласно предварительному неравенству пересечений имеем
Рассмотрим математические ожидания этих величин, получим
Поскольку каждая из вершин графа попадает с вероятностью в граф , мы имеем . Подобным же образом, каждое из рёбер графа имеет вероятность оказаться в графе , поскольку оба конца графа должны в нём находиться . Таким образом, . Наконец, каждое пересечение на рисунке графа имеет вероятность оказаться в графе , поскольку каждое пересечение требует наличия четырёх вершин. Чтобы это показать, представим рисунок графа с пересечениями. Мы можем допустить, что любые два ребра на этом рисунке с общей вершиной не пересекаются, в противном случае они образуют что-то близкое к букве альфа (см. рисунок) и мы можем обменять местами части дуг до точки пересечения и уменьшить число пересечений. Тогда любое пересечение на рисунке графа имеет четыре различные вершины графа . Таким образом, и мы получаем
Теперь, если мы положим (мы выше предположили, что ), после некоторых алгебраических выкладок, получим
Небольшое улучшение этого подхода позволяет заменить на для .
Вариации Для графов с обхватом, большим и числом рёбер , Пах, Спенсер и Тот показали улучшение этого неравенства до.
Примечания
Литература
Категория:Топологическая теория графов Категория:Неравенства Категория:Визуализация графов