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

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

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

Лемма была доказана Эндре Семереди в 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 работах на самые разные темы.

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

См. также

• Эндре Семереди
• Теорема Семереди
• Лемма об удалении треугольников