Лема регулярності Семереді
Лема регулярності Семереді — лема із загальної теорії графів, яка стверджує, що вершини будь-якого досить великого графа можна розбити на скінченне число таких груп, що майже у всіх двочасткових графах, що з'єднують вершини з двох різних груп, ребра розподілені між вершинами майже рівномірно. При цьому найменша необхідна кількість груп, на які потрібно розбити множину вершин графа, може бути як завгодно великою, але кількість груп у розбитті завжди обмежена зверху.
Неформально кажучи, лема стверджує наявність багатьох великих псевдовипадкових структур у будь-якому графі досить великого розміру.
Лему довів Ендре Семереді 1975 році[1][2].
Формулювання
Поняття ε-рівномірності
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9c/Epsilon-regularity.png/220px-Epsilon-regularity.png)
Нехай дано двочастковий граф , ребра якого з'єднують вершини зі множини
з вершинами зі множини
.
Для позначимо через
щільність розподілу ребер між цими множинами, тобто
.
Двочастковий граф |
Існує кілька еквівалентних цьому визначень (еквівалентних у сенсі існування монотонної залежності в одному визначенні від
в іншому за еквівалентності двох визначень), але всі вони використовують величину
і якесь кількісне порівняння її значень для різних пар
.
Очевидно, що повний і порожній двочасткові графи є -регулярними для будь-якого
. Слід зазначити, що це, взагалі кажучи, не так для довільного регулярного в звичайному сенсі двочасткового графа (як контрприклад можна розглянути об'єднання кількох неперетинних за множиною вершин регулярних графів).
-Рівномірні графи за даного
іноді також називають псевдовипадковими, оскільки за рівномірністю розподілу ребер між вершинами вони схожі на згенеровані випадково.
Формулювання леми
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/3-partite_graph_with_difference_density.png/400px-3-partite_graph_with_difference_density.png)
Лема регулярності Семереді[3][4] Для будь-яких |
Зауваження
Лема не накладає жодних обмежень на ребра між вершинами з однієї й тієї ж множини розбиття.
Твердження леми нетривіальне тільки для графів із досить великим числом ребер. Якщо , то будь-який його двочастковий підграф на частках із розмірами
також виявиться розрідженим (його щільність не перевищуватиме
) — отже, умова на різницю щільностей виконуватиметься завжди[5].
Слід також зазначити, що згадка однієї й тієї ж змінної у двох різних характеристиках — показнику регулярності та частці
-регулярних двочасткових підграфів — не створює жодного додаткового зв'язку між цими характеристиками. Таке формулювання випливало б і з ослабленішого формулювання, де потрібно, наприклад, щоб
-регулярно були розподілені ребра тільки між
парами множин, де
при
(тобто навіть за
). У такому разі для досягнення початкового формулювання достатньо було б розглянути
, оскільки
-регулярність графа тягне за собою
-регулярність при
.
Доведення
Алгоритм розбиття
Розбиття проводиться жадібним алгоритмом.
Спочатку вибирається довільне розбиття вершин на множини , де:
Далі на кожній ітерації алгоритму з наявного розбиття певним чином генерується нове розбиття з меншими розмірами часток і більшою кількістю. Воно будується як підрозбиття початкового розбиття, але потім нормалізується невеликими перебудовами, щоб розміри всіх (крім, можливо, однієї) часток виявилися рівними.
Таке перетворення триває, поки в розбитті на множин залишається хоча б
пар множин, двочасткові графи між якими не
-регулярні. Перехід від одного розбиття до наступного відбувається так, що можна довести, що алгоритм точно зупиниться за скінченне та обмежене сталою (залежною від
і
) число кроків. Крім того, кількість отриманих множин у розбитті на кожній конкретній ітерації алгоритму також обмежена, так що найбільша кількість множин, яка може утворитися на останній ітерації, і буде шуканою величиною
.
Перехід від розбиття до підрозбиття
Нехай поточне розбиття не задовольняє умову леми, тобто є
пар
, для яких двочастковий граф між ними не
-регулярний. Позначимо цю умову, як
.
Якщо , то існують якісь конкретні «проблемні» підмножини
, що порушують
-регулярність двочасткового графа, який з'єднує ці компоненти. Тобто для них виконано:
Розумно виглядає ідея позбавиться цих проблемних підмножин, просто виділивши їх у окрему компоненту, утворивши замість пари компонент четвірку
. Однак одна й та ж компонента
може конфліктувати відразу з декількома іншими компонентами, так що розбиття слід проводити не за однією, а одразу за кількома проблемними множинами.
Щоб формалізувати цей процес, для кожної окремої компоненти розглядають усі «проблемні» підмножини, що виникають у ній:
та σ-алгебру, утворену на
(тобто
підрозбивається на такі частини, щоб будь-які дві вершини, одна з яких належить деякому
, а інша йому не належить, опинилися в різних частинах підрозбиття).
Оскільки для окремого існує не більше
проблемних підмножин (і, отже, не більше
елементів побудованої на них σ-алгебри), то в результаті з однієї компоненти утворюється не більше
нових.
Якщо підрозбити в такий спосіб кожну компоненту , то вийде нове підрозбиття
.
Далі в треба вирівняти розміри компонент (яких у ньому всього не більше
). Для цього кожну його компоненту можна розділити на нові компоненти розміру
(і, можливо, одну компоненту меншого розміру — «залишок»), а всі вершини з «залишків» з'єднати довільно в нові компоненти того ж розміру
і, можливо, одну компоненту меншого розміру.
Розбиття, що вийшло, і буде результатом однієї ітерації алгоритму.
Оцінка кількості кроків алгоритму
Доведення зупинки алгоритму після скінченного числа кроків проводиться через уведення потенціальної функції — чисельної величини, що залежить від поточного розбиття — і відстеження її зміни при зміні ітерацій алгоритму.
«Потенціал» можна визначити, наприклад, так:
Ця функція має низку важливих властивостей:
- якщо розбиття
утворено з
підрозбиттям однієї компоненти
на дві множини
і
, то
Це випливає з нерівності , істинної при
, яка тягне за собою нерівність
- для розбиття
з алгоритму, описаного в попередньому розділі, виконується нерівність
- якщо розбиття
отримано з розбиття
перерозподілом вершин кількох компонент
на якісь інші компоненти (не обов'язково підрозбиттям), то
Достатньо показати, що об'єднання зменшує
не більш, ніж на
(подальше підрозбиття не зменшує
, згідно з другою властивістю).
При об'єднанні компонент із суми зникають деякі доданки та з'являються якісь нові. Оскільки всі доданки додатні, досить розглянути ті, які зникають. Суму таких доданків легко оцінити:
Оскільки при отриманні нового розбиття згідно з алгоритмом у підрозбитті перебудовується не більше ніж
вершин і оскільки
за досить великих
для будь-якої константи
, то зі властивостей потенціальної функції випливає, що алгоритм зупиниться через
кроків.
У першій праці на цю тему Семереді використав дещо іншу функцію потенціалу[1]:
Попри відмінності, обидві функції об'єднує ідея усереднення квадратів щільностей.
Оцінка розміру розбиття
Як випливає з опису алгоритму, верхня оцінка кількості компонент у розбитті на -й ітерації алгоритму виражається рекурентним співвідношенням
Кількість ітерацій, що пропрацює алгоритм, оцінюється як .
Отже, підсумкову кількість компонент можна оцінити лише вежею з піднесень до степеня висоти
.
Ефективний алгоритм пошуку розбиття
Типове математичне доведення леми Семереді не дбає про обчислювальну складність алгоритму.
Однак група з п'яти математиків у окремій праці дослідила алгоритмічний аспект пошуку потрібного розбиття — зокрема вони описали алгоритм, що дозволяє знайти розбиття -вершинного графа за час
за фіксованих
і
. Час роботи їхнього алгоритму обмежено часом множення двох матриць
, що складаються з нулів та одиниць. Також алгоритм можна розпаралелити і виконати за час
на поліноміально залежному від
числі процесорів[6].
Нижня оцінка розміру шуканого розбиття
1997 року Вільям Гауерс показав, що оцінку розміру кількості компонент у шуканому розбитті не можна покращити більш, ніж до вежі степенів висоти
. А саме він показав, що завжди існує граф, будь-яке розбиття якого на меншу кількість частин не задовольняє умов леми.
Він розглянув навіть узагальнене поняття -регулярності, де на підмножину часток двочасткового графа
, відхилення щільності якої обмежується визначенням, накладаються обмеження
замість
, і для нього також довів існування контрприкладу.
Для пошуку контрприкладу Гауерс використав імовірнісний метод, тому його доведення неконструктивне. У роботі розглянуто зважені графи з вагами з інтервалу . Для таких графів можна розглядати повністю аналогічне формулювання леми, де як щільність
буде розглядатися сума ваг ребер, замість їхньої кількості. Побудувавши контрприклад у вигляді зваженого графа, Гауерс також показав, що випадковий граф, який генерується за схемою Бернуллі, з імовірностями ребер, що відповідають вагам у цьому зваженому графі, з великою ймовірністю буде контрприкладом для звичайної леми (більш того, з великою ймовірністю щільності
будуть не сильно відхилятися від аналогічних щільностей у зваженому графі за умови, що
і
достатньо великі)[7].
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9f/Gowers_construction_for_lower_bound_of_Szemeredi_regularity_lemma.gif/500px-Gowers_construction_for_lower_bound_of_Szemeredi_regularity_lemma.gif)
Зважений граф, який є контрприкладом для леми зі звичайним визначенням -регулярності, будується як комбінація з різними вагами кількох специфічно влаштованих великих графів. При побудові кожного наступного графа з цього набору вершини об'єднуються у все більші й більші групи рівного розміру такі, що вершини з двох різних груп або з'єднуються між собою повним двочастковим графом, або взагалі не з'єднуються (нові групи завжди є об'єднанням попередніх).
Нехай вершини розбито на групи однакового розміру. Об'єднаємо ці групи в блоки
,
де (вважаємо, що це - ціле число).
Для кожної пари різних блоків виберемо розбиття
груп із
на дві частини та розбиття
груп із
на дві частини. Додамо в граф усі ребра повних двочасткових графів
і
.
Якщо вибирати розбиття так, щоб у будь-яких , що належать одному
, було не більше
блоків, у яких є вершини, суміжні їм обом, то за правильного добору
і
конструкція, що вийшла, і буде конструкцією Гауерса. Але це конструкція лише одного графа – для побудови наступного графа блоки
ставляться на місце груп
і весь процес починається спочатку, поки всі вершини не буде об'єднано в одну групу.
Отриманий ланцюжок графів об'єднується у зважений граф за формулою
(найбільші ваги мають графи, в яких об'єднані групи вершин дуже великі).
Контрприклад для -регулярності будується в схожий спосіб, але з кількома відмінностями:
- групи всередині одного блока
розбиваються не на два, на довільне число
наборів
;
- на кількість груп у кожному наборі
накладаються обмеження за розміром (вони не повинні бути надто малими);
- в кінці отримані графи
об'єднують не у вигляді зваженого графа, а виключним «або» (до підсумкового графа входять лише ті ребра, які були наявні в непарній кількості графів
).
Узагальнення
2007 року Вільям Гауерс узагальнив лему регулярності на гіперграфи та використав узагальнення для доведення багатовимірної теореми Семереді[8].
Існує також аналог леми Семереді для розріджених графів (у звичайному формулюванні лема є тривіальною для таких графів, оскільки будь-яке розбиття задовольняє потрібні умови)[9].
Застосування
Найвідоміше застосування леми регулярності для комбінаторного доведення теореми Семереді та її узагальнень (наприклад, теореми про кутики)[5]. Однак лема та її ідеї мають низку застосувань і в загальній теорії графів[10] — першу статтю Семереді про цю лему процитовано більш ніж у 500 працях на різні теми[1].
Також окремий інтерес становить лема про видалення трикутників, яка виводиться з леми регулярності і використовується під час доведення теореми Семереді.