Лема регулярності Семереді

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

Неформально кажучи, лема стверджує наявність багатьох великих псевдовипадкових структур у будь-якому графі досить великого розміру.

Лему довів Ендре Семереді 1975 році.

Формулювання

Поняття ε-рівномірності

Підрахунок ребер показує, що цей граф може бути $\varepsilon$-регулярним тільки для $\varepsilon >{\frac {7}{50}}$ (така оцінка доречна в цьому випадку лише тому що $|S|>|T|>{\frac {7}{50}}|V|={\frac {7}{50}}|U|$)

Нехай дано двочастковий граф $G=(W=U\sqcup V,E)$, ребра якого з'єднують вершини зі множини $U$ з вершинами зі множини $V$.

Для $S\subset U,T\subset V$ позначимо через $d(S,T)$ щільність розподілу ребер між цими множинами, тобто

$d(S,T)={\frac {\#\left\lbrace {(u,v)\in E:u\in S,v\in T}\right\rbrace }{|S||T|}}$.

Визначення Двочастковий граф $G=(U\sqcup V,E)$ називають $\varepsilon$-рівномірним якщо для будь-яких $S\subset U,T\subset V$, що задовольняють умови $|S|>\varepsilon |U|,|T|>\varepsilon |V|$, виконується нерівність $|d(S,T)-d(U,V)|\leq \varepsilon$

Існує кілька еквівалентних цьому визначень (еквівалентних у сенсі існування монотонної залежності $\varepsilon$ в одному визначенні від $\varepsilon$ в іншому за еквівалентності двох визначень), але всі вони використовують величину $d(S,T)$ і якесь кількісне порівняння її значень для різних пар $S,T$.

Очевидно, що повний і порожній двочасткові графи є $\varepsilon$-регулярними для будь-якого $\varepsilon >0$. Слід зазначити, що це, взагалі кажучи, не так для довільного регулярного в звичайному сенсі двочасткового графа (як контрприклад можна розглянути об'єднання кількох неперетинних за множиною вершин регулярних графів).

$\varepsilon$-Рівномірні графи за даного $\varepsilon$ іноді також називають псевдовипадковими, оскільки за рівномірністю розподілу ребер між вершинами вони схожі на згенеровані випадково.

Формулювання леми

Тричастковий граф із випадковими наборами ребер різної щільності між частками (для червоних ребер — $0,8$, для зелених — $0,5$ для синіх — $0,25$). Між компонентами розбиття з теореми Семереді утворюються схожі конфігурації ребер, оскільки $\varepsilon$-регулярні графи схожі на випадкові.

Лема регулярності Семереді Для будь-яких $\varepsilon >0,\ m\geq 2$ існують $M,n_{0}$ такі, що для будь-якого графа $G=(V,E)$ з кількістю вершин $|V|>n_{0}$ існує розбиття $V=V_{1}\sqcup \dots \sqcup V_{k}\ (m\leq k\leq M)$ на максимально можливо рівні за розміром частки $|V_{1}|=\dots =|V_{k-1}|\geq |V_{k}|$ такі, що для $(1-\varepsilon ){\binom {k}{2}}$ із пар цих часток двочастковий граф із ребер, що пролягають між ними, є $\varepsilon$-регулярним.

Зауваження

Лема не накладає жодних обмежень на ребра між вершинами з однієї й тієї ж множини розбиття.

Твердження леми нетривіальне тільки для графів із досить великим числом ребер. Якщо $|E|\leq {\frac {\varepsilon ^{3}}{k^{2}}}|V|^{2}$, то будь-який його двочастковий підграф на частках із розмірами ${\frac {\varepsilon }{k}}|V|$ також виявиться розрідженим (його щільність не перевищуватиме $\varepsilon$) — отже, умова на різницю щільностей виконуватиметься завжди.

Слід також зазначити, що згадка однієї й тієї ж змінної $\varepsilon$ у двох різних характеристиках — показнику регулярності та частці $\varepsilon$-регулярних двочасткових підграфів — не створює жодного додаткового зв'язку між цими характеристиками. Таке формулювання випливало б і з ослабленішого формулювання, де потрібно, наприклад, щоб $\varepsilon$-регулярно були розподілені ребра тільки між $(1-\eta ){\binom {k}{2}}$ парами множин, де $\eta =\eta (\varepsilon )\to 0$ при $\varepsilon \to 0$ (тобто навіть за $\eta >\varepsilon$). У такому разі для досягнення початкового формулювання достатньо було б розглянути $\varepsilon _{0}=\eta ^{-1}(\varepsilon )$, оскільки $\varepsilon _{0}$-регулярність графа тягне за собою $\varepsilon$-регулярність при $\varepsilon _{0}<\varepsilon$.

Доведення

Алгоритм розбиття

Розбиття проводиться жадібним алгоритмом.

Спочатку вибирається довільне розбиття вершин на множини $V_{1},\dots ,V_{k}$, де:

• $|V_{1}|=\dots =|V_{k-1}|>|V_{k}|$
• $k=\max \left({{\frac {1}{\varepsilon }},m}\right)$

Далі на кожній ітерації алгоритму з наявного розбиття певним чином генерується нове розбиття з меншими розмірами часток і більшою кількістю. Воно будується як підрозбиття початкового розбиття, але потім нормалізується невеликими перебудовами, щоб розміри всіх (крім, можливо, однієї) часток виявилися рівними.

Таке перетворення триває, поки в розбитті на $k'$ множин залишається хоча б $\varepsilon {\binom {k'}{2}}$ пар множин, двочасткові графи між якими не $\varepsilon$-регулярні. Перехід від одного розбиття до наступного відбувається так, що можна довести, що алгоритм точно зупиниться за скінченне та обмежене сталою (залежною від $\varepsilon$ і $m$) число кроків. Крім того, кількість отриманих множин у розбитті на кожній конкретній ітерації алгоритму також обмежена, так що найбільша кількість множин, яка може утворитися на останній ітерації, і буде шуканою величиною $M$.

Перехід від розбиття до підрозбиття

Нехай поточне розбиття ${\mathcal {P}}=(V_{1},\dots ,V_{k})$ не задовольняє умову леми, тобто є $\varepsilon {\binom {k}{2}}$ пар $(V_{i},V_{j}),i\not =j$, для яких двочастковий граф між ними не $\varepsilon$-регулярний. Позначимо цю умову, як $P_{\varepsilon }(V_{i},V_{j})$.

Якщо $P_{\varepsilon }(V_{i},V_{j})$, то існують якісь конкретні «проблемні» підмножини $S_{ij}\in V_{i},S_{ji}\in V_{j}$, що порушують $\varepsilon$-регулярність двочасткового графа, який з'єднує ці компоненти. Тобто для них виконано:

• $|S_{ij}|>\varepsilon |V_{i}|$
• $|S_{ji}|>\varepsilon |V_{j}|$
• $|d(S_{ij},S_{ji})-d(V_{i},V_{j})|>\varepsilon$

Розумно виглядає ідея позбавиться цих проблемних підмножин, просто виділивши їх у окрему компоненту, утворивши замість пари компонент $(V_{i},V_{j})$ четвірку $(S_{ij},V_{i}\setminus S_{ij},S_{ji},V_{j}\setminus S_{ji})$. Однак одна й та ж компонента $V_{i}$ може конфліктувати відразу з декількома іншими компонентами, так що розбиття слід проводити не за однією, а одразу за кількома проблемними множинами.

Щоб формалізувати цей процес, для кожної окремої компоненти $V_{i}$ розглядають усі «проблемні» підмножини, що виникають у ній:

${\mathcal {S}}(V_{i})=\left\lbrace {S_{ij}:1\leq j\leq k,P_{\varepsilon }(V_{i},V_{j})}\right\rbrace$

та σ-алгебру, утворену ${\mathcal {S}}(V_{i})$ на $V_{i}$ (тобто $V_{i}$ підрозбивається на такі частини, щоб будь-які дві вершини, одна з яких належить деякому $S_{ij}$, а інша йому не належить, опинилися в різних частинах підрозбиття).

Оскільки для окремого $V_{i}$ існує не більше $k-1$ проблемних підмножин (і, отже, не більше $2^{k-1}$ елементів побудованої на них σ-алгебри), то в результаті з однієї компоненти утворюється не більше $2^{k-1}$ нових.

Якщо підрозбити в такий спосіб кожну компоненту $V_{i}$, то вийде нове підрозбиття ${\mathcal {P}}'$.

Далі в ${\mathcal {P}}'$ треба вирівняти розміри компонент (яких у ньому всього не більше $k2^{k-1}$). Для цього кожну його компоненту можна розділити на нові компоненти розміру $\left\lfloor {\frac {n}{{(k2^{k-1})}^{2}}}\right\rfloor$ (і, можливо, одну компоненту меншого розміру — «залишок»), а всі вершини з «залишків» з'єднати довільно в нові компоненти того ж розміру $\left\lfloor {\frac {n}{{(k2^{k-1})}^{2}}}\right\rfloor$ і, можливо, одну компоненту меншого розміру.

Розбиття, що вийшло, і буде результатом однієї ітерації алгоритму.

Оцінка кількості кроків алгоритму

Доведення зупинки алгоритму після скінченного числа кроків проводиться через уведення потенціальної функції — чисельної величини, що залежить від поточного розбиття — і відстеження її зміни при зміні ітерацій алгоритму.

«Потенціал» можна визначити, наприклад, так:

$\Phi ({\mathcal {P}})=\sum \limits _{1\leq i<j\leq |{\mathcal {P}}|}{{\frac {|V_{i}||V_{j}|}{|V|^{2}}}d(V_{i},V_{j})^{2}}$

Ця функція має низку важливих властивостей:

• $0\leq \Phi ({\mathcal {P}})\leq 1$

• якщо розбиття ${\mathcal {Q}}$ утворено з ${\mathcal {P}}=(V_{1},\dots ,V_{k})$ підрозбиттям однієї компоненти $V_{1}$ на дві множини $S\subset V_{1}$ і $V_{1}\setminus S$, то $\Phi ({\mathcal {Q}})\geq \Phi ({\mathcal {P}})$

Доведення

Це випливає з нерівності $(x+y)^{2}\leq {\frac {1}{\alpha }}x^{2}+{\frac {1}{\beta }}y^{2}$, істинної при $\alpha +\beta =1$, яка тягне за собою нерівність

${\frac {E(V_{1},V_{j})^{2}}{|V_{1}|}}\leq {\frac {E(S,V_{j})^{2}}{|S|}}+{\frac {E(V_{1}\setminus S,V_{j})^{2}}{|V_{1}\setminus S|}}$

• для розбиття ${\mathcal {P}}'$ з алгоритму, описаного в попередньому розділі, виконується нерівність$\Phi ({\mathcal {P}}')>\Phi ({\mathcal {P}})+\Omega (\varepsilon ^{5})$

• якщо розбиття ${\mathcal {Q}}$ отримано з розбиття ${\mathcal {P}}=(V_{1},\dots ,V_{k})$ перерозподілом вершин кількох компонент $V_{1},\dots ,V_{s}$ на якісь інші компоненти (не обов'язково підрозбиттям), то $\Phi ({\mathcal {Q}})\geq \Phi ({\mathcal {P}})-{\frac {|V_{1}|+\dots +|V_{s}|}{|V|}}$

Доведення

Достатньо показати, що об'єднання $V_{1},\dots ,V_{s}$ зменшує $\Phi$ не більш, ніж на ${\frac {|V_{1}|+\dots +|V_{s}|}{|V|}}$ (подальше підрозбиття не зменшує $\Phi$, згідно з другою властивістю).

При об'єднанні компонент із суми $\Phi$ зникають деякі доданки та з'являються якісь нові. Оскільки всі доданки додатні, досить розглянути ті, які зникають. Суму таких доданків легко оцінити:

$\sum \limits _{i=1}^{s}{\sum \limits _{j>i}{{\frac {|V_{i}||V_{j}|}{|V|^{2}}}d(V_{i},V_{j})}}\leq \sum \limits _{i=1}^{s}{|V_{i}|\sum \limits _{j>i}{\frac {|V_{j}|}{|V|^{2}}}}\leq {\frac {1}{|V|^{2}}}\sum \limits _{i=1}^{s}{|V_{i}|\sum \limits _{j=1}^{k}{|V_{j}|}}={\frac {|V_{1}|+\dots +|V_{s}|}{|V|}}$

Оскільки при отриманні нового розбиття згідно з алгоритмом у підрозбитті ${\mathcal {P}}'$ перебудовується не більше ніж $k2^{k-1}\left\lfloor {\frac {n}{{(k2^{k-1})}^{2}}}\right\rfloor \leq {\frac {n}{k2^{k-1}}}$ вершин і оскільки ${\frac {1}{k2^{k-1}}}<c\varepsilon ^{5}$ за досить великих $k$ для будь-якої константи $c$, то зі властивостей потенціальної функції випливає, що алгоритм зупиниться через $O\left({\frac {1}{\varepsilon ^{5}}}\right)$ кроків.

У першій праці на цю тему Семереді використав дещо іншу функцію потенціалу:

$\Phi ({\mathcal {P}})={\frac {1}{|{\mathcal {P}}|^{2}}}\sum \limits _{1\leq i<j\leq |{\mathcal {P}}|}{d(V_{i},V_{j})^{2}}$

Попри відмінності, обидві функції об'єднує ідея усереднення квадратів щільностей.

Оцінка розміру розбиття

Як випливає з опису алгоритму, верхня оцінка кількості компонент у розбитті на $n$-й ітерації алгоритму виражається рекурентним співвідношенням

$a_{n}={a_{n}}^{2}2^{a_{n}-1}$

Кількість ітерацій, що пропрацює алгоритм, оцінюється як $O\left({\frac {1}{\varepsilon ^{5}}}\right)$.

Отже, підсумкову кількість компонент можна оцінити лише вежею з піднесень до степеня $2^{2^{\cdot ^{\cdot ^{\cdot ^{k}}}}}$ висоти $O\left({\frac {1}{\varepsilon ^{5}}}\right)$.

Ефективний алгоритм пошуку розбиття

Типове математичне доведення леми Семереді не дбає про обчислювальну складність алгоритму.

Однак група з п'яти математиків у окремій праці дослідила алгоритмічний аспект пошуку потрібного розбиття — зокрема вони описали алгоритм, що дозволяє знайти розбиття $n$-вершинного графа за час $O(n^{2.376})$ за фіксованих $\varepsilon$ і $m$. Час роботи їхнього алгоритму обмежено часом множення двох матриць $n\times n$, що складаються з нулів та одиниць. Також алгоритм можна розпаралелити і виконати за час $O(\log {n})$ на поліноміально залежному від $n$ числі процесорів.

Нижня оцінка розміру шуканого розбиття

1997 року Вільям Гауерс показав, що оцінку розміру кількості компонент у шуканому розбитті не можна покращити більш, ніж до вежі степенів $2^{2^{\cdot ^{\cdot ^{\cdot ^{k}}}}}$ висоти $O\left({\log {\left({\frac {1}{\varepsilon }}\right)}}\right)$. А саме він показав, що завжди існує граф, будь-яке розбиття якого на меншу кількість частин не задовольняє умов леми.

Він розглянув навіть узагальнене поняття $(\varepsilon ,\delta )$ -регулярності, де на підмножину часток двочасткового графа $S\subset U,T\subset V$, відхилення щільності якої обмежується визначенням, накладаються обмеження $|S|\geq \delta |U|,|T|\geq \delta |V|$ замість $|S|\geq \varepsilon |U|,|T|\geq \varepsilon |V|$, і для нього також довів існування контрприкладу.

Для пошуку контрприкладу Гауерс використав імовірнісний метод, тому його доведення неконструктивне. У роботі розглянуто зважені графи з вагами з інтервалу $(0;1)$. Для таких графів можна розглядати повністю аналогічне формулювання леми, де як щільність $d(U,V)$ буде розглядатися сума ваг ребер, замість їхньої кількості. Побудувавши контрприклад у вигляді зваженого графа, Гауерс також показав, що випадковий граф, який генерується за схемою Бернуллі, з імовірностями ребер, що відповідають вагам у цьому зваженому графі, з великою ймовірністю буде контрприкладом для звичайної леми (більш того, з великою ймовірністю щільності $d(U,V)$ будуть не сильно відхилятися від аналогічних щільностей у зваженому графі за умови, що $|U|$ і $|V|$ достатньо великі).

Побудова Гауерса  

Ілюстрація типу структури графа, який Гауерс використав для побудови контрприкладу. Для зручності кількість блоків $B_{i}$ (на малюнку вони візуально віддалені один від одного) і розмір груп вибрано рівними трьом. Зверніть увагу, що в кожному двочастковому підграфі, що утворюється між блоками, вершини одного кольору, розташовані поруч, завжди потрапляють в одну частку - це і є групи $X_{i}$, в які попередньо об'єднано вершини. При побудові наступного графа в одну таку групу об'єднаються вершини кожного окремого блоку.

Зважений граф, який є контрприкладом для леми зі звичайним визначенням $\varepsilon$-регулярності, будується як комбінація з різними вагами кількох специфічно влаштованих великих графів. При побудові кожного наступного графа з цього набору вершини об'єднуються у все більші й більші групи рівного розміру такі, що вершини з двох різних груп або з'єднуються між собою повним двочастковим графом, або взагалі не з'єднуються (нові групи завжди є об'єднанням попередніх).

Нехай вершини розбито на групи $X_{1},\dots ,X_{s}$ однакового розміру. Об'єднаємо ці групи в блоки

$B_{1}=(X_{1},\dots ,X_{t})$

$B_{2}=(X_{t+1},\dots ,X_{2t})$

$\dots$

$B_{k}=(X_{(m-1)t+1},\dots ,X_{s})$,

де $k={\frac {s}{t}}$ (вважаємо, що це - ціле число).

Для кожної пари різних блоків $(B_{i},B_{j})$ виберемо розбиття $B_{i}=B_{ij}^{(1)}\sqcup B_{ij}^{(2)}$ груп із $B_{i}$ на дві частини та розбиття $B_{j}=B_{ji}^{(1)}\sqcup B_{ji}^{(2)}$ груп із $B_{j}$ на дві частини. Додамо в граф усі ребра повних двочасткових графів $(B_{ij}^{(1)},B_{ji}^{(1)})$ і $(B_{ij}^{(2)},B_{ji}^{(2)})$.

Якщо вибирати розбиття так, щоб у будь-яких $X_{j},X_{j'}$, що належать одному $B_{i}$, було не більше ${\frac {3}{4}}k$ блоків, у яких є вершини, суміжні їм обом, то за правильного добору $s$ і $t$ конструкція, що вийшла, і буде конструкцією Гауерса. Але це конструкція лише одного графа – для побудови наступного графа блоки $B_{1},\dots ,B_{m}$ ставляться на місце груп $X_{1},\dots ,X_{s}$ і весь процес починається спочатку, поки всі вершини не буде об'єднано в одну групу.

Отриманий ланцюжок графів $G_{1},\dots ,G_{s}$ об'єднується у зважений граф за формулою $G=\sum \limits _{r=1}^{s}{2^{r-s-1}G_{r}}$ (найбільші ваги мають графи, в яких об'єднані групи вершин дуже великі).

Контрприклад для $(\varepsilon ,\delta )$-регулярності будується в схожий спосіб, але з кількома відмінностями:

• групи всередині одного блока $B_{i}$ розбиваються не на два, на довільне число $d$ наборів $B_{i}=B_{i}^{(1)}\sqcup \dots \sqcup B_{i}^{(d)}$;

• на кількість груп у кожному наборі $B_{i}^{(j)}$ накладаються обмеження за розміром (вони не повинні бути надто малими);

• в кінці отримані графи $G_{1},\dots ,G_{s}$ об'єднують не у вигляді зваженого графа, а виключним «або» (до підсумкового графа входять лише ті ребра, які були наявні в непарній кількості графів $G_{r},1\leq r\leq s$).

Узагальнення

2007 року Вільям Гауерс узагальнив лему регулярності на гіперграфи та використав узагальнення для доведення багатовимірної теореми Семереді.

Існує також аналог леми Семереді для розріджених графів (у звичайному формулюванні лема є тривіальною для таких графів, оскільки будь-яке розбиття задовольняє потрібні умови).

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

Найвідоміше застосування леми регулярності для комбінаторного доведення теореми Семереді та її узагальнень (наприклад, теореми про кутики). Однак лема та її ідеї мають низку застосувань і в загальній теорії графів — першу статтю Семереді про цю лему процитовано більш ніж у 500 працях на різні теми.

Також окремий інтерес становить лема про видалення трикутників, яка виводиться з леми регулярності і використовується під час доведення теореми Семереді.

Див. також

• Ендре Семереді
• Теорема Семереді
• Лема про видалення трикутників