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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

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

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

[math]\displaystyle{ \operatorname{cr}(G) \geq \frac{e^3}{29 n^2}. }[/math]

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

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

Приложения

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

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

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

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

[math]\displaystyle{ \operatorname{cr}(G) \geq e - 3n. }[/math]

Для доказательства этого представим рисунок графа 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. Пусть eH, nH и crH обозначают число рёбер, вершин и числа пересечений в графе H соответственно. Поскольку H является подграфом графа G, рисунок графа G содержит рисунок графа H. Согласно предварительному неравенству пересечений имеем

[math]\displaystyle{ \operatorname{cr}_H \geq e_H - 3n_H. }[/math]

Рассмотрим математические ожидания этих величин, получим

[math]\displaystyle{ \mathbf{E}[\operatorname{cr}_H] \geq \mathbf{E}[e_H] - 3 \mathbf{E}[n_H]. }[/math]
Смежные пересекающиеся рёбра можно перерисовать так, что число пересечений уменьшится

Поскольку каждая из n вершин графа G попадает с вероятностью p в граф H, мы имеем E[nH] = pn. Подобным же образом, каждое из рёбер графа G имеет вероятность p2 оказаться в графе H, поскольку оба конца графа должны в нём находиться H. Таким образом, E[eH] = p2e. Наконец, каждое пересечение на рисунке графа G имеет вероятность p4 оказаться в графе H, поскольку каждое пересечение требует наличия четырёх вершин. Чтобы это показать, представим рисунок графа G с cr(G) пересечениями. Мы можем допустить, что любые два ребра на этом рисунке с общей вершиной не пересекаются, в противном случае они образуют что-то близкое к букве альфа (см. рисунок) и мы можем обменять местами части дуг до точки пересечения и уменьшить число пересечений. Тогда любое пересечение на рисунке графа имеет четыре различные вершины графа G. Таким образом, E[crH] = p4cr(G) и мы получаем

[math]\displaystyle{ p^4 \operatorname{cr}(G) \geq p^2 e - 3 p n. }[/math]

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

[math]\displaystyle{ \operatorname{cr}(G) \geq \frac{e^3}{64 n^2}. }[/math]

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

Вариации

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

[math]\displaystyle{ \operatorname{cr}(G) \geq c_r\frac{e^{r+2}}{n^{r+1}}. }[/math]

Примечания

  1. ↑ Ajtai, Chvátal, Newborn, Szemerédi, 1982, с. 9–12.
  2. ↑ 2,0 2,1 Leighton, 1983.
  3. ↑ 3,0 3,1 Ackerman, 2013.
  4. ↑ Pach, Tóth, 1997, с. 427–439.
  5. ↑ Pach, Radoičić, Tardos, Tóth, 2006, с. 527–552.
  6. ↑ Székely, 1997, с. 353–358.
  7. ↑ Dey, 1998, с. 373–382.
  8. ↑ Pach, Spencer, Tóth, 2000, с. 623–644.

Литература

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Неравенство_числа_пересечений&oldid=5815669