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

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

Пусть дан двудольный граф ${\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)}$.