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

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

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

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

Формулировка

Понятие ε-равномерности 

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

Для  обозначим через  плотность распределения рёбер между этими множествами, то есть

 .

Определение

Двудольный граф  называется -равномерным если для любых , удовлетворяющих условиям , выполнено неравенство

 

Существует несколько эквивалентных этому определений (эквивалентных в смысле существования монотонной зависимости  в одном определении от  в другом при эквивалентности двух определений), но все они используют величину  и какое-то количественное сравнение её значений для различных пар .

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

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

Формулировка леммы 

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

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

Замечания 

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

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

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

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

Алгоритм разбиения 

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

Сначала выбирается произвольное разбиение вершин на множества , где:

 
 

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

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

Переход от разбиения к подразбиению 

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

Если , то существуют какие-то конкретные "проблемные" подмножества , нарушающие -регулярность двудольного графа, соединяющего эти компоненты. То есть для них выполнено:

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

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

 

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

Поскольку для отдельного  существует не более  проблемных подмножеств (и, следовательно, не более  элементов построенной на них σ-алгебры), то в результате из одной компоненты образуется не больше  новых.

Если подразбить таким образом каждую компоненту , то получится новое подразбиение .

Далее в  надо выровнять размеры компонент (которых в нём всего не более ). Для это каждую его компоненту можно разделить на новые компоненты размера  (и, возможно, одну оставшуюся компоненту меньшего размера - "остаток"), а все вершины из "остатков" соединить произвольным образом в новые компоненты того же размера  и, возможно, одну компоненту меньшего размера.

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

Оценка количества шагов алгоритма 

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

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

 

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

 

 если разбиение  образовано из  подразбиением одной компоненты  на два множества  и , то 

 для разбиения  из алгоритма, описанного в предыдущем разделе, верно 

 если разбиение  получено из разбиения  переразбиением вершин нескольких компонент  на какие-то другие компоненты (не обязательно подразбиением), то 

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

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

 

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

Оценка размера разбиения 

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

 

Количество итераций, которое проработает алгоритм, оценивается как .

Следовательно, итоговое количество компонент можно оценить лишь башней из возведений в степень  высоты .

Эффективный алгоритм поиска разбиения 

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

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

Нижняя оценка на размер искомого разбиения 

В 1997 году Уильям Гауэрс показал, что оценка на размер количества компонент в искомом разбиении не может быть улучшена больше, чем до башни экспонент  высоты . А именно, он показал, что всегда существует граф, любое разбиение которого на меньшее количество частей не удовлетворяет условиям леммы.

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

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

Обобщения 

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

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

Приложения 

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

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

См. также 

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

Примечания 

Теоремы теории графов
Комбинаторика
Арифметическая комбинаторика