Введение
Концепция в экстремальной теории графов
В экстремальной теории графов лемма регулярности Семереди утверждает, что граф можно разбить на ограниченное число частей таким образом, чтобы рёбра между частями были регулярными. Лемма показывает, что некоторые свойства случайных графов можно применять к плотным графам, например, для подсчёта копий заданного подграфа в графе. Эндре Семереди доказал лемму для двудольных графов в связи со своей теоремой об арифметических прогрессиях в 1975 году и для общих графов в 1978 году. Различные варианты леммы используют разные понятия регулярности и применимы к другим математическим объектам, таким как гиперграфы.
Лемма подсчета графов
Если у нас достаточно информации о регулярности графа, мы можем подсчитать количество копий конкретного подграфа в графе с небольшой погрешностью. Лемма о подсчете графов. Пусть – граф с вершинами, и пусть – граф с вершинами с множествами вершин такими, что является -регулярным всякий раз, когда. Тогда количество помеченных копий в находится в пределах от .
Это можно объединить с леммой регулярности Семереди, чтобы доказать лемму об удалении графов. Лемма об удалении графов может быть использована для доказательства теоремы Рота об арифметических прогрессиях, а её обобщение, лемма об удалении гиперграфов, может быть использована для доказательства теоремы Семереди. Лемма об удалении графов обобщается на индуцированные подграфы, рассматривая изменение рёбер вместо только удаления рёбер. Это было доказано Алоном, Фишером, Кривелевичем и Сегеди в 2000 году. Однако для этого требовалась более сильная версия леммы регулярности. Лемма регулярности Семереди не даёт значимых результатов для разреженных графов. Поскольку разреженные графы имеют субконстантную плотность рёбер, -регулярность удовлетворяется тривиально. Несмотря на то, что результат кажется чисто теоретическим, были предприняты некоторые попытки использовать метод регулярности как метод сжатия для больших графов.
Алгоритмические приложения
Одной из первоначальных мотиваций для разработки леммы слабой регулярности был поиск эффективного алгоритма для оценки максимального разреза в плотном графе. Было показано, что приближение задачи о максимальном разрезе с точностью лучше 16/17 является NP-трудным, однако алгоритмическая версия леммы слабой регулярности предоставляет эффективный алгоритм для приближения максимального разреза для плотных графов с аддитивной погрешностью. Эти идеи получили дальнейшее развитие в эффективных алгоритмах выборки для оценки максимального разреза в плотных графах. Более слабые границы леммы слабой регулярности позволяют эффективным алгоритмам находить почти регулярное разбиение. Графическая регулярность также нашла применение в различных областях теоретической информатики, таких как умножение матриц и сложность коммуникации.
Лема сильной закономерности
Лемма сильной регулярности — более сильная версия леммы регулярности, доказанная Алоном, Фишером, Кривелевичем и Сегеди в 2000 году. Интуитивно, она предоставляет информацию о нерегулярных парах и может быть использована для доказательства леммы об удалении индуцированного графа.
Замечания по справедливому
Разбиение считается справедливым, если размеры любых двух подмножеств отличаются не более чем на B. Достигая справедливости на каждом шаге итерации, доказательство леммы регулярности можно адаптировать для доказательства справедливой версии леммы регулярности. И, заменяя лемму регулярности ее справедливой версией, вышеуказанное доказательство может доказать справедливую версию леммы сильной регулярности, где и являются справедливыми разбиениями.
Мотивация
Данное следствие более детально исследует малое приращение энергии. Оно предоставляет нам разбиение вместе с подмножествами больших размеров из каждой части, которые попарно регулярны. Кроме того, разница в плотности между соответствующими парами подмножеств "незначительно" отличается от разницы в плотности между соответствующими частями.
Доказательство последовательности
Мы докажем только более слабый результат, где второе условие требует лишь регулярности для . Полную версию можно доказать, выбрав больше подмножеств из каждой части, которые в основном попарно регулярны, и объединив их вместе. Пусть . Применим лемму о сильной регулярности, чтобы найти равное разбиение, которое является -регулярным, и равное уточнение, которое является -регулярным, такое, что и .
Теперь предположим, что . Случайно выберем вершину из каждого и пусть будет множеством, содержащим в . Утверждаем, что подмножества удовлетворяют всем условиям с вероятностью .
Установив , первое условие тривиально выполняется, поскольку является справедливым разбиением. Поскольку не более пар вершин находятся между нерегулярными парами в , вероятность того, что пара и является нерегулярной, равна . По принципу включений-исключений, вероятность того, что хотя бы одна пара , является нерегулярной, не превышает . Заметим, что .
Следовательно, по неравенству Маркова, с вероятностью не более пар могут иметь . По принципу включений-исключений, вероятность того, что все условия выполняются, равна .