Лемма Семереди о регулярности - Szemerédi regularity lemma

Края между частями ведут себя «случайным образом».

Семереди лемма о регулярности один из самых мощных инструментов в экстремальная теория графов, особенно при изучении больших плотных графов. В нем говорится, что вершины каждого достаточно большого график может быть разделен на ограниченное количество частей, так что края между разными частями ведут себя почти случайно.

Согласно лемме, независимо от размера графа, мы можем аппроксимировать его плотностями ребер между ограниченным числом частей. Между любыми двумя частями распределение ребер будет псевдослучайным по плотности ребер. Эти аппроксимации обеспечивают по существу правильные значения для различных свойств графа, таких как количество внедренных копий данного подграфа или количество удалений ребер, необходимых для удаления всех копий некоторого подграфа.

Заявление

Чтобы сформулировать лемму Семереди о регулярности формально, мы должны формализовать, что на самом деле означает распределение ребер между частями, ведущими себя «почти случайно». Под «почти случайным» мы подразумеваем понятие, называемое ε-регулярность. Чтобы понять, что это означает, мы сначала дадим несколько определений. В дальнейшем грамм это граф с вершина набор V.

Определение 1. Позволять Икс, Y быть непересекающимися подмножествами V. В плотность края пары (Икс, Y) определяется как:

${\displaystyle d(X,Y):={\frac {\left|E(X,Y)\right|}{|X||Y|}}}$

куда E(Икс, Y) обозначает множество ребер, имеющих одну конечную вершину в Икс и один в Y.

Пары подмножеств обычной пары по плотности краев аналогичны исходной паре.

Назовем пару деталей ε-регулярно, если всякий раз, когда вы берете большое подмножество каждой детали, их плотность краев не слишком сильно отличается от плотности краев пары деталей. Формально,

Определение 2. За ε> 0, пара множеств вершин Икс и Y называется ε-обычный, если для всех подмножеств А ⊆ Икс, B ⊆ Y удовлетворение |А| ≥ ε |Икс|, |B| ≥ ε |Y|, у нас есть

${\displaystyle \left|d(X,Y)-d(A,B)\right|\leq \varepsilon .}$

Естественный способ определить ε-регулярный раздел должен быть таким, в котором каждая пара частей ε-обычный. Однако некоторые графики, такие как половинные графики, требуют, чтобы много пар разделов (но небольшая часть всех пар) были нерегулярными.^[1] Итак, определим ε-регулярные перегородки должны быть такими, в которых находится большинство пар деталей ε-обычный.

Определение 3. Раздел ${\displaystyle V}$ в ${\displaystyle k}$ наборы ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}}$ называется ${\displaystyle \varepsilon }$-регулярная перегородка если

${\displaystyle \sum _{(V_{i},V_{j}){\text{ not }}\varepsilon {\text{-regular}}}|V_{i}||V_{j}|\leq \varepsilon |V(G)|^{2}}$

Теперь мы можем сформулировать лемму:

Лемма Семереди о регулярности. Для каждого ε> 0 и положительный целое число м существует целое число M так что если грамм является графом не менее M вершин существует целое число k В диапазоне м ≤ k ≤ M и ε-регулярное разбиение множества вершин грамм в k наборы.

Граница M поскольку количество частей в разбиении графа, которое дается доказательствами леммы Семереди о регулярности, очень велико, O (ε⁻⁵)-уровневая повторяющаяся экспонента м. Одно время надеялись, что истинная граница будет намного меньше, что могло бы иметь несколько полезных применений. тем не мение Гауэрс (1997) нашел примеры графиков, для которых M действительно растет очень быстро и по крайней мере такой же большой, как ε^−1/16-уровневая повторяющаяся экспонента м. В частности, лучшая граница имеет уровень ровно 4 в Иерархия Гжегорчика, и поэтому не элементарная рекурсивная функция.^[2]

Доказательство

Границы подмножеств, свидетельствующих о нерегулярности, уточняют каждую часть разбиения.

Мы найдем ε-регулярное разбиение для данного графа, следуя алгоритму. Примерный план:

1. Начните с произвольного раздела (может быть всего 1 часть)
2. Пока раздел не является ε-регулярным:
   • Найдите подмножества, свидетельствующие о ε-неоднородности для каждой неправильной пары.
   • Одновременно уточните раздел, используя все наблюдаемые подмножества.

Мы применяем технику, называемую аргумент приращения энергии чтобы показать, что этот процесс завершается после ограниченного числа шагов. По сути, мы определяем моновариант, который должен увеличиваться на определенную величину на каждом шаге, но он ограничен сверху и, следовательно, не может увеличиваться бесконечно. Этот моновариант называется «энергия», поскольку это ${\displaystyle L^{2}}$ количество.

Определение 4. Позволять U, W быть подмножествами V. Набор ${\displaystyle |V|=n}$. В энергия пары (U, W) определяется как:

${\displaystyle q(U,W):={\frac {|U||W|}{n^{2}}}d(U,W)^{2}}$

Для перегородок ${\displaystyle {\mathcal {P}}_{U}=\{U_{1},\ldots ,U_{k}\}}$ из U и ${\displaystyle {\mathcal {P}}_{W}=\{W_{1},\ldots ,W_{l}\}}$ из W, мы определяем энергию как сумму энергий между каждой парой частей:

${\displaystyle q({\mathcal {P}}_{U},{\mathcal {P}}_{W}):=\sum _{i=1}^{k}\sum _{j=1}^{l}q(U_{i},W_{j})}$

Наконец, для раздела ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}}$ из V, определим энергию ${\displaystyle {\mathcal {P}}}$ быть ${\displaystyle q({\mathcal {P}},{\mathcal {P}})}$. Конкретно,

${\displaystyle q({\mathcal {P}})=\sum _{i=1}^{k}\sum _{j=1}^{k}q(V_{i},V_{j})=\sum _{i=1}^{k}\sum _{j=1}^{k}{\frac {|V_{i}||V_{j}|}{n^{2}}}d(V_{i},V_{j})^{2}}$

Обратите внимание, что энергия находится между 0 и 1, потому что плотность краев ограничена сверху единицей:

${\displaystyle q({\mathcal {P}})=\sum _{i=1}^{k}\sum _{j=1}^{k}{\frac {|V_{i}||V_{j}|}{n^{2}}}d(V_{i},V_{j})^{2}\leq \sum _{i=1}^{k}\sum _{j=1}^{k}{\frac {|V_{i}||V_{j}|}{n^{2}}}=1}$

Теперь мы начнем с доказательства того, что энергия не уменьшается при очищении.

Лемма 1. (Энергия не убывает при разбиении) Для любых перегородок ${\displaystyle {\mathcal {P}}_{U}}$ и ${\displaystyle {\mathcal {P}}_{W}}$ наборов вершин ${\displaystyle U}$ и ${\displaystyle W}$, ${\displaystyle q({\mathcal {P}}_{U},{\mathcal {P}}_{W})\geq q(U,W)}$.

Доказательство: Позволять ${\displaystyle {\mathcal {P}}_{U}=\{U_{1},\ldots ,U_{k}\}}$ и ${\displaystyle {\mathcal {P}}_{W}=\{W_{1},\ldots ,W_{l}\}}$. Выбрать вершины ${\displaystyle x}$ равномерно от ${\displaystyle U}$ и ${\displaystyle y}$ равномерно от ${\displaystyle W}$, с ${\displaystyle x}$ частично ${\displaystyle U_{i}}$ и ${\displaystyle y}$ частично ${\displaystyle W_{j}}$. Затем определите случайную величину ${\displaystyle Z=d(U_{i},W_{j})}$. Давайте посмотрим на свойства ${\displaystyle Z}$. Ожидание

${\displaystyle \mathbb {E} [Z]=\sum _{i=1}^{k}\sum _{j=1}^{l}{\frac {|U_{i}|}{|U|}}{\frac {|W_{j}|}{|W|}}d(U_{i},W_{j})={\frac {e(U,W)}{|U||W|}}=d(U,W)}$

Второй момент

${\displaystyle \mathbb {E} [Z^{2}]=\sum _{i=1}^{k}\sum _{j=1}^{l}{\frac {|U_{i}|}{|U|}}{\frac {|W_{j}|}{|W|}}d(U_{i},W_{j})^{2}={\frac {n^{2}}{|U||W|}}q({\mathcal {P}}_{U},{\mathcal {P}}_{W})}$

По выпуклости ${\displaystyle \mathbb {E} [Z^{2}]\geq \mathbb {E} [Z]^{2}}$. Переставляя, получаем ${\displaystyle q({\mathcal {P}}_{U},{\mathcal {P}}_{W})\geq q(U,W)}$ для всех ${\displaystyle U,W}$.${\displaystyle \square }$

Если каждая часть ${\displaystyle {\mathcal {P}}}$ дальнейшее разбиение, новое разбиение называется уточнением ${\displaystyle {\mathcal {P}}}$. Сейчас если ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{m}\}}$, применяя лемму 1 к каждой паре ${\displaystyle (V_{i},V_{j})}$ доказывает, что при каждой изысканности ${\displaystyle {\mathcal {P'}}}$ из ${\displaystyle {\mathcal {P}}}$, ${\displaystyle q({\mathcal {P'}})\geq q({\mathcal {P}})}$. Таким образом, этап уточнения алгоритма не теряет энергии.

Лемма 2. (Лемма о повышении энергии) Если ${\displaystyle (U,W)}$ не является ${\displaystyle \varepsilon }$-регулярно, как засвидетельствовано ${\displaystyle U_{1}\subset U,W_{1}\subset W}$, тогда,

${\displaystyle q\left(\{U_{1},U\backslash U_{1}\},\{W_{1},W\backslash W_{1}\}\right)>q(U,W)+\varepsilon ^{4}{\frac {|U||W|}{n^{2}}}}$

Доказательство: Определять ${\displaystyle Z}$ как указано выше. Потом,

${\displaystyle Var(Z)=\mathbb {E} [Z^{2}]-\mathbb {E} [Z]^{2}={\frac {n^{2}}{|U||W|}}\left(q\left(\{U_{1},U\backslash U_{1}\},\{W_{1},W\backslash W_{1}\}\right)-q(U,W)\right)}$

Но заметьте, что ${\displaystyle |Z-\mathbb {E} [Z]|=|d(U_{1},W_{1})-d(U,W)|}$ с вероятностью ${\displaystyle {\frac {|U_{1}|}{|U|}}{\frac {|W_{1}|}{|W|}}}$(соответствует ${\displaystyle x\in U_{1}}$ и ${\displaystyle y\in W_{1}}$), так

${\displaystyle Var(Z)=\mathbb {E} [(Z-\mathbb {E} [Z])^{2}]\geq {\frac {|U_{1}|}{|U|}}{\frac {|W_{1}|}{|W|}}(d(U_{1},W_{1})-d(U,W))^{2}>\varepsilon \cdot \varepsilon \cdot \varepsilon ^{2}}$ ${\displaystyle \square }$

Теперь мы можем доказать аргумент об увеличении энергии, который показывает, что энергия существенно увеличивается на каждой итерации алгоритма.

Лемма 3. (Лемма об увеличении энергии) Если разбиение ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}}$ из ${\displaystyle V(G)}$ не является ${\displaystyle \varepsilon }$-регулярно, то существует уточнение ${\displaystyle {\mathcal {Q}}}$ из ${\displaystyle {\mathcal {P}}}$ где каждый ${\displaystyle V_{i}}$ делится не более чем на ${\displaystyle 2^{k}}$ такие части, что

${\displaystyle q({\mathcal {Q}})\geq q({\mathcal {P}})+\varepsilon ^{5}.}$

Доказательство: Для всех ${\displaystyle (i,j)}$ такой, что ${\displaystyle (V_{i},V_{j})}$ не является ${\displaystyle \varepsilon }$-регулярный, найти ${\displaystyle A^{i,j}\subset V_{i}}$ и ${\displaystyle A^{j,i}\subset V_{j}}$ которые свидетельствуют о неправильности (сделайте это одновременно для всех неправильных пар). Позволять ${\displaystyle {\mathcal {Q}}}$ быть обычным усовершенствованием ${\displaystyle {\mathcal {P}}}$ к ${\displaystyle A^{i,j}}$с. Каждый ${\displaystyle V_{i}}$ делится не более чем на ${\displaystyle 2^{k}}$ части по желанию. Потом,

${\displaystyle q({\mathcal {Q}})=\sum _{(i,j)\in [k]^{2}}q({\mathcal {Q}}_{V_{i}},{\mathcal {Q}}_{V_{j}})=\sum _{(V_{i},V_{j}){\text{ }}\varepsilon {\text{-regular}}}q({\mathcal {Q}}_{V_{i}},{\mathcal {Q}}_{V_{j}})+\sum _{(V_{i},V_{j}){\text{ not }}\varepsilon {\text{-regular}}}q({\mathcal {Q}}_{V_{i}},{\mathcal {Q}}_{V_{j}})}$

Где ${\displaystyle {\mathcal {Q}}_{V_{i}}}$ это раздел ${\displaystyle V_{i}}$ данный ${\displaystyle {\mathcal {Q}}}$. По лемме 1 указанная величина не меньше

${\displaystyle \sum _{(V_{i},V_{j}){\text{ }}\varepsilon {\text{-regular}}}q(V_{i},V_{j})+\sum _{(V_{i},V_{j}){\text{ not }}\varepsilon {\text{-regular}}}q(\{A^{i,j},V_{i}\backslash A^{i,j}\},\{A^{j,i},V_{j}\backslash A^{j,i}\})}$

С ${\displaystyle V_{i}}$ сокращается ${\displaystyle A^{i,j}}$ при создании ${\displaystyle {\mathcal {Q}}}$, так ${\displaystyle {\mathcal {Q}}_{V_{i}}}$ это уточнение ${\displaystyle \{A^{i,j},V_{i}\backslash A^{i,j}\}}$. По лемме 2 указанная сумма не меньше

${\displaystyle \sum _{(i,j)\in [k]^{2}}q(V_{i},V_{j})+\sum _{(V_{i},V_{j}){\text{ not }}\varepsilon {\text{-regular}}}\varepsilon ^{4}{\frac {|V_{i}||V_{j}|}{n^{2}}}}$

Но вторая сумма не менее ${\displaystyle \varepsilon ^{5}}$ поскольку ${\displaystyle {\mathcal {P}}}$ не является ${\displaystyle \varepsilon }$-регулярно, поэтому выводим искомое неравенство. ${\displaystyle \square }$

Теперь, начиная с любого разбиения, мы можем продолжать применять лемму 3, пока полученное разбиение не ${\displaystyle \varepsilon }$-обычный. Но с каждым шагом энергия увеличивается на ${\displaystyle \varepsilon ^{5}}$, а сверху он ограничен 1. Тогда этот процесс можно повторить не более чем ${\displaystyle \varepsilon ^{-5}}$ раз, прежде чем он закончится, и мы должны иметь ${\displaystyle \varepsilon }$-регулярная перегородка.

Приложения

Если у нас достаточно информации о регулярности графа, мы можем подсчитать количество копий определенного подграфа в графе с точностью до небольшой ошибки.

Лемма о подсчете графов. Позволять ${\displaystyle H}$ быть графом с ${\displaystyle V(H)=[k]}$, и разреши ${\displaystyle \varepsilon >0}$. Позволять ${\displaystyle G}$ быть ${\displaystyle n}$-вершинный граф с множеством вершин ${\displaystyle V_{1},\dots ,V_{k}\subseteq V(G)}$ такой, что ${\displaystyle (V_{i},V_{j})}$ является ${\displaystyle \varepsilon }$-регулярно, когда ${\displaystyle \{i,j\}\in E(H)}$. Затем количество помеченных копий ${\displaystyle H}$ в ${\displaystyle G}$ внутри ${\displaystyle e(H)\varepsilon |V_{1}|\cdots |V_{k}|}$ из

${\displaystyle \left(\prod _{\{i,j\}\in E(H)}d(V_{i},V_{j})\right)\left(\prod _{i=1}^{k}|V_{i}|\right)}$

Это можно комбинировать с леммой Семереди о регулярности, чтобы доказать Лемма об удалении графа. Лемму об удалении графа можно использовать для доказательства Теорема Рота об арифметических прогрессиях,^[3] и его обобщение, лемма об удалении гиперграфа, можно использовать для доказательства Теорема Семереди.^[4]

Лемма об удалении графа обобщается на индуцированные подграфы, рассматривая редактирование краев вместо удаления только краев. Это доказали Алон, Фишер, Кривелевич и Сегеди в 2000 году.^[5] Однако для этого потребовалась более сильная вариация леммы о регулярности.

Лемма Семереди о регулярности не дает содержательных результатов в разреженные графики. Поскольку разреженные графы имеют субконстантную плотность ребер, ${\displaystyle \varepsilon }$-регулярность тривиально выполняется. Хотя результат кажется чисто теоретическим, некоторые попытки ^[6][7] было сделано использовать метод регулярности как метод сжатия для больших графов.

История и расширения

Конструкция Гауэрса для нижней оценки леммы Семереди о регулярности

Семереди (1975) впервые представил более слабую версию этой леммы, ограниченную двудольными графами, чтобы доказать Теорема Семереди,^[8]И в (Семереди 1978 ) он доказал полную лемму.^[9] Расширения метода регулярности на гиперграфы были получены Rödl и его сотрудники^[10][11][12] и Гауэрс.^[13][14]

Янош Комлош, Габор Шаркози и Эндре Семереди позже (в 1997 г.) доказал лемма о раздутии^[15][16] что регулярные пары из леммы Семереди о регулярности ведут себя как полные двудольные графы при правильных условиях. Лемма позволила глубже изучить природу вложения больших разреженных графов в плотные графы.

Первую конструктивную версию представили Алон, Дюк, Лефманн, Rödl и Юстер.^[17]Впоследствии Фриз и Каннан дал другую версию и распространил ее на гиперграфы.^[18] Позже они создали другую конструкцию из-за Алана Фриза и Рави Каннана, которая использует сингулярные значения матриц.^[19] Можно найти более эффективные недетерминированные алгоритмы, как формально подробно описано в Теренс Тао блог^[20] и косвенно упоминается в различных статьях.^[21][22][23]

Неравенство Теренс Тао расширяет лемму Семереди о регулярности, пересматривая ее с точки зрения теории вероятностей и теории информации, а не теории графов.^[24] Теренс Тао также предоставил доказательство леммы на основе спектральной теории, используя матрицы смежности графов.^[25]

Невозможно доказать вариант леммы о регулярности, в котором все пары множеств разбиений регулярны. Некоторые графики, такие как половинные графики, требуют, чтобы много пар разделов (но небольшая часть всех пар) были нерегулярными.^[26]

Это распространенный вариант в определении ${\displaystyle \varepsilon }$-регулярное разделение, чтобы требовать, чтобы все наборы вершин имели одинаковый размер, а оставшиеся вершины собираются в "ошибочном" -наборе ${\displaystyle V_{0}}$ чей размер не более ${\displaystyle \varepsilon }$-доля размера множества вершин ${\displaystyle G}$.

Более сильный вариант леммы о регулярности был доказан Алоном, Фишером, Кривелевичем и Сегеди при доказательстве леммы об удалении индуцированного графа. Это работает с последовательностью ${\displaystyle \varepsilon }$ вместо одного, и показывает, что существует раздел с чрезвычайно регулярным уточнением, где уточнение не имеет слишком большого приращения энергии.

Лемму Семереди о регулярности можно интерпретировать как утверждение, что пространство всех графов полностью ограниченный (и поэтому прекомпактный ) в подходящей метрике ( отрезать расстояние ). Пределы этого показателя могут быть представлены как графоны; другая версия леммы о регулярности просто утверждает, что пространство графонов компактный.^[27]

Рекомендации

1. Конлон, Дэвид; Фокс, Джейкоб (2012), «Границы регулярности графов и леммы об удалении», Геометрический и функциональный анализ, 22 (5): 1191–1256, arXiv:1107.4829, Дои:10.1007 / s00039-012-0171-х, МИСТЕР  2989432, S2CID  1623986
2. Гауэрс, В. Т. (1997), "Нижние оценки башенного типа для леммы Семереди о равномерности", Геометрический и функциональный анализ, 7 (2): 322–337, Дои:10.1007 / PL00001621, МИСТЕР  1445389, S2CID  115242956.
3. Рот, К.Ф. (1953), «О некоторых наборах целых чисел», Журнал Лондонского математического общества, 28 (1): 104–109, Дои:10.1112 / jlms / s1-28.1.104, МИСТЕР  0051853
4. Тао, Теренс (2006), «Вариант леммы об удалении гиперграфа», Журнал комбинаторной теории, Серия А, 113 (7): 1257–1280, arXiv:математика / 0503572, Дои:10.1016 / j.jcta.2005.11.006, МИСТЕР  2259060, S2CID  14337591
5. Алон, Нога; Фишер, Эльдар; Кривелевич Михаил; Сегеди, Марио (2000), «Эффективное тестирование больших графов», Комбинаторика, 20 (4): 451–476, Дои:10.1007 / s004930070001, МИСТЕР  1804820, S2CID  44645628
6. Пелосин, Франческо (2018). «Сжатие графов методом регулярности». arXiv:1810.07275.
7. Фиоруччи, Марко; Пелосин, Франческо; Пелильо, Марчелло (2020). «Отделение структуры от шума в больших графах с помощью леммы о регулярности». 98. arXiv:1905.06917.
8. Семереди, Эндре (1975), «О наборах целых чисел, не содержащих k элементов в арифметической прогрессии», Польская Академия Наук. Instytut Matematyczny. Acta Arithmetica, 27: 199–245, МИСТЕР  0369312.
9. Семереди, Эндре (1978), «Регулярные разбиения графов», Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Коллок. Междунар. CNRS, 260, Париж: CNRS, стр. 399–401, МИСТЕР  0540024.
10. Франкл, Питер; Рёдль, Войтех (2002), «Экстремальные задачи на системах множеств», Случайные структуры и алгоритмы, 20 (2): 131–164, Дои:10.1002 / rsa.10017.abs, МИСТЕР  1884430.
11. Рёдль, Войтех; Скокан, Йозеф (2004), "Лемма о регулярности для k-равномерные гиперграфы », Случайные структуры и алгоритмы, 25 (1): 1–42, Дои:10.1002 / rsa.20017, МИСТЕР  2069663.
12. Нэгл, Брендан; Рёдль, Войтех; Шахт, Матиас (2006), "Считающая лемма для регулярных k-однородные гиперграфы », Случайные структуры и алгоритмы, 28 (2): 113–179, CiteSeerX  10.1.1.378.8503, Дои:10.1002 / rsa.20117, МИСТЕР  2198495.
13. Гауэрс, В. Т. (2006), «Квазислучайность, счет и регулярность для 3-однородных гиперграфов», Комбинаторика, теория вероятностей и вычисления, 15 (1–2): 143–184, Дои:10.1017 / S0963548305007236, МИСТЕР  2195580, S2CID  14632612.
14. Гауэрс, В. Т. (2007), "Регулярность гиперграфа и многомерная теорема Семереди", Анналы математики, Вторая серия, 166 (3): 897–946, arXiv:0710.3032, Bibcode:2007arXiv0710.3032G, Дои:10.4007 / анналы.2007.166.897, МИСТЕР  2373376, S2CID  56118006.
15. Комлош, Янош; Шаркози, Габор Н.; Семереди, Эндре (1997), "Лемма о раздутии", Комбинаторика, 17 (1): 109–123, Дои:10.1007 / BF01196135, МИСТЕР  1466579, S2CID  6720143
16. Комлош, Янош; Шаркози, Габор Н.; Семереди, Эндре (1998), "Алгоритмическая версия леммы о раздутии", Случайные структуры и алгоритмы, 12 (3): 297–312, arXiv:математика / 9612213, Дои:10.1002 / (SICI) 1098-2418 (199805) 12: 3 <297 :: AID-RSA5> 3.3.CO; 2-W, МИСТЕР  1635264
17. Н. Алон, Р. А. Дюк, Х. Лефманн, В. Рёдль и Р. Юстер (1994). «Алгоритмические аспекты леммы о регулярности». J. Алгоритмы. 16: 80–109. CiteSeerX  10.1.1.102.681. Дои:10.1006 / jagm.1994.1005.
18. А. Фриз и Р. Каннан (1996). «Лемма о регулярности и аппроксимационные схемы для плотных задач». FOCS '96: Материалы 37-го ежегодного симпозиума по основам компьютерных наук. Дои:10.1109 / SFCS.1996.548459.
19. А. Фриз и Р. Каннан (1999). "Простой алгоритм построения разбиения регулярности Семереди" (PDF). Электрон. J. Гребень. 6.
20. Тао, Теренс (2009), Лемма Семереди о регулярности через случайные разбиения
21. Алон, Нога; Шапира, Асаф (2008), «Каждое свойство монотонного графа можно проверить», SIAM J. Comput., 38 (2): 505–522, Дои:10.1137/050633445, ISSN  0097-5397, МИСТЕР  2411033
22. Исигами, Ёсиясу (2006), Простая регуляризация гиперграфов, arXiv:математика / 0612838, Bibcode:2006математика ..... 12838I
23. Остин, Тим (2008), "Обмениваемые случайные величины и статистика больших графов и гиперграфов", Вероятностные исследования, 5: 80–145, arXiv:0801.1698, Bibcode:2008arXiv0801.1698A, Дои:10.1214 / 08-ПС124, S2CID  15421306
24. Тао, Теренс (2006), "Повторное обращение к лемме Семереди о регулярности", Вклад в дискретную математику, 1 (1): 8–28, arXiv:математика / 0504472, Bibcode:2005математика ...... 4472T, МИСТЕР  2212136.
25. Тао, Теренс (2012), Спектральное доказательство леммы Семереди о регулярности
26. Конлон, Дэвид; Фокс, Джейкоб (2012), «Границы регулярности графов и леммы об удалении», Геометрический и функциональный анализ, 22 (5): 1191–1256, arXiv:1107.4829, Дои:10.1007 / s00039-012-0171-х, МИСТЕР  2989432, S2CID  1623986
27. Ловас, Ласло; Сегеди, Балаж (2007), «Лемма Семереди для аналитика», Геометрический и функциональный анализ, 17: 252–270, Дои:10.1007 / s00039-007-0599-6, ISSN  1016-443X, МИСТЕР  2306658, S2CID  15201345

дальнейшее чтение

• Комлос, Я.; Симоновиц, М. (1996), "Лемма Семереди о регулярности и ее приложения в теории графов", Комбинаторика, Пол Эрдёш - восемьдесят, Vol. 2 (Кестхей, 1993), Bolyai Soc. Математика. Stud., 2, János Bolyai Math. Soc., Будапешт, стр. 295–352, МИСТЕР  1395865.
• Комлос, Я.; Шокуфанде, Али; Симоновиц, Миклош; Семереди, Эндре (2002), "Лемма о регулярности и ее приложения в теории графов", Теоретические аспекты информатики (Тегеран, 2000 г.), Конспект лекций по информатике, 2292, Springer, Берлин, стр. 84–112, Дои:10.1007/3-540-45878-6_3, ISBN  978-3-540-43328-6, МИСТЕР  1966181.