Нерівність числа схрещень

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

Нерівність застосовують при розробці надвеликих інтегральних схем (НВІС) та в комбінаторній геометрії. Нерівність відкрили Айтай, Хватал, Ньюборн та Семереді і, незалежно, Лейтон.

Твердження та історія

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

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

Стала 29 є найкращою на даний час і належить Акерману. Раніші результати зі слабшими сталими наведено в статтях Паха і Тота, Паха, Радожича, Тардоса і Тота.

Сталу 7 можна знизити до 4, але ціною цього стала 29 замінюється гіршою сталою 64.

Затсосування

Причина, що спонукала Лейтона до вивчення числа схрещень, полягала в застосуванні до розробки НВІС.

Пізніше Секей зрозумів, що ця нерівність дає дуже просте доведенняч деяких важливих теорем у геометрії інцидентності. Наприклад, теорема Семереді — Троттера, верхня грань числа інциденцій, можливих між даним числом точок і прямих на площині, випливає з побудови графа, вершинами якого є задані точки, а ребрами — відрізки на прямих, що з'єднують точки. Якби було більше інциденцій, ніж дозволяє теорема Семереді — Троттера, цей граф мав би більше схрещень, ніж загальна кількість пар прямих, що неможливо. Нерівність також можна використати для доведення теореми Бека, яка стверджує, що якщо скінченна множина точок не має лінійного числа колінеарних точок, то ця множина визначає квадратичне число різних прямих. У подібний спосіб Тамал Дей використав нерівність для доведення верхніх меж геометричних k-множин.

Доведення

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

$\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. Нехай e_H, n_H і cr_H позначають число ребер, вершин та числа схрещень у графі H відповідно. Оскільки H є підграфом графа G, то малюнок графа G містить малюнок графа H. За попередньою нерівністю схрещень маємо

$\operatorname {cr} _{H}\geq e_{H}-3n_{H}.$

Розглянувши математичні сподівання цих величин, отримаємо

$\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) схрещеннями. Можна припустити, що будь-які два ребра на цьому малюнку, які мають спільну вершину, не перехрещуються, інакше вони утворюють щось подібне до літери $\alpha$ (див. малюнок) і можна поміняти місцями частини дуг до точки схрещення та зменшити кількість схрещень. Тоді будь-яке схрещення на малюнку графа має чотири різні вершини графа G. Таким чином, E[cr_H] = p⁴cr(G) і ми отримуємо

$p^{4}\operatorname {cr} (G)\geq p^{2}e-3pn.$

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

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

Незначне покращення цього підходу дозволяє замінити 64 на 33.75 для e > 7.5n.

Варіації

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

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

Література

• Miklós Ajtai, Václav Chvátal, M. M. Newborn, E. Szemerédi. 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.
• János Pach, Géza Tóth. Graphs drawn with few crossings per edge // Combinatorica. — 1997. — Т. 17, вип. 3. — С. 427–439. — DOI:10.1007/BF01215922.
• János Pach, Radoš Radoičić, Gábor Tardos, Géza Tóth. 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. Székely. Crossing numbers and hard Erdős 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.
• János Pach, Joel Spencer, Géza Tóth. New bounds on crossing numbers // Discrete and Computational Geometry. — 2000. — Т. 24, вип. 4. — С. 623–644. — DOI:10.1145/304893.304943.