Меню Главная Случайная статья Настройки Неравенство числа пересечений Материал из https://ru.wikipedia.org Неравенство числа пересечений или лемма о пересечениях даёт нижнюю грань минимального числа пересечений данного графа как функцию от числа рёбер и вершин графа. Лемма утверждает, что для графов, у которых число рёбер e достаточно велико по сравнению с числом вершин Неравенство имеет приложения при разработке СБИС и в комбинаторной геометрии. Неравенство открыли Аитаи, Хватал, Ньюборн и Семереди[1] и, независимо, Лейтон[2]. Содержание 1 Утверждение и история 2 Приложения 3 Доказательство 4 Вариации 5 Примечания 6 Литература Утверждение и история Неравенство числа пересечений утверждает, что для неориентированного простого графа ${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.}$ Константа Константа Приложения Причина, побудившая Лейтона к изучению числа пересечений, заключалась в приложениях к разработке СБИС[2]. Позднее Секей понял, что это неравенство даёт очень простое доказательство некоторых важных теорем в геометрии инцидентности. Например, теорема Семереди – Троттера, верхняя грань числа инциденций, возможных между данным числом точек и прямых на плоскости, следует из построения графа, вершинами которого служат заданные точки, а рёбрами — отрезки на прямых, соединяющие точки. Если бы имелось больше инциденций, чем позволяет теорема Семереди – Троттера, этот граф имел бы больше пересечений, чем общее число пар прямых, что невозможно. Неравенство также можно использовать для доказательства теоремы Бека[англ.], утверждающей, что если конечное множество точек не имеет линейного числа коллинеарных точек, то это множество определяет квадратичное число различных прямых[6]. Похожим образом Тамал Дей использовал неравенство для доказательства верхних границ геометрических k-множеств[англ.][7]. Доказательство Сначала дадим предварительную оценку — для любого графа ${\displaystyle \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. Пусть eH, nH и crH обозначают число рёбер, вершин и числа пересечений в графе 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[nH] = pn. Подобным же образом, каждое из рёбер графа G имеет вероятность p2 оказаться в графе H, поскольку оба конца графа должны в нём находиться H. Таким образом, E[eH] = p2e. Наконец, каждое пересечение на рисунке графа G имеет вероятность p4 оказаться в графе H, поскольку каждое пересечение требует наличия четырёх вершин. Чтобы это показать, представим рисунок графа G с cr(G) пересечениями. Мы можем допустить, что любые два ребра на этом рисунке с общей вершиной не пересекаются, в противном случае они образуют что-то близкое к букве альфа (см. рисунок) и мы можем обменять местами части дуг до точки пересечения и уменьшить число пересечений. Тогда любое пересечение на рисунке графа имеет четыре различные вершины графа G. Таким образом, E[crH] = p4cr(G) и мы получаем ${\displaystyle p^{4}\operatorname {cr} (G)\geq p^{2}e-3pn.}$ Теперь, если мы положим p = 4n/e < 1 (мы выше предположили, что e > 4n), после некоторых алгебраических выкладок, получим ${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{64n^{2}}}.}$ Небольшое улучшение этого подхода позволяет заменить 64 на 33.75 для e > 7.5n[3]. Вариации Для графов с обхватом, большим 2r и числом рёбер e 4n, Пах, Спенсер и Тот показали улучшение этого неравенства до[8]. ${\displaystyle \operatorname {cr} (G)\geq c_{r}{\frac {e^{r+2}}{n^{r+1}}}.}$ Примечания Ajtai, Chvtal, Newborn, Szemerdi, 1982, с. 9–12. 1 2 Leighton, 1983. 1 2 Ackerman, 2013. Pach, Tth, 1997, с. 427–439. Pach, Radoii, Tardos, Tth, 2006, с. 527–552. Szkely, 1997, с. 353–358. Dey, 1998, с. 373–382. Pach, Spencer, Tth, 2000, с. 623–644. Литература Mikls Ajtai, Vclav Chvtal, M. M. Newborn, E. Szemerdi. Crossing-free subgraphs // Theory and practice of combinatorics. — North-Holland, Amsterdam, 1982. — Т. 60. — С. 9–12. — (North-Holland Mathematics Studies). T. Leighton. Complexity Issues in VLSI. — Cambridge, MA: MIT Press, 1983. — (Foundations of Computing Series). Eyal Ackerman. On topological graphs with at most four crossings per edge : сайт. — 2013. — arXiv:1509.01932v1. Архивировано 8 сентября 2015 года. Jnos Pach, Gza Tth. Graphs drawn with few crossings per edge // Combinatorica. — 1997. — Т. 17, вып. 3. — С. 427–439. — doi:10.1007/BF01215922. Jnos Pach, Rado Radoii, Gbor Tardos, Gza Tth. Improving the crossing lemma by finding more crossings in sparse graphs // Discrete and Computational Geometry. — 2006. — Т. 36, вып. 4. — С. 527–552. — doi:10.1007/s00454-006-1264-9. L. A. Szkely. Crossing numbers and hard Erds problems in discrete geometry // Combinatorics, Probability and Computing. — 1997. — Т. 6, вып. 3. — С. 353–358. — doi:10.1017/S0963548397002976. T. L. Dey. Improved bounds for planar k-sets and related problems // Discrete and Computational Geometry. — 1998. — Т. 19, вып. 3. — С. 373–382. — doi:10.1007/PL00009354. Jnos Pach, Joel Spencer, Gza Tth. New bounds on crossing numbers // Discrete and Computational Geometry. — 2000. — Т. 24, вып. 4. — С. 623–644. — doi:10.1145/304893.304943.