Перегляд вихідного коду сторінки Лема регулярності Семереді

'''Лема регулярності Семереді'''&nbsp;— лема із загальної [[Теорія графів|теорії графів]], яка стверджує, що вершини будь-якого досить великого [[Граф (математика)|графа]] можна розбити на скінченне число таких груп, що майже у всіх [[Двочастковий граф|двочасткових графах]], що з'єднують вершини з двох різних груп, ребра розподілені між вершинами майже рівномірно. При цьому найменша необхідна кількість груп, на які потрібно розбити множину вершин графа, може бути як завгодно великою, але кількість груп у розбитті завжди обмежена зверху.

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

Лему довів [[Ендре Семереді]] 1975 році<ref name="Szemeredi first">[https://www.researchgate.net/publication/235058342_Regular_Partitions_of_Graphs E. Szemeredi, «Regular partitions of graphs», Computer science department, School of Humanities and Sciences, Stanford University, 1975]</ref><ref>{{Cite web|url=http://i.stanford.edu/pub/cstr/reports/cs/tr/75/489/CS-TR-75-489.pdf|title=E. Szemeredi, "Regular partitions of graphs", Computer science department, School of Humanities and Sciences, Stanford University, 1975|accessdate=2018-07-29|archivedate=2020-02-23|archiveurl=https://web.archive.org/web/20200223014425/http://i.stanford.edu/pub/cstr/reports/cs/tr/75/489/CS-TR-75-489.pdf|deadurl=no}}</ref>.

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

=== Поняття ε-рівномірності ===
[[Файл:Epsilon-regularity.png|міні| Підрахунок ребер показує, що цей граф може бути <math>\varepsilon</math>-регулярним тільки для <math>\varepsilon > \frac{7}{50}</math> (така оцінка доречна в цьому випадку лише тому що <math>|S| > |T| > \frac{7}{50} |V| = \frac{7}{50} |U|</math>)]]
Нехай дано [[двочастковий граф]] <math>G = (W = U \sqcup V,E)</math>, ребра якого з'єднують вершини зі множини <math>U</math> з вершинами зі множини <math>V</math>.

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

: <math>d(S,T) = \frac{\#\left\lbrace{(u, v) \in E : u \in S, v \in T}\right\rbrace}{|S| |T|}</math>.
{{Рамка}}
'''Визначення'''<ref name="Szemeredi first" /><ref name="Prinston">{{Cite web |url=https://www.math.cmu.edu/~af1p/Teaching/AdditiveCombinatorics/allnotes.pdf |title="Mini course of additive combinatorics", замітки за лекціями Принстонського університету |access-date=2018-07-29 |archive-date=2017-08-29 |archive-url=https://web.archive.org/web/20170829160603/http://www.math.cmu.edu/~af1p/Teaching/AdditiveCombinatorics/allnotes.pdf |deadlink=no }}</ref>

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

: <math>|d(S,T) - d(U,V)| \le \varepsilon</math>
{{/рамка}}Існує кілька еквівалентних цьому визначень (еквівалентних у сенсі існування монотонної залежності <math>\varepsilon</math> в одному визначенні від <math>\varepsilon</math> в іншому за еквівалентності двох визначень), але всі вони використовують величину <math>d(S,T)</math> і якесь кількісне порівняння її значень для різних пар <math>S,T</math>.

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

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

=== Формулювання леми ===
[[Файл:3-partite_graph_with_difference_density.png|міні|400x400пкс| Тричастковий граф із випадковими наборами ребер різної щільності між частками (для червоних ребер&nbsp;— <math>0,8</math>, для зелених&nbsp;— <math>0,5</math> для синіх&nbsp;— <math>0,25</math>). Між компонентами розбиття з [[Теорема Семереді|теореми Семереді]] утворюються схожі конфігурації ребер, оскільки <math>\varepsilon</math>-регулярні графи схожі на випадкові.]]
{{Рамка}}
'''Лема регулярності Семереді'''<ref name="Prinston" /><ref>[https://youtube.com/watch?v=SaFBAlG5FMY&t=1726 Математична лабораторія ім. Чебишова, курс лекцій «Адитивна комбінаторика», лекція 3] {{ref-ru}}</ref>

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

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

Твердження леми нетривіальне тільки для графів із досить великим числом ребер. Якщо <math>|E| \le \frac{\varepsilon^3}{k^2} |V|^2</math>, то будь-який його двочастковий підграф на частках із розмірами <math>\frac{\varepsilon}{k} |V|</math> також виявиться розрідженим (його щільність не перевищуватиме <math>\varepsilon</math>)&nbsp;— отже, умова на різницю щільностей виконуватиметься завжди<ref name="Shkredov">{{Cite web|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=5293&option_lang=rus|title=И. Д. Шкредов, "Теорема Семереди и задачи об арифметических прогрессиях"|accessdate=2018-07-29|archivedate=2018-07-24|archiveurl=https://web.archive.org/web/20180724175742/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=5293&option_lang=rus|deadurl=no}}</ref>.

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

== Доведення ==

=== Алгоритм розбиття ===
Розбиття проводиться [[Жадібний алгоритм|жадібним алгоритмом]].

Спочатку вибирається довільне розбиття вершин на множини <math>V_1,\dots,V_k</math>, де:

* <math>|V_1|=\dots=|V_{k-1}|>|V_k|</math>
* <math>k=\max\left({\frac{1}{\varepsilon}, m}\right)</math>

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

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

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

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

* <math>|S_{ij}| > \varepsilon |V_i|</math>
* <math>|S_{ji}| > \varepsilon |V_j|</math>
* <math>|d(S_{ij},S_{ji}) - d(V_i,V_j)| > \varepsilon</math>

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

Щоб формалізувати цей процес, для кожної окремої компоненти <math>V_i</math> розглядають усі «проблемні» підмножини, що виникають у ній:

: <math>{\mathcal S}(V_i) = \left\lbrace{S_{ij} : 1 \le j \le k, P_{\varepsilon}(V_i,V_j)}\right\rbrace</math>

та [[Сигма-алгебра|σ-алгебру]], утворену <math>{\mathcal S}(V_i)</math> на <math>V_i</math> (тобто <math>V_i</math> підрозбивається на такі частини, щоб будь-які дві вершини, одна з яких належить деякому <math>S_{ij}</math>, а інша йому не належить, опинилися в різних частинах підрозбиття).

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

Якщо підрозбити в такий спосіб кожну компоненту <math>V_i</math>, то вийде нове підрозбиття <math>{\mathcal P}'</math>.

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

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

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

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

: <math>\Phi({\mathcal P}) = \sum \limits_{1 \le i < j \le |{\mathcal P}|} {\frac{|V_i||V_j|}{|V|^2} d(V_i, V_j)^2}</math>

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

* <math>0 \le \Phi({\mathcal P}) \le 1</math>

* якщо розбиття <math>{\mathcal Q}</math> утворено з <math>{\mathcal P}=(V_1,\dots,V_k)</math> підрозбиттям однієї компоненти <math>V_1</math> на дві множини <math>S \subset V_1</math> і <math>V_1 \setminus S</math>, то <math>\Phi({\mathcal Q}) \ge \Phi({\mathcal P})</math>
{{Hidden|title=Доведення|content=Це випливає з нерівності <math>(x+y)^2 \le \frac{1}{\alpha} x^2 + \frac{1}{\beta} y^2</math>, істинної при <math>\alpha+\beta=1</math>, яка тягне за собою нерівність

:<math>\frac{E(V_1,V_j)^2}{|V_1|} \le \frac{E(S,V_j)^2}{|S|} + \frac{E(V_1 \setminus S,V_j)^2}{|V_1 \setminus S|}</math>}}

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

* якщо розбиття <math>{\mathcal Q}</math> отримано з розбиття <math>{\mathcal P}=(V_1,\dots,V_k)</math> перерозподілом вершин кількох компонент <math>V_1,\dots,V_s</math> на якісь інші компоненти (не обов'язково підрозбиттям), то <math>\Phi({\mathcal Q}) \ge \Phi({\mathcal P}) - \frac{|V_1|+\dots+|V_s|}{|V|}</math>
{{Hidden|title=Доведення|content=Достатньо показати, що об'єднання <math>V_1,\dots,V_s</math> зменшує <math>\Phi</math> не більш, ніж на <math>\frac{|V_1|+\dots+|V_s|}{|V|}</math> (подальше підрозбиття не зменшує <math>\Phi</math>, згідно з другою властивістю).

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

<math>\sum \limits_{i=1}^{s} {\sum \limits_{j>i} {\frac{|V_i||V_j|}{|V|^2} d(V_i,V_j)}} \le \sum \limits_{i=1}^{s} {|V_i| \sum \limits_{j>i} {\frac{|V_j|}{|V|^2}}} \le \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|}</math>}}

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

У першій праці на цю тему Семереді використав дещо іншу функцію потенціалу<ref name="Szemeredi first"/>:

: <math>\Phi({\mathcal P}) = \frac{1}{|{\mathcal P}|^2} \sum \limits_{1 \le i < j \le |{\mathcal P}|} {d(V_i,V_j)^2}</math>

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

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

: <math>a_n = {a_n}^2 2^{a_n-1}</math>

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

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

== Ефективний алгоритм пошуку розбиття ==
Типове математичне доведення леми Семереді не дбає про [[Обчислювальна складність|обчислювальну складність]] алгоритму.

Однак група з п'яти математиків у окремій праці дослідила алгоритмічний аспект пошуку потрібного розбиття&nbsp;— зокрема вони описали алгоритм, що дозволяє знайти розбиття <math>n</math>-вершинного графа за час <math>O(n^{2.376})</math> за фіксованих <math>\varepsilon</math> і <math>m</math>. Час роботи їхнього алгоритму обмежено часом множення двох матриць <math>n \times n</math>, що складаються з нулів та одиниць. Також алгоритм можна [[Рівночасні обчислення|розпаралелити]] і виконати за час <math>O(\log{n})</math> на поліноміально залежному від <math>n</math> числі процесорів<ref>{{Cite web|url=https://www.tau.ac.il/~nogaa/PDFS/reg5.pdf|title=N. Alon, R. A. Duke, H. Lefmann, V. Rodl, R. Yusterk, "The Algorithmic Aspects of the Regularity Lemma", Tel Aviv University|accessdate=2018-07-29|archivedate=2017-08-08|archiveurl=https://web.archive.org/web/20170808025149/http://www.tau.ac.il/~nogaa/PDFS/reg5.pdf|deadurl=no}}</ref>.

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

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

Для пошуку контрприкладу Гауерс використав [[імовірнісний метод]], тому його доведення [[Неконструктивне доведення|неконструктивне]]. У роботі розглянуто [[Словник термінів теорії графів#З|зважені графи]] з вагами з інтервалу <math>(0;1)</math>. Для таких графів можна розглядати повністю аналогічне формулювання леми, де як щільність <math>d(U,V)</math> буде розглядатися сума ваг ребер, замість їхньої кількості. Побудувавши контрприклад у вигляді зваженого графа, Гауерс також показав, що випадковий граф, який генерується за [[Зсув Бернуллі|схемою Бернуллі]], з імовірностями ребер, що відповідають вагам у цьому зваженому графі, з великою ймовірністю буде контрприкладом для звичайної леми (більш того, з великою ймовірністю щільності <math>d(U,V)</math> будуть не сильно відхилятися від аналогічних щільностей у зваженому графі за умови, що <math>|U|</math> і <math>|V|</math> достатньо великі)<ref>{{Cite web|url=https://link.springer.com/article/10.1007%2FPL00001621|title=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|accessdate=2018-07-29|archivedate=2018-06-18|archiveurl=https://web.archive.org/web/20180618134803/https://link.springer.com/article/10.1007%2FPL00001621|deadurl=no}}</ref>.

{{Hider|
  title = Побудова Гауерса|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =

[[File:Gowers construction for lower bound of Szemeredi regularity lemma.gif|thumb|500px|Ілюстрація типу структури графа, який Гауерс використав для побудови контрприкладу. Для зручності кількість блоків <math>B_i</math> (на малюнку вони візуально віддалені один від одного) і розмір груп вибрано рівними трьом. Зверніть увагу, що в кожному двочастковому підграфі, що утворюється між блоками, вершини одного кольору, розташовані поруч, завжди потрапляють в одну частку - це і є групи <math>X_i</math>, в які попередньо об'єднано вершини. При побудові наступного графа в одну таку групу об'єднаються вершини кожного окремого блоку.]]

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

Нехай вершини розбито на групи <math>X_1,\dots,X_s</math> однакового розміру. Об'єднаємо ці групи в блоки

: <math>B_1=(X_1,\dots,X_t)</math>
: <math>B_2=(X_{t+1},\dots,X_{2t})</math>
: <math>\dots</math>
: <math>B_k=(X_{(m-1)t+1},\dots,X_{s})</math>,

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

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

Якщо вибирати розбиття так, щоб у будь-яких <math>X_j, X_{j'}</math>, що належать одному <math>B_i</math>, було не більше <math>\frac{3}{4}k</math> блоків, у яких є вершини, суміжні їм обом, то за правильного добору <math>s</math> і <math>t</math> конструкція, що вийшла, і буде конструкцією Гауерса. Але це конструкція лише одного графа – для побудови наступного графа блоки <math>B_1,\dots,B_m</math> ставляться на місце груп <math>X_1,\dots,X_s</math> і весь процес починається спочатку, поки всі вершини не буде об'єднано в одну групу.

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

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

* групи всередині одного блока <math>B_i</math> розбиваються не на два, на довільне число <math>d</math> наборів <math>B_i=B_i^{(1)} \sqcup \dots \sqcup B_i^{(d)}</math>;

* на кількість груп у кожному наборі <math>B_i^{(j)}</math> накладаються обмеження за розміром (вони не повинні бути надто малими);

* в кінці отримані графи <math>G_1,\dots,G_s</math> об'єднують не у вигляді зваженого графа, а [[Виключна диз'юнкція|виключним «або»]] (до підсумкового графа входять лише ті ребра, які були наявні в непарній кількості графів <math>G_r, 1 \le r \le s</math>).
}}

== Узагальнення ==
2007 року Вільям Гауерс узагальнив лему регулярності на гіперграфи та використав узагальнення для доведення багатовимірної [[Теорема Семереді|теореми Семереді]]<ref>{{Cite web|url=http://annals.math.princeton.edu/wp-content/uploads/annals-v166-n3-p07.pdf|title=W. T. Gowers, "Hypergraph regularity and the multidimensional Szemer´edi theorem", Annals of Mathematics, 166 (2007), 897–946|accessdate=2018-07-29|archivedate=2018-07-20|archiveurl=https://web.archive.org/web/20180720230749/http://annals.math.princeton.edu/wp-content/uploads/annals-v166-n3-p07.pdf|deadurl=no}}</ref>.

Існує також аналог леми Семереді для розріджених графів (у звичайному формулюванні лема є тривіальною для таких графів, оскільки будь-яке розбиття задовольняє потрібні умови)<ref>{{Cite web|url=https://link.springer.com/chapter/10.1007%2F978-3-642-60539-0_16|title=Y. Kohayakawa, "Szemerédi’s Regularity Lemma for Sparse Graphs"|accessdate=2018-07-29|archivedate=2018-06-10|archiveurl=https://web.archive.org/web/20180610143133/https://link.springer.com/chapter/10.1007%2F978-3-642-60539-0_16|deadurl=no}}</ref>.

== Застосування ==
Найвідоміше застосування леми регулярності для комбінаторного доведення [[Теорема Семереді|теореми Семереді]] та її узагальнень (наприклад, [[Теорема про кутики|теореми про кутики]])<ref name="Shkredov"/>. Однак лема та її ідеї мають низку застосувань і в загальній теорії графів<ref>{{Cite web|url=http://www.math.ucsd.edu/~fan/teach/262/read/reg.pdf|title=Janos Komlos, Miklos Simonovits, "Szemeredi's Regularity Lemma and its applications in graph theory", Rutgers University, Hungarian Academy of Sciences|accessdate=2018-07-29|archivedate=2005-04-23|archiveurl=https://web.archive.org/web/20050423204355/http://www.math.ucsd.edu/~fan/teach/262/read/reg.pdf|deadurl=no}}</ref>&nbsp;— першу статтю Семереді про цю лему процитовано більш ніж у 500 працях на різні теми<ref name="Szemeredi first"/>.

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

== Див. також ==
* [[Ендре Семереді]]
* [[Теорема Семереді]]
* [[Лема про видалення трикутників]]

== Примітки ==
{{примітки|2}}
{{Бібліоінформація}}
[[Категорія:Арифметична комбінаторика]]
[[Категорія:Комбінаторика]]
[[Категорія:Теореми теорії графів]]