Лема регулярності Семереді
Лема регулярності Семереді — лема із загальної теорії графів, яка стверджує, що вершини будь-якого досить великого графа можна розбити на скінченне число таких груп, що майже у всіх двочасткових графах, що з'єднують вершини з двох різних груп, ребра розподілені між вершинами майже рівномірно. При цьому найменша необхідна кількість груп, на які потрібно розбити множину вершин графа, може бути як завгодно великою, але кількість груп у розбитті завжди обмежена зверху.
Неформально кажучи, лема стверджує наявність багатьох великих псевдовипадкових структур у будь-якому графі досить великого розміру.
Лему довів Ендре Семереді 1975 році[1][2].
Нехай дано двочастковий граф , ребра якого з'єднують вершини зі множини з вершинами зі множини .
Для позначимо через щільність розподілу ребер між цими множинами, тобто
- .
Двочастковий граф називають -рівномірним якщо для будь-яких , що задовольняють умови , виконується нерівність |
Існує кілька еквівалентних цьому визначень (еквівалентних у сенсі існування монотонної залежності в одному визначенні від в іншому за еквівалентності двох визначень), але всі вони використовують величину і якесь кількісне порівняння її значень для різних пар .
Очевидно, що повний і порожній двочасткові графи є -регулярними для будь-якого . Слід зазначити, що це, взагалі кажучи, не так для довільного регулярного в звичайному сенсі двочасткового графа (як контрприклад можна розглянути об'єднання кількох неперетинних за множиною вершин регулярних графів).
-Рівномірні графи за даного іноді також називають псевдовипадковими, оскільки за рівномірністю розподілу ребер між вершинами вони схожі на згенеровані випадково.
Лема регулярності Семереді[3][4] Для будь-яких існують такі, що для будь-якого графа з кількістю вершин існує розбиття на максимально можливо рівні за розміром частки такі, що для із пар цих часток двочастковий граф із ребер, що пролягають між ними, є -регулярним. |
Лема не накладає жодних обмежень на ребра між вершинами з однієї й тієї ж множини розбиття.
Твердження леми нетривіальне тільки для графів із досить великим числом ребер. Якщо , то будь-який його двочастковий підграф на частках із розмірами також виявиться розрідженим (його щільність не перевищуватиме ) — отже, умова на різницю щільностей виконуватиметься завжди[5].
Слід також зазначити, що згадка однієї й тієї ж змінної у двох різних характеристиках — показнику регулярності та частці -регулярних двочасткових підграфів — не створює жодного додаткового зв'язку між цими характеристиками. Таке формулювання випливало б і з ослабленішого формулювання, де потрібно, наприклад, щоб -регулярно були розподілені ребра тільки між парами множин, де при (тобто навіть за ). У такому разі для досягнення початкового формулювання достатньо було б розглянути , оскільки -регулярність графа тягне за собою -регулярність при .
Розбиття проводиться жадібним алгоритмом.
Спочатку вибирається довільне розбиття вершин на множини , де:
Далі на кожній ітерації алгоритму з наявного розбиття певним чином генерується нове розбиття з меншими розмірами часток і більшою кількістю. Воно будується як підрозбиття початкового розбиття, але потім нормалізується невеликими перебудовами, щоб розміри всіх (крім, можливо, однієї) часток виявилися рівними.
Таке перетворення триває, поки в розбитті на множин залишається хоча б пар множин, двочасткові графи між якими не -регулярні. Перехід від одного розбиття до наступного відбувається так, що можна довести, що алгоритм точно зупиниться за скінченне та обмежене сталою (залежною від і ) число кроків. Крім того, кількість отриманих множин у розбитті на кожній конкретній ітерації алгоритму також обмежена, так що найбільша кількість множин, яка може утворитися на останній ітерації, і буде шуканою величиною .
Нехай поточне розбиття не задовольняє умову леми, тобто є пар , для яких двочастковий граф між ними не -регулярний. Позначимо цю умову, як .
Якщо , то існують якісь конкретні «проблемні» підмножини , що порушують -регулярність двочасткового графа, який з'єднує ці компоненти. Тобто для них виконано:
Розумно виглядає ідея позбавиться цих проблемних підмножин, просто виділивши їх у окрему компоненту, утворивши замість пари компонент четвірку . Однак одна й та ж компонента може конфліктувати відразу з декількома іншими компонентами, так що розбиття слід проводити не за однією, а одразу за кількома проблемними множинами.
Щоб формалізувати цей процес, для кожної окремої компоненти розглядають усі «проблемні» підмножини, що виникають у ній:
та σ-алгебру, утворену на (тобто підрозбивається на такі частини, щоб будь-які дві вершини, одна з яких належить деякому , а інша йому не належить, опинилися в різних частинах підрозбиття).
Оскільки для окремого існує не більше проблемних підмножин (і, отже, не більше елементів побудованої на них σ-алгебри), то в результаті з однієї компоненти утворюється не більше нових.
Якщо підрозбити в такий спосіб кожну компоненту , то вийде нове підрозбиття .
Далі в треба вирівняти розміри компонент (яких у ньому всього не більше ). Для цього кожну його компоненту можна розділити на нові компоненти розміру (і, можливо, одну компоненту меншого розміру — «залишок»), а всі вершини з «залишків» з'єднати довільно в нові компоненти того ж розміру і, можливо, одну компоненту меншого розміру.
Розбиття, що вийшло, і буде результатом однієї ітерації алгоритму.
Доведення зупинки алгоритму після скінченного числа кроків проводиться через уведення потенціальної функції — чисельної величини, що залежить від поточного розбиття — і відстеження її зміни при зміні ітерацій алгоритму.
«Потенціал» можна визначити, наприклад, так:
Ця функція має низку важливих властивостей:
- якщо розбиття утворено з підрозбиттям однієї компоненти на дві множини і , то
Це випливає з нерівності , істинної при , яка тягне за собою нерівність
- для розбиття з алгоритму, описаного в попередньому розділі, виконується нерівність
- якщо розбиття отримано з розбиття перерозподілом вершин кількох компонент на якісь інші компоненти (не обов'язково підрозбиттям), то
Достатньо показати, що об'єднання зменшує не більш, ніж на (подальше підрозбиття не зменшує , згідно з другою властивістю).
При об'єднанні компонент із суми зникають деякі доданки та з'являються якісь нові. Оскільки всі доданки додатні, досить розглянути ті, які зникають. Суму таких доданків легко оцінити:
Оскільки при отриманні нового розбиття згідно з алгоритмом у підрозбитті перебудовується не більше ніж вершин і оскільки за досить великих для будь-якої константи , то зі властивостей потенціальної функції випливає, що алгоритм зупиниться через кроків.
У першій праці на цю тему Семереді використав дещо іншу функцію потенціалу[1]:
Попри відмінності, обидві функції об'єднує ідея усереднення квадратів щільностей.
Як випливає з опису алгоритму, верхня оцінка кількості компонент у розбитті на -й ітерації алгоритму виражається рекурентним співвідношенням
Кількість ітерацій, що пропрацює алгоритм, оцінюється як .
Отже, підсумкову кількість компонент можна оцінити лише вежею з піднесень до степеня висоти .
Типове математичне доведення леми Семереді не дбає про обчислювальну складність алгоритму.
Однак група з п'яти математиків у окремій праці дослідила алгоритмічний аспект пошуку потрібного розбиття — зокрема вони описали алгоритм, що дозволяє знайти розбиття -вершинного графа за час за фіксованих і . Час роботи їхнього алгоритму обмежено часом множення двох матриць , що складаються з нулів та одиниць. Також алгоритм можна розпаралелити і виконати за час на поліноміально залежному від числі процесорів[6].
1997 року Вільям Гауерс показав, що оцінку розміру кількості компонент у шуканому розбитті не можна покращити більш, ніж до вежі степенів висоти . А саме він показав, що завжди існує граф, будь-яке розбиття якого на меншу кількість частин не задовольняє умов леми.
Він розглянув навіть узагальнене поняття -регулярності, де на підмножину часток двочасткового графа , відхилення щільності якої обмежується визначенням, накладаються обмеження замість , і для нього також довів існування контрприкладу.
Для пошуку контрприкладу Гауерс використав імовірнісний метод, тому його доведення неконструктивне. У роботі розглянуто зважені графи з вагами з інтервалу . Для таких графів можна розглядати повністю аналогічне формулювання леми, де як щільність буде розглядатися сума ваг ребер, замість їхньої кількості. Побудувавши контрприклад у вигляді зваженого графа, Гауерс також показав, що випадковий граф, який генерується за схемою Бернуллі, з імовірностями ребер, що відповідають вагам у цьому зваженому графі, з великою ймовірністю буде контрприкладом для звичайної леми (більш того, з великою ймовірністю щільності будуть не сильно відхилятися від аналогічних щільностей у зваженому графі за умови, що і достатньо великі)[7].
Зважений граф, який є контрприкладом для леми зі звичайним визначенням -регулярності, будується як комбінація з різними вагами кількох специфічно влаштованих великих графів. При побудові кожного наступного графа з цього набору вершини об'єднуються у все більші й більші групи рівного розміру такі, що вершини з двох різних груп або з'єднуються між собою повним двочастковим графом, або взагалі не з'єднуються (нові групи завжди є об'єднанням попередніх).
Нехай вершини розбито на групи однакового розміру. Об'єднаємо ці групи в блоки
- ,
де (вважаємо, що це - ціле число).
Для кожної пари різних блоків виберемо розбиття груп із на дві частини та розбиття груп із на дві частини. Додамо в граф усі ребра повних двочасткових графів і .
Якщо вибирати розбиття так, щоб у будь-яких , що належать одному , було не більше блоків, у яких є вершини, суміжні їм обом, то за правильного добору і конструкція, що вийшла, і буде конструкцією Гауерса. Але це конструкція лише одного графа – для побудови наступного графа блоки ставляться на місце груп і весь процес починається спочатку, поки всі вершини не буде об'єднано в одну групу.
Отриманий ланцюжок графів об'єднується у зважений граф за формулою (найбільші ваги мають графи, в яких об'єднані групи вершин дуже великі).
Контрприклад для -регулярності будується в схожий спосіб, але з кількома відмінностями:
- групи всередині одного блока розбиваються не на два, на довільне число наборів ;
- на кількість груп у кожному наборі накладаються обмеження за розміром (вони не повинні бути надто малими);
- в кінці отримані графи об'єднують не у вигляді зваженого графа, а виключним «або» (до підсумкового графа входять лише ті ребра, які були наявні в непарній кількості графів ).
2007 року Вільям Гауерс узагальнив лему регулярності на гіперграфи та використав узагальнення для доведення багатовимірної теореми Семереді[8].
Існує також аналог леми Семереді для розріджених графів (у звичайному формулюванні лема є тривіальною для таких графів, оскільки будь-яке розбиття задовольняє потрібні умови)[9].
Найвідоміше застосування леми регулярності для комбінаторного доведення теореми Семереді та її узагальнень (наприклад, теореми про кутики)[5]. Однак лема та її ідеї мають низку застосувань і в загальній теорії графів[10] — першу статтю Семереді про цю лему процитовано більш ніж у 500 працях на різні теми[1].
Також окремий інтерес становить лема про видалення трикутників, яка виводиться з леми регулярності і використовується під час доведення теореми Семереді.
- ↑ а б в г E. Szemeredi, «Regular partitions of graphs», Computer science department, School of Humanities and Sciences, Stanford University, 1975
- ↑ E. Szemeredi, "Regular partitions of graphs", Computer science department, School of Humanities and Sciences, Stanford University, 1975 (PDF). Архів (PDF) оригіналу за 23 лютого 2020. Процитовано 29 липня 2018.
- ↑ а б "Mini course of additive combinatorics", замітки за лекціями Принстонського університету (PDF). Архів (PDF) оригіналу за 29 серпня 2017. Процитовано 29 липня 2018.
- ↑ Математична лабораторія ім. Чебишова, курс лекцій «Адитивна комбінаторика», лекція 3 (рос.)
- ↑ а б И. Д. Шкредов, "Теорема Семереди и задачи об арифметических прогрессиях". Архів оригіналу за 24 липня 2018. Процитовано 29 липня 2018.
- ↑ N. Alon, R. A. Duke, H. Lefmann, V. Rodl, R. Yusterk, "The Algorithmic Aspects of the Regularity Lemma", Tel Aviv University (PDF). Архів (PDF) оригіналу за 8 серпня 2017. Процитовано 29 липня 2018.
- ↑ W. T. Gowers, "Lower bounds of tower type for Szemerédi's uniformity lemma", Geometric & Functional Analysis GAFA, May 1997, Volume 7, Issue 2, pp 322–337. Архів оригіналу за 18 червня 2018. Процитовано 29 липня 2018.
- ↑ W. T. Gowers, "Hypergraph regularity and the multidimensional Szemer´edi theorem", Annals of Mathematics, 166 (2007), 897–946 (PDF). Архів (PDF) оригіналу за 20 липня 2018. Процитовано 29 липня 2018.
- ↑ Y. Kohayakawa, "Szemerédi’s Regularity Lemma for Sparse Graphs". Архів оригіналу за 10 червня 2018. Процитовано 29 липня 2018.
- ↑ Janos Komlos, Miklos Simonovits, "Szemeredi's Regularity Lemma and its applications in graph theory", Rutgers University, Hungarian Academy of Sciences (PDF). Архів (PDF) оригіналу за 23 квітня 2005. Процитовано 29 липня 2018.