Лемма об удалении графа

В теории графов лемма об удалении графа утверждает, что когда граф содержит несколько копий данного подграфа , то все копии можно устранить, удалив небольшое количество ребер. ^[1] Особый случай, в котором подграф является треугольником, известен как лемма об удалении треугольника . ^[2]

Лемма об удалении графа может быть использована для доказательства теоремы Рота о 3-членных арифметических прогрессиях ^[3] , а ее обобщение, лемма об удалении гиперграфа , может быть использовано для доказательства теоремы Семереди . ^[4] Она также применима к тестированию свойств . ^[5]

Пусть будет графом с вершинами. Лемма об удалении графа утверждает, что для любого существует константа такая, что для любого графа с вершинами с меньшим числом подграфов, изоморфных , можно удалить все копии , удалив не более ребер из . ^[1]${\displaystyle H}$${\displaystyle ч}$${\displaystyle \epsilon >0}$${\displaystyle \delta =\delta (\epsilon,H)>0}$${\displaystyle n}$${\displaystyle G}$${\displaystyle \delta n^{h}}$ ${\displaystyle H}$${\displaystyle H}$${\displaystyle \epsilon n^{2}}$${\displaystyle G}$

Альтернативный способ сформулировать это — сказать, что для любого графа с вершинами и подграфами, изоморфными , можно устранить все копии , удалив ребра из . Здесь указывает на использование небольшой нотации o .${\displaystyle n}$${\displaystyle G}$${\displaystyle o(n^{h})}$${\displaystyle H}$${\displaystyle H}$${\displaystyle o(n^{2})}$${\displaystyle G}$${\displaystyle о}$

В случае, когда — треугольник, результирующая лемма называется леммой об удалении треугольника .${\displaystyle H}$

Первоначальной мотивацией для изучения леммы об удалении треугольников была проблема Ружи–Семереди . Ее первоначальная формулировка Имре З. Ружи и Семереди от 1978 года была немного слабее леммы об удалении треугольников, используемой в настоящее время, и может быть грубо сформулирована следующим образом: каждый локально линейный граф на вершинах содержит ребра. ^[6] Это утверждение можно быстро вывести из современной леммы об удалении треугольников. Ружа и Семереди также предоставили альтернативное доказательство теоремы Рота об арифметических прогрессиях в качестве простого следствия. ^[6]${\displaystyle n}$${\displaystyle o(n^{2})}$

В 1986 году, во время работы над обобщениями задачи Ружи–Семереди на произвольные -однородные графы, Эрдёш , Франкл и Рёдль сформулировали утверждение для общих графов, очень близкое к современной лемме об удалении графа: если граф является гомоморфным образом , то любой -свободный граф на вершинах можно сделать -свободным путем удаления ребер. ^[7]${\displaystyle r}$${\displaystyle H_{2}}$${\displaystyle H_{2}}$${\displaystyle H_{1}}$${\displaystyle G}$${\displaystyle n}$${\displaystyle H_{2}}$${\displaystyle o(n^{2})}$

Современная формулировка леммы об удалении графа была впервые сформулирована Фюреди в 1994 году. ^[8] Доказательство обобщило более ранние подходы Ружи и Семереди, а также Эрдёша, Франкла и Рёдля, также используя лемму Семереди о регулярности .

Ключевым компонентом доказательства леммы об удалении графа является лемма о подсчете графов о подсчете подграфов в системах регулярных пар. Лемма о подсчете графов также очень полезна сама по себе. По словам Фюреди, она используется «в большинстве приложений леммы о регулярности». ^[8]

Пусть будет графом на вершинах, множество вершин которого равно , а множество ребер равно . Пусть будет множествами вершин некоторого графа , такого что для всех пара является - регулярной (в смысле леммы о регулярности). Пусть также будет плотностью между множествами и . Интуитивно, регулярная пара с плотностью должна вести себя как случайный граф типа Эрдёша–Реньи , где каждая пара вершин выбирается так, чтобы быть ребром независимо с вероятностью . Это говорит о том, что число копий на вершинах, таких что должно быть близко к ожидаемому числу из модели Эрдёша–Реньи, где и являются множеством ребер и множеством вершин .${\displaystyle H}$${\displaystyle ч}$${\displaystyle V=\{1,2,\ldots ,h\}}$${\displaystyle E}$${\displaystyle X_{1},X_{2},\ldots ,X_{h}}$${\displaystyle G}$${\displaystyle ij\in E}$${\displaystyle (X_{i},X_{j})}$${\displaystyle \epsilon}$${\displaystyle d_{ij}}$${\displaystyle X_{i}}$${\displaystyle X_{j}}$${\displaystyle (X,Y)}$${\displaystyle д}$${\displaystyle (x,y)\in (X\times Y)}$${\displaystyle д}$${\displaystyle H}$${\displaystyle x_{1},x_{2},\ldots ,x_{h}}$${\displaystyle x_{i}\in X_{i}}$$${\displaystyle \prod _{ij\in E(H)}d_{ij}\prod _{i\in V(H)}|X_{i}|,}$$${\displaystyle E(H)}$${\displaystyle V(H)}$${\displaystyle H}$

Простая формализация приведенного выше эвристического утверждения выглядит следующим образом. Пусть будет графом на вершинах, множество вершин которого равно , а множество ребер — . Пусть будет произвольным. Тогда существует такой, что для любого , как указано выше, удовлетворяющего для всех , число гомоморфизмов графа из в , таких, что вершина отображается в , не меньше, чем${\displaystyle H}$${\displaystyle h}$${\displaystyle V=\{1,2,\ldots ,h\}}$${\displaystyle E}$${\displaystyle \delta >0}$${\displaystyle \epsilon >0}$${\displaystyle X_{1},X_{2},\ldots ,X_{h}}$${\displaystyle d_{ij}>\delta }$${\displaystyle ij\in E}$${\displaystyle H}$${\displaystyle G}$${\displaystyle i\in V(H)}$${\displaystyle X_{i}}$$${\displaystyle (1-\delta )\prod _{ij\in E}(d_{ij}-\delta )\prod _{i\in V}|X_{i}|.}$$

Можно даже найти подграфы ограниченной степени раздутий в аналогичной обстановке. Следующее утверждение появляется в литературе под названием леммы о раздутии и было впервые доказано Комлошем , Саркози и Семереди. ^[9] Точное утверждение здесь является слегка упрощенной версией, принадлежащей Комлошу, который также называл его ключевой леммой, поскольку она используется в многочисленных доказательствах, основанных на регулярности. ^[10]${\displaystyle H}$

Пусть будет произвольным графом и пусть . Построим , заменив каждую вершину независимым множеством размера и заменив каждое ребро полным двудольным графом на . Пусть будут произвольными вещественными числами, пусть будет положительным целым числом, и пусть будет подграфом с вершинами и максимальной степенью . Определим . Наконец, пусть будет графом и будет непересекающимися множествами вершин из такими, что всякий раз , то является -регулярной парой с плотностью не менее . Тогда если и , то число инъективных гомоморфизмов графа из в не менее .${\displaystyle H_{1}}$${\displaystyle t\in \mathbb {Z} _{+}}$${\displaystyle H(t)}$${\displaystyle i}$${\displaystyle H}$${\displaystyle V_{i}}$${\displaystyle t}$${\displaystyle ij}$${\displaystyle H}$${\displaystyle (V_{i},V_{j})}$${\displaystyle \epsilon ,\delta >0}$${\displaystyle N}$${\displaystyle H_{2}}$${\displaystyle H(t)}$${\displaystyle h}$${\displaystyle \Delta }$${\displaystyle \epsilon _{0}=\delta ^{\Delta }/(2+\Delta )}$${\displaystyle G}$${\displaystyle X_{1},X_{2},\ldots ,X_{h}}$${\displaystyle G}$${\displaystyle ij\in E(H_{2})}$${\displaystyle (X_{i},X_{j})}$${\displaystyle \epsilon }$${\displaystyle \epsilon +\delta }$${\displaystyle \epsilon \leq \epsilon _{0}}$${\displaystyle 1-t\leq N\epsilon _{0}}$${\displaystyle H_{2}}$${\displaystyle G}$${\displaystyle (\epsilon _{0}N)^{h}}$

Фактически, можно ограничиться подсчетом только тех гомоморфизмов, при которых любая вершина из отображается в вершину из .${\displaystyle k\in [h]}$${\displaystyle H_{2}}$${\displaystyle k\in V_{i}}$${\displaystyle X_{i}}$

Мы предоставим доказательство леммы подсчета в случае, когда является треугольником ( лемма подсчета треугольников ). Доказательство общего случая, а также доказательство леммы о раздутии очень похожи и не требуют различных приемов.${\displaystyle H}$

Возьмем . Пусть будет множеством тех вершин в , которые имеют не менее соседей в и не менее соседей в . Заметим, что если бы было больше вершин в с меньшим числом соседей в , то эти вершины вместе со всем целым свидетельствовали бы о -нерегулярности пары . Повторение этого рассуждения для показывает, что мы должны иметь . Теперь возьмем произвольное и определим и как соседи в и , соответственно. По определению и , поэтому в силу регулярности получаем существование не менее треугольников, содержащих . Поскольку было выбрано произвольно из множества размера не менее , получаем в сумме не менее , что завершает доказательство как .${\displaystyle \epsilon =\delta /2}$${\displaystyle X_{1}'\subset X_{1}}$${\displaystyle X_{1}}$${\displaystyle (d_{12}-\epsilon )|X_{2}|}$${\displaystyle X_{2}}$${\displaystyle (d_{13}-\epsilon )|X_{3}|}$${\displaystyle X_{3}}$${\displaystyle \epsilon |X_{1}|}$${\displaystyle X_{1}}$${\displaystyle (d_{12}-\epsilon )|X_{2}|}$${\displaystyle X_{2}}$${\displaystyle X_{2}}$${\displaystyle \epsilon }$${\displaystyle (X_{1},X_{2})}$${\displaystyle X_{3}}$${\displaystyle |X_{1}'|>(1-2\epsilon )|X_{1}|}$${\displaystyle x\in X_{1}'}$${\displaystyle X_{2}'}$${\displaystyle X_{3}'}$${\displaystyle x}$${\displaystyle X_{2}}$${\displaystyle X_{3}}$${\displaystyle |X_{2}'|\geq (d_{12}-\epsilon )|X_{2}|\geq \epsilon |X_{2}|}$${\displaystyle |X_{3}'|\geq \epsilon |X_{3}|}$${\displaystyle (X_{2},X_{3})}$$${\displaystyle (d_{23}-\epsilon )|X_{2}'||X_{3}'|\geq (d_{12}-\epsilon )(d_{23}-\epsilon )(d_{13}-\epsilon )|X_{2}||X_{3}|}$$${\displaystyle x}$${\displaystyle x}$${\displaystyle X_{1}'}$${\displaystyle (1-2\epsilon )|X_{1}|}$$${\displaystyle (1-2\epsilon )|X_{1}|(d_{23}-\epsilon )|X_{2}'||X_{3}'|\geq (1-2\epsilon )(d_{12}-\epsilon )(d_{23}-\epsilon )(d_{13}-\epsilon )|X_{1}||X_{2}||X_{3}|,}$$${\displaystyle \epsilon =\delta /2}$

Чтобы доказать лемму об удалении треугольников, рассмотрим -регулярное разбиение множества вершин . Оно существует по лемме о регулярности Семереди. Идея состоит в том, чтобы удалить все ребра между нерегулярными парами, парами с низкой плотностью и малыми частями, и доказать, что если хотя бы один треугольник все еще остается, то остается много треугольников. В частности, удалить все ребра между частями и если ${\displaystyle \epsilon /4}$${\displaystyle V_{1}\cup \cdots \cup V_{M}}$${\displaystyle G}$${\displaystyle V_{i}}$${\displaystyle V_{j}}$

Эта процедура удаляет большинство ребер. Если существует треугольник с вершинами в после удаления этих ребер, то лемма о подсчете треугольников говорит нам, что есть по крайней мере тройки в , которые образуют треугольник. Таким образом, мы можем взять${\displaystyle \epsilon n^{2}}$${\displaystyle V_{i},V_{j},V_{k}}$$${\displaystyle \left(1-{\frac {\epsilon }{2}}\right)\left({\frac {\epsilon }{4}}\right)^{3}\left({\frac {\epsilon }{4M}}\right)^{3}\cdot n^{3}}$$${\displaystyle V_{i}\times V_{j}\times V_{k}}$$${\displaystyle \delta <{\frac {1}{6}}\left(1-{\frac {\epsilon }{2}}\right)\left({\frac {\epsilon }{4}}\right)^{3}\left({\frac {\epsilon }{4M}}\right)^{3}.}$$

Доказательство случая общего случая аналогично случаю треугольника и использует лемму о подсчете графов вместо леммы о подсчете треугольников.${\displaystyle H}$

Естественным обобщением леммы об удалении графа является рассмотрение индуцированных подграфов . При тестировании свойств часто бывает полезно рассмотреть, насколько граф далек от того, чтобы быть индуцированным H -свободным. ^[11] Граф считается содержащим индуцированный подграф , если существует инъективное отображение такое, что является ребром , если и только если является ребром . Обратите внимание, что не-ребра также рассматриваются. является индуцированным -свободным, если нет индуцированного подграфа . Мы определяем как -далеко от того, чтобы быть индуцированным -свободным, если мы не можем добавлять или удалять ребра, чтобы сделать индуцированный -свободным.${\displaystyle G}$${\displaystyle H}$${\displaystyle f:V(H)\rightarrow V(G)}$${\displaystyle (f(u),f(v))}$${\displaystyle G}$${\displaystyle (u,v)}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle G}$${\displaystyle \epsilon }$${\displaystyle H}$${\displaystyle \epsilon n^{2}}$${\displaystyle G}$${\displaystyle H}$

Версия леммы об удалении графа для индуцированных подграфов была доказана Алоном , Фишером, Кривелевичем и Сегеди в 2000 году. ^[12] Она утверждает, что для любого графа с вершинами и существует константа такая, что если граф с вершинами имеет меньше, чем индуцированных подграфов, изоморфных , то можно устранить все индуцированные копии путем добавления или удаления меньше, чем ребер.${\displaystyle H}$${\displaystyle h}$${\displaystyle \epsilon >0}$${\displaystyle \delta >0}$${\displaystyle n}$${\displaystyle G}$${\displaystyle \delta n^{h}}$${\displaystyle H}$${\displaystyle H}$${\displaystyle \epsilon n^{2}}$

Проблему можно переформулировать следующим образом: если задана красно-синяя раскраска полного графа (аналогичная графу на тех же вершинах, где не-ребра синие, а ребра красные), и константа , то существует константа такая, что для любой красно-синей раскраски из имеет меньше подграфов, изоморфных , то можно устранить все копии , изменив цвета меньше ребер. Обратите внимание, что наш предыдущий процесс «очистки», в котором мы удаляем все ребра между нерегулярными парами, парами с низкой плотностью и небольшими частями, включает только удаление ребер. Удаление ребер соответствует только изменению цвета ребер с красного на синий. Однако в индуцированном случае существуют ситуации, когда оптимальное расстояние редактирования также включает изменение цвета ребер с синего на красный. Таким образом, леммы о регулярности недостаточно для доказательства леммы об удалении индуцированного графа. Доказательство леммы об удалении индуцированного графа должно использовать преимущества сильной леммы о регулярности . ^[12]${\displaystyle H'}$${\displaystyle K_{h}}$${\displaystyle H}$${\displaystyle h}$${\displaystyle \epsilon >0}$${\displaystyle \delta >0}$${\displaystyle K_{n}}$${\displaystyle \delta n^{h}}$${\displaystyle H'}$${\displaystyle H}$${\displaystyle \epsilon n^{2}}$

Сильная лемма регулярности ^[12] является усиленной версией леммы регулярности Семереди. Для любой бесконечной последовательности констант существует целое число такое, что для любого графа можно получить два (справедливых) разбиения и такое, что выполняются следующие свойства:${\displaystyle \epsilon _{0}\geq \epsilon _{1}\geq ...>0}$${\displaystyle M}$${\displaystyle G}$${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {Q}}}$

• ${\displaystyle {\mathcal {Q}}}$уточняет ; то есть каждая часть представляет собой объединение некоторой совокупности частей в .${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {Q}}}$
• ${\displaystyle {\mathcal {P}}}$является -регулярным и является -регулярным.${\displaystyle \epsilon _{0}}$${\displaystyle {\mathcal {Q}}}$${\displaystyle \epsilon _{|{\mathcal {P}}|}}$
• ${\displaystyle q({\mathcal {Q}})<q({\mathcal {P}})+\epsilon _{0}}$
• ${\displaystyle |{\mathcal {Q}}|\leq M}$

Функция определяется как функция энергии , определенная в лемме регулярности Семереди . По сути, мы можем найти пару разбиений , где чрезвычайно регулярно по сравнению с , и в то же время близки друг к другу. Это свойство зафиксировано в третьем условии.${\displaystyle q}$${\displaystyle {\mathcal {P}},{\mathcal {Q}}}$${\displaystyle {\mathcal {Q}}}$${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {P}},{\mathcal {Q}}}$

Следующее следствие леммы о сильной регулярности используется в доказательстве леммы об удалении индуцированного графа. ^[12] Для любой бесконечной последовательности констант существует такое, что существуют разбиение и подмножества для каждой , где выполняются следующие свойства:${\displaystyle \epsilon _{0}\geq \epsilon _{1}\geq ...>0}$${\displaystyle \delta >0}$${\displaystyle {\mathcal {P}}={V_{1},...,V_{k}}}$${\displaystyle W_{i}\subset V_{i}}$${\displaystyle i}$

• ${\displaystyle |W_{i}|>\delta n}$
• ${\displaystyle (W_{i},W_{j})}$является -регулярным для каждой пары${\displaystyle \epsilon _{|{\mathcal {P}}|}}$${\displaystyle i,j}$
• ${\displaystyle |d(W_{i},W_{j})-d(V_{i},V_{j})|\leq \epsilon _{0}}$для всех, кроме пар${\displaystyle \epsilon _{0}|{\mathcal {P}}|^{2}}$${\displaystyle i,j}$

Основная идея доказательства этого следствия заключается в том, чтобы начать с двух разбиений и , которые удовлетворяют лемме о сильной регулярности, где . Затем для каждой части мы равномерно случайным образом выбираем некоторую часть , которая является частью в . Ожидаемое число нерегулярных пар меньше 1. Таким образом, существует некоторый набор из , такой что каждая пара является -регулярной!${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {Q}}}$${\displaystyle q({\mathcal {Q}})<q({\mathcal {P}})+\epsilon _{0}^{3}/8}$${\displaystyle V_{i}\in {\mathcal {P}}}$${\displaystyle W_{i}\subset V_{i}}$${\displaystyle {\mathcal {Q}}}$${\displaystyle (W_{i},W_{j})}$${\displaystyle W_{i}}$${\displaystyle \epsilon _{|{\mathcal {P}}|}}$

Важным аспектом этого следствия является то, что каждая пара является -регулярной! Это позволяет нам учитывать края и не-края, когда мы выполняем наше рассуждение об очистке.${\displaystyle W_{i},W_{j}}$${\displaystyle \epsilon _{|{\mathcal {P}}|}}$

С этими результатами мы можем доказать лемму об удалении индуцированного графа. Возьмем любой граф с вершинами, который имеет менее копий . Идея состоит в том, чтобы начать с набора множеств вершин , которые удовлетворяют условиям Следствия леммы о сильной регулярности . ^[12] Затем мы можем выполнить процесс «очистки», в котором мы удаляем все ребра между парами частей с низкой плотностью, и мы можем добавить все ребра между парами частей с высокой плотностью. Мы выбираем требования к плотности таким образом, чтобы мы добавляли/удаляли на большинстве ребер.${\displaystyle G}$${\displaystyle n}$${\displaystyle \delta n^{v(H)}}$${\displaystyle H}$${\displaystyle W_{i}}$${\displaystyle (W_{i},W_{j})}$${\displaystyle (W_{i},W_{j})}$${\displaystyle \epsilon n^{2}}$

Если новый граф не имеет копий , то мы закончили. Предположим, что новый граф имеет копию . Предположим, что вершина встроена в . Тогда, если есть ребро, соединяющее в , то не имеет низкой плотности. (Ребра между не были удалены в процессе очистки.) Аналогично, если нет ребра, соединяющего в , то не имеет высокой плотности. (Ребра между не были добавлены в процессе очистки.)${\displaystyle H}$${\displaystyle H}$${\displaystyle v_{i}\in v(H)}$${\displaystyle W_{f(i)}}$${\displaystyle v_{i},v_{j}}$${\displaystyle H}$${\displaystyle W_{i},W_{j}}$${\displaystyle W_{i},W_{j}}$${\displaystyle v_{i},v_{j}}$${\displaystyle H}$${\displaystyle W_{i},W_{j}}$${\displaystyle W_{i},W_{j}}$

Таким образом, с помощью подсчетного аргумента, аналогичного доказательству леммы о подсчете треугольников (то есть леммы о подсчете графов ), мы можем показать, что имеет более копий .${\displaystyle G}$${\displaystyle \delta n^{v(H)}}$${\displaystyle H}$

Лемма об удалении графа была позднее распространена на направленные графы ^[5] и гиперграфы ^[4] .

Использование леммы о регулярности в доказательстве леммы об удалении графа заставляет быть чрезвычайно малым, ограниченным функцией башни , высота которой является полиномом по ; то есть, (здесь — башня двоек высоты ). Функция башни высоты необходима во всех доказательствах регулярности, как следует из результатов Гауэрса о нижних границах в лемме о регулярности. ^[13] Однако в 2011 году Фокс предоставил новое доказательство леммы об удалении графа, которое не использует лемму о регулярности, улучшая границу до (здесь — число вершин удаленного графа ). ^[1] Его доказательство, однако, использует связанные с регулярностью идеи, такие как приращение энергии , но с другим понятием энергии, связанным с энтропией . Это доказательство также можно перефразировать с использованием леммы Фриза-Каннана о слабой регулярности , как отметили Конлон и Фокс. ^[11] В частном случае двудольного было показано, что достаточно.${\displaystyle \delta }$${\displaystyle \epsilon ^{-1}}$${\displaystyle \delta =1/{\text{tower}}(\epsilon ^{-O(1)})}$${\displaystyle {\text{tower}}(k)}$${\displaystyle k}$${\displaystyle \epsilon ^{-O(1)}}$${\displaystyle \delta =1/{\text{tower}}(5h^{2}\log \epsilon ^{-1})}$${\displaystyle h}$${\displaystyle H}$${\displaystyle H}$${\displaystyle \delta =\epsilon ^{O(1)}}$

Существует большой разрыв между доступными верхними и нижними границами для в общем случае. Текущий лучший результат, верный для всех графов, принадлежит Алону и утверждает, что для каждого недвудольного существует константа , такая что необходима для выполнения леммы об удалении графа, в то время как для двудольного оптимальное имеет полиномиальную зависимость от , что соответствует нижней границе. Конструкция для недвудольного случая является следствием конструкции Беренда больших множеств Салема-Спенсера. Действительно, поскольку лемма об удалении треугольника подразумевает теорему Рота , существование больших множеств Салема-Спенсера может быть переведено в верхнюю границу для в лемме об удалении треугольника. Этот метод можно использовать для произвольного недвудольного , чтобы получить вышеупомянутую границу.${\displaystyle \delta }$${\displaystyle H}$${\displaystyle H}$${\displaystyle c>0}$${\displaystyle \delta <(\epsilon /c)^{c\log(c/\epsilon )}}$${\displaystyle H}$${\displaystyle \delta }$${\displaystyle \epsilon }$${\displaystyle \delta }$${\displaystyle H}$

• Лемма подсчета
• Догадка Тузы