Русская Википедия:Неравенство числа пересечений
Неравенство числа пересечений или лемма о пересечениях даёт нижнюю грань минимального числа пересечений данного графа как функцию от числа рёбер и вершин графа. Лемма утверждает, что для графов, у которых число рёбер Шаблон:Mvar достаточно велико по сравнению с числом вершин Шаблон:Mvar, число пересечений по меньшей мере пропорционально Шаблон:Math.
Неравенство имеет приложения при разработке СБИС и в комбинаторной геометрии. Неравенство открыли Аитаи, Хватал, Ньюборн и СемередиШаблон:Sfn и, независимо, ЛейтонШаблон:Sfn.
Утверждение и история
Неравенство числа пересечений утверждает, что для неориентированного простого графа Шаблон:Mvar с Шаблон:Mvar вершинами и Шаблон:Mvar рёбрами, такого, что Шаблон:Math, число пересечений в графе Шаблон:Math удовлетворяет неравенству
- <math>\operatorname{cr}(G) \geq \frac{e^3}{29 n^2}.</math>
Константа Шаблон:Math является лучшей на настоящее время и принадлежит АкермануШаблон:Sfn. О более ранних результатах с более слабыми константами смотрите статьи Паха и ТотаШаблон:Sfn, Паха Радожича, Тардоса и ТотаШаблон:Sfn.
Константа Шаблон:Math может быть понижена до Шаблон:Math, но ценой этого константа Шаблон:Math заменяется худшей константой Шаблон:Math.
Приложения
Причина, побудившая Лейтона к изучению числа пересечений, заключалась в приложениях к разработке СБИСШаблон:Sfn.
Позднее Секей понял, что это неравенство даёт очень простое доказательство некоторых важных теорем в геометрии инцидентности. Например, теорема Семереди – Троттера, верхняя грань числа инциденций, возможных между данным числом точек и прямых на плоскости, следует из построения графа, вершинами которого служат заданные точки, а рёбрами — отрезки на прямых, соединяющие точки. Если бы имелось больше инциденций, чем позволяет теорема Семереди – Троттера, этот граф имел бы больше пересечений, чем общее число пар прямых, что невозможно. Неравенство также можно использовать для доказательства Шаблон:Не переведено 5, утверждающей, что если конечное множество точек не имеет линейного числа коллинеарных точек, то это множество определяет квадратичное число различных прямыхШаблон:Sfn. Похожим образом Тамал Дей использовал неравенство для доказательства верхних границ Шаблон:Не переведено 5Шаблон:Sfn.
Доказательство
Сначала дадим предварительную оценку — для любого графа Шаблон:Mvar с Шаблон:Mvar вершинами и Шаблон:Mvar рёбрами имеем
- <math>\operatorname{cr}(G) \geq e - 3n.</math>
Для доказательства этого представим рисунок графа Шаблон:Mvar, который имеет в точности Шаблон:Math пересечений. Каждое из этих пересечений может быть удалено путём удаления ребра из Шаблон:Mvar. Тогда мы можем найти граф с по меньшей мере Шаблон:Math рёбрами и Шаблон:Mvar вершинами, не имеющий пересечений, а потому этот граф планарен. Но из формулы Эйлера мы должны тогда иметь Шаблон:Math, откуда следует требуемое. (Фактически мы имеем Шаблон:Math для Шаблон:Math).
Для получения фактического неравенства числа пересечений, мы теперь используем вероятностные доводы. Пусть Шаблон:Math является вероятностным параметром, который выберем позже. Построим случайный подграф Шаблон:Mvar подграфа Шаблон:Mvar, в котором каждая вершина графа Шаблон:Mvar попадает в Шаблон:Mvar независимо с вероятностью Шаблон:Mvar, а ребро графа Шаблон:Mvar попадает в граф Шаблон:Mvar тогда и только тогда, когда две вершины попадают в граф Шаблон:Mvar. Пусть Шаблон:Mvar и Шаблон:Math обозначают число рёбер, вершин и числа пересечений в графе Шаблон:Mvar соответственно. Поскольку Шаблон:Mvar является подграфом графа Шаблон:Mvar, рисунок графа Шаблон:Mvar содержит рисунок графа Шаблон:Mvar. Согласно предварительному неравенству пересечений имеем
- <math>\operatorname{cr}_H \geq e_H - 3n_H.</math>
Рассмотрим математические ожидания этих величин, получим
- <math>\mathbf{E}[\operatorname{cr}_H] \geq \mathbf{E}[e_H] - 3 \mathbf{E}[n_H].</math>
Поскольку каждая из Шаблон:Mvar вершин графа Шаблон:Mvar попадает с вероятностью Шаблон:Mvar в граф Шаблон:Mvar, мы имеем Шаблон:Math. Подобным же образом, каждое из рёбер графа Шаблон:Mvar имеет вероятность Шаблон:Math оказаться в графе Шаблон:Mvar, поскольку оба конца графа должны в нём находиться Шаблон:Mvar. Таким образом, Шаблон:Math. Наконец, каждое пересечение на рисунке графа Шаблон:Mvar имеет вероятность Шаблон:Math оказаться в графе Шаблон:Mvar, поскольку каждое пересечение требует наличия четырёх вершин. Чтобы это показать, представим рисунок графа Шаблон:Mvar с Шаблон:Math пересечениями. Мы можем допустить, что любые два ребра на этом рисунке с общей вершиной не пересекаются, в противном случае они образуют что-то близкое к букве альфа (см. рисунок) и мы можем обменять местами части дуг до точки пересечения и уменьшить число пересечений. Тогда любое пересечение на рисунке графа имеет четыре различные вершины графа Шаблон:Mvar. Таким образом, Шаблон:Math и мы получаем
- <math> p^4 \operatorname{cr}(G) \geq p^2 e - 3 p n.</math>
Теперь, если мы положим Шаблон:Math (мы выше предположили, что Шаблон:Math), после некоторых алгебраических выкладок, получим
- <math> \operatorname{cr}(G) \geq \frac{e^3}{64 n^2}.</math>
Небольшое улучшение этого подхода позволяет заменить Шаблон:Math на Шаблон:Math для Шаблон:MathШаблон:Sfn.
Вариации
Для графов с обхватом, большим Шаблон:Math и числом рёбер Шаблон:Math, Пах, Спенсер и Тот показали улучшение этого неравенства доШаблон:Sfn.
- <math>\operatorname{cr}(G) \geq c_r\frac{e^{r+2}}{n^{r+1}}.</math>
Примечания
Литература
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
