Нерівність числа схрещень або лема про схрещення дає нижню межу мінімальної кількості схрещень даного графа як функцію від числа ребер і вершин графа. Лема стверджує, що для графів, у яких число ребер досить велике, порівняно з числом вершин , число схрещень принаймні пропорційне
Нерівність застосовують при розробці надвеликих інтегральних схем (НВІС) та в комбінаторній геометрії. Нерівність відкрили Айтай, Хватал, Ньюборн та Семереді і, незалежно, Лейтон.
Твердження та історія Нерівність числа схрещень стверджує, що для неорієнтованого простого графа з вершинами та ребрами, такого, що число схрещень у графі задовольняє нерівності
Стала є найкращою на даний час і належить Акерману. Раніші результати зі слабшими сталими наведено в статтях Паха і Тота, Паха, Радожича, Тардоса і Тота.
Сталу можна знизити до , але ціною цього стала замінюється гіршою сталою .
Затсосування Причина, що спонукала Лейтона до вивчення числа схрещень, полягала в застосуванні до розробки НВІС.
Пізніше Секей зрозумів, що ця нерівність дає дуже просте доведенняч деяких важливих теорем у геометрії інцидентності. Наприклад, теорема Семереді — Троттера, верхня грань числа інциденцій, можливих між даним числом точок і прямих на площині, випливає з побудови графа, вершинами якого є задані точки, а ребрами — відрізки на прямих, що з'єднують точки. Якби було більше інциденцій, ніж дозволяє теорема Семереді — Троттера, цей граф мав би більше схрещень, ніж загальна кількість пар прямих, що неможливо. Нерівність також можна використати для доведення , яка стверджує, що якщо скінченна множина точок не має лінійного числа колінеарних точок, то ця множина визначає квадратичне число різних прямих. У подібний спосіб Тамал Дей використав нерівність для доведення верхніх меж .
Доведення Спочатку дамо попередню оцінку — для будь-якого графа з вершинами та ребрами маємо
Для доведення цього наведемо малюнок графа , який має рівно схрещень. Кожне з цих схрещень можна видалити, видаливши ребро з Тоді можна знайти граф з принаймні ребрами та вершинами, який не має схрещень, тому цей граф планарний. Але тоді з формули Ейлера має бути , звідки випливає необхідне. (Фактично ми маємо для ).
Для отримання фактичної нерівності числа схрещень, ми тепер використовуємо імовірнісні доводи. Нехай є ймовірнісним параметром, який виберемо пізніше. Побудуємо випадковий підграф підграфа , у якому кожна вершина графа потрапляє в незалежно з імовірністю , а ребро графа потрапляє до графа тоді й лише тоді, коли дві вершини потрапляють у граф . Нехай і позначають число ребер, вершин та числа схрещень у графі відповідно. Оскільки є підграфом графа , то малюнок графа містить малюнок графа . За попередньою нерівністю схрещень маємо
Розглянувши математичні сподівання цих величин, отримаємо
Оскільки кожна з вершин графа потрапляє з імовірністю у граф , ми маємо . Подібним чином, кожне з ребер графа має ймовірність опинитися в графі , оскільки обидва його кінці мають міститися в . Таким чином, . Нарешті, кожне схрещення на малюнку графа має ймовірність опинитися в графі , оскільки кожне схрещення потребує наявності чотирьох вершин. Щоб це показати, розглянемо малюнок графа з схрещеннями. Можна припустити, що будь-які два ребра на цьому малюнку, які мають спільну вершину, не перехрещуються, інакше вони утворюють щось подібне до літери (див. малюнок) і можна поміняти місцями частини дуг до точки схрещення та зменшити кількість схрещень. Тоді будь-яке схрещення на малюнку графа має чотири різні вершини графа . Таким чином, і ми отримуємо
Тепер, якщо ми покладемо (ми вище припустили, що ), після деяких алгебричних викладок, отримаємо
Незначне покращення цього підходу дозволяє замінити на для .
Варіації Для графів з обхватом, більшим від і числом ребер , Пах, Спенсер і Тот показали поліпшення цієї нерівності до
Примітки
Література