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

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

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

Лемма была доказана Эндре Семереди в 1975 году.^[1][2]

Пусть дан двудольный граф ${\displaystyle G=(W=U\sqcup V,E)}$, рёбра которого соединяют вершины из множества ${\displaystyle U}$ с вершинами из множества ${\displaystyle V}$.

Для ${\displaystyle S\subset U,T\subset V}$ обозначим через ${\displaystyle d(S,T)}$ плотность распределения рёбер между этими множествами, то есть

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

Существует несколько эквивалентных этому определений (эквивалентных в смысле существования монотонной зависимости ${\displaystyle \varepsilon }$ в одном определении от ${\displaystyle \varepsilon }$ в другом при эквивалентности двух определений), но все они используют величину ${\displaystyle d(S,T)}$ и какое-то количественное сравнение её значений для различных пар ${\displaystyle S,T}$.

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

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

Лемма Семереди не накладывает никаких ограничений на рёбра между вершинами из одного и того же множества разбиения.

Утверждение леммы нетривиально только для графов с достаточно большим числом рёбер. Если ${\displaystyle |E|\leq {\frac {\varepsilon ^{3}}{k^{2}}}|V|^{2}}$, то любой его двудольный подграф на долях с размерами ${\displaystyle {\frac {\varepsilon }{k}}|V|}$ также окажется разреженным (его плотность не будет превышать ${\displaystyle \varepsilon }$) - следовательно, условие на разность плотностей будет выполняться всегда.^[5]

Следует также отметить, что упоминание одной и той же переменной ${\displaystyle \varepsilon }$ в двух различных характеристиках - показателе регулярности и доле ${\displaystyle \varepsilon }$-регулярных двудольных подграфов - не создаёт никакой дополнительной связи между этими характеристиками. Такая формулировка следовала бы и из более ослабленной формулировки, где требовалось бы, например, чтобы ${\displaystyle \varepsilon }$-регулярно были распределены рёбра только между ${\displaystyle (1-\eta ){\binom {k}{2}}}$ парами множеств, где ${\displaystyle \eta =\eta (\varepsilon )\to 0}$ при ${\displaystyle \varepsilon \to 0}$ (то есть даже при ${\displaystyle \eta >\varepsilon }$). В таком случае для достижения исходной формулировки достаточно было бы рассмотреть ${\displaystyle \varepsilon _{0}=\eta ^{-1}(\varepsilon )}$, поскольку ${\displaystyle \varepsilon _{0}}$-регулярность графа влечёт за собой ${\displaystyle \varepsilon }$-регулярность при ${\displaystyle \varepsilon _{0}<\varepsilon }$.

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

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

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

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

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

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

Если ${\displaystyle P_{\varepsilon }(V_{i},V_{j})}$, то существуют какие-то конкретные "проблемные" подмножества ${\displaystyle S_{ij}\in V_{i},S_{ji}\in V_{j}}$, нарушающие ${\displaystyle \varepsilon }$-регулярность двудольного графа, соединяющего эти компоненты. То есть для них выполнено:

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

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

Чтобы формализовать этот процесс, для каждой отдельной компоненты ${\displaystyle V_{i}}$ рассматриваются все возникающие в нём "проблемные" подмножества:

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

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

Поскольку для отдельного ${\displaystyle V_{i}}$ существует не более ${\displaystyle k-1}$ проблемных подмножеств (и, следовательно, не более ${\displaystyle 2^{k-1}}$ элементов построенной на них σ-алгебры), то в результате из одной компоненты образуется не больше ${\displaystyle 2^{k-1}}$ новых.

Если подразбить таким образом каждую компоненту ${\displaystyle V_{i}}$, то получится новое подразбиение ${\displaystyle {\mathcal {P}}'}$.

Далее в ${\displaystyle {\mathcal {P}}'}$ надо выровнять размеры компонент (которых в нём всего не более ${\displaystyle k2^{k-1}}$). Для это каждую его компоненту можно разделить на новые компоненты размера ${\displaystyle \left\lfloor {\frac {n}{{(k2^{k-1})}^{2}}}\right\rfloor }$ (и, возможно, одну оставшуюся компоненту меньшего размера - "остаток"), а все вершины из "остатков" соединить произвольным образом в новые компоненты того же размера ${\displaystyle \left\lfloor {\frac {n}{{(k2^{k-1})}^{2}}}\right\rfloor }$ и, возможно, одну компоненту меньшего размера.

Получившееся разбиение и будет результатом одной итерации алгоритма.

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

"Потенциал" может определяться, например, следующим образом:

${\displaystyle \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}}}$

Эта функция имеет ряд важных свойств:

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

• если разбиение ${\displaystyle {\mathcal {Q}}}$ образовано из ${\displaystyle {\mathcal {P}}=(V_{1},\dots ,V_{k})}$ подразбиением одной компоненты ${\displaystyle V_{1}}$ на два множества ${\displaystyle S\subset V_{1}}$ и ${\displaystyle V_{1}\setminus S}$, то ${\displaystyle \Phi ({\mathcal {Q}})\geq \Phi ({\mathcal {P}})}$

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

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

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

В первой работе на эту тему Семереди использовал несколько другую функцию потенциала^[1]:

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

Несмотря на различия, обе эти функции объединяет идея усреднения квадратов плотностей.

Как следует из описания алгоритма, верхняя оценка на количество компонент в разбиении на ${\displaystyle n}$-той итерации алгоритма выражается рекуррентным соотношением

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

Количество итераций, которое проработает алгоритм, оценивается как ${\displaystyle O\left({\frac {1}{\varepsilon ^{5}}}\right)}$.

Следовательно, итоговое количество компонент можно оценить лишь башней из возведений в степень ${\displaystyle 2^{2^{\cdot ^{\cdot ^{\cdot ^{k}}}}}}$ высоты ${\displaystyle O\left({\frac {1}{\varepsilon ^{5}}}\right)}$.

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

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

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

Он рассмотрел даже более обобщённое понятие ${\displaystyle (\varepsilon ,\delta )}$-регулярности, где на подмножество долей двудольного графа ${\displaystyle S\subset U,T\subset V}$, отклонение плотности которой ограничивается определением, накладываются ограничения ${\displaystyle |S|\geq \delta |U|,|T|\geq \delta |V|}$ вместо ${\displaystyle |S|\geq \varepsilon |U|,|T|\geq \varepsilon |V|}$, и для него также доказал существование контрпримера.

Для поиска контрпримера Гауэрс использовал вероятностный метод, так что его доказательство неконструктивно. В работе рассматривались взвешенные графы с весами из интервала ${\displaystyle (0;1)}$. Для таких графов можно рассматривать полностью аналогичную формулировку леммы, где в качестве плотности ${\displaystyle d(U,V)}$ будет рассматриваться сумма весов рёбер вместо их количества. Построив контрпример в виде взвешенного графа, Гауэрс также показал, что случайный граф, генерируемый по схеме Бернулли с вероятностями рёбер, соответствующими весам в этом взвешенном графе, с большой вероятностью будет являться контрпримером для обычной леммы (более того, с большой вероятностью плотности ${\displaystyle d(U,V)}$ будут не сильно отклоняться от аналогичных плотностей во взвешенном графе при условии, что ${\displaystyle |U|}$ и ${\displaystyle |V|}$ достаточно велики).^[7]

Конструкция Гауэрса

Взвешенный граф, служащий контрпримером для леммы с обычным определением ${\displaystyle \varepsilon }$-регулярности, строится как комбинация с разными весами нескольких специфически устроенных больших графов. При построении каждого следующего графа из этого набора вершины объединяются во всё большие и большие группы равного размера такие, что вершины из двух разных групп либо соединяются между собой полным двудольным графом, либо не соединяются вообще (новые группы всегда являются объединением предыдущих).

Пусть вершины разбиты на группы ${\displaystyle X_{1},\dots ,X_{s}}$ одинакового размера. Объединим эти группы в блоки

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

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

${\displaystyle \dots }$

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

где ${\displaystyle k={\frac {s}{t}}}$ (предполагаем, что это - целое число).

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

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

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

Контрпример для ${\displaystyle (\varepsilon ,\delta )}$-регулярности строится похожим образом, но с несколькими отличиями:

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

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

• в конце получившиеся графы ${\displaystyle G_{1},\dots ,G_{s}}$ объединяются не в виде взвешенного графа, а исключающим "или" (в итоговый граф входят только те рёбра, которые присутствовали в нечётном количестве графов ${\displaystyle G_{r},1\leq r\leq s}$).

В 2007 году Уильям Гауэрс обобщил лемму регулярности на гиперграфы и использовал обобщение для доказательства многомерной теоремы Семереди.^[8]

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

Наиболее известно применение леммы регулярности для комбинаторного доказательства теоремы Семереди и её обобщений (например. теоремы об уголках).^[5] Однако лемма и её идеи имеют ряд применений и в общей теории графов^[10] - первая статья Семереди об этой лемме цитируется более чем в 500 работах на самые разные темы.^[1]

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

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