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

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

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

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

Нерівність числа схрещень стверджує, що для неорієнтованого простого графа Шаблон:Mvar з Шаблон:Mvar вершинами та Шаблон:Mvar ребрами, такого, що Шаблон:Math число схрещень у графі Шаблон:Math задовольняє нерівності

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

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

Сталу Шаблон:Math можна знизити до Шаблон:Math, але ціною цього стала Шаблон:Math замінюється гіршою сталою Шаблон:Math.

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

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

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

Доведення

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

$\mathrm{cr}(G)\ge e-3n.$

Для доведення цього наведемо малюнок графа Шаблон:Mvar, який має рівно Шаблон:Math схрещень. Кожне з цих схрещень можна видалити, видаливши ребро з Шаблон:Mvar Тоді можна знайти граф з принаймні Шаблон:Math ребрами та Шаблон:Mvar вершинами, який не має схрещень, тому цей граф планарний. Але тоді з формули Ейлера має бути Шаблон:Math, звідки випливає необхідне. (Фактично ми маємо Шаблон:Math для Шаблон:Math).

Для отримання фактичної нерівності числа схрещень, ми тепер використовуємо імовірнісні доводи. Нехай Шаблон:Math є ймовірнісним параметром, який виберемо пізніше. Побудуємо випадковий підграф Шаблон:Mvar підграфа Шаблон:Mvar, у якому кожна вершина графа Шаблон:Mvar потрапляє в Шаблон:Mvar незалежно з імовірністю Шаблон:Mvar, а ребро графа Шаблон:Mvar потрапляє до графа Шаблон:Mvar тоді й лише тоді, коли дві вершини потрапляють у граф Шаблон:Mvar. Нехай Шаблон:Mvar і Шаблон:Math позначають число ребер, вершин та числа схрещень у графі Шаблон:Mvar відповідно. Оскільки Шаблон:Mvar є підграфом графа Шаблон:Mvar, то малюнок графа Шаблон:Mvar містить малюнок графа Шаблон:Mvar. За попередньою нерівністю схрещень маємо

${\mathrm{cr}}_H\ge e_H-3n_H.$

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

$𝐄[{\mathrm{cr}}_H]\ge 𝐄[e_H]-3𝐄[n_H].$

Суміжні перехресні ребра можна перемалювати так, що кількість схрещень зменшиться

Оскільки кожна з Шаблон:Mvar вершин графа Шаблон:Mvar потрапляє з імовірністю Шаблон:Mvar у граф Шаблон:Mvar, ми маємо Шаблон:Math. Подібним чином, кожне з ребер графа Шаблон:Mvar має ймовірність Шаблон:Math опинитися в графі Шаблон:Mvar, оскільки обидва його кінці мають міститися в Шаблон:Mvar. Таким чином, Шаблон:Math. Нарешті, кожне схрещення на малюнку графа Шаблон:Mvar має ймовірність Шаблон:Math опинитися в графі Шаблон:Mvar, оскільки кожне схрещення потребує наявності чотирьох вершин. Щоб це показати, розглянемо малюнок графа Шаблон:Mvar з Шаблон:Math схрещеннями. Можна припустити, що будь-які два ребра на цьому малюнку, які мають спільну вершину, не перехрещуються, інакше вони утворюють щось подібне до літери $\alpha$ (див. малюнок) і можна поміняти місцями частини дуг до точки схрещення та зменшити кількість схрещень. Тоді будь-яке схрещення на малюнку графа має чотири різні вершини графа Шаблон:Mvar. Таким чином, Шаблон:Math і ми отримуємо

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

Тепер, якщо ми покладемо Шаблон:Math (ми вище припустили, що Шаблон:Math), після деяких алгебричних викладок, отримаємо

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

Незначне покращення цього підходу дозволяє замінити Шаблон:Math на Шаблон:Math для Шаблон:MathШаблон:Sfn.

Варіації

Для графів з обхватом, більшим від Шаблон:Math і числом ребер Шаблон:Math, Пах, Спенсер і Тот показали поліпшення цієї нерівності доШаблон:Sfn

$\mathrm{cr}(G)\ge c_r\frac{e^{r+2}}{n^{r+1}}.$

Література

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття