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

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

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

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

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

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

В случае, когда $H$ является треугольником, полученная лемма называется леммой об удалении треугольника .

История

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

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

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

Лемма о подсчете графов

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

Эвристический аргумент

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

Точное утверждение

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

Лемма о раздутии

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

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

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

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

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

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

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

Доказательство леммы об удалении треугольника.

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

• $(V_{i},V_{j})$ не $\epsilon /4$-обычный
• плотность $d(V_{i},V_{j})$ меньше, чем $\epsilon /2$, или
• или $V_{i}$ или $V_{j}$ имеет не более $(\epsilon /4M)n$ вершины.

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

Доказательство леммы об удалении графа

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

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

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

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

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

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

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

Лемма о сильной регулярности

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

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

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

Следствие леммы о сильной регулярности.

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

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

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

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

Доказательство наброска леммы об удалении индуцированного графа

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

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

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

Обобщения

Лемма об удалении графа позже была распространена на ориентированные графы. и гиперграфам .

Количественные границы

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

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

Приложения

Аддитивная комбинаторика

• Ружа и Семереди сформулировали лемму об удалении треугольников, чтобы обеспечить субквадратичные верхние оценки проблемы Ружи–Семереди о размере графов, в которых каждое ребро принадлежит уникальному треугольнику . Это приводит к доказательству теоремы Рота.
• Лемму об удалении треугольников можно также использовать для доказательства теоремы об углах , которая утверждает, что любое подмножество треугольников $[n]^{2}$ который не содержит равнобедренных прямоугольных треугольников, выровненных по осям, имеет размер $o(n^{2})$.
• можно Лемму об удалении гиперграфа использовать для доказательства теоремы Семереди о существовании длинных арифметических прогрессий в плотных подмножествах целых чисел.

Теория графов

• Лемму о подсчете/удалении графов можно использовать для быстрого и прозрачного доказательства теоремы Эрдеша – Стоуна, начиная с теоремы Турана , и расширяя результат до устойчивости Симоновица : для любого графа $H$ и любой $\epsilon >0$ существует $\delta$ такой, что любой $H$-бесплатный график на $n$ вершины с по крайней мере $\left(1-{\frac {1}{\chi (H)-1}}\right){\binom {n}{2}}-\delta n^{2}$ края могут быть преобразованы в законченные $(\chi (H)-1)$-частный граф Турана $T_{n,\chi (H)-1}$ добавляя и/или удаляя не более $\epsilon n^{2}$ края (здесь $\chi (H)$ это хроматическое число $H$). Хотя оба результата были доказаны ранее с использованием более элементарных методов (теорема Эрдеша – Стоуна была доказана в 1966 г. Эрдёшем и Стоуном, в то время как устойчивость Симоновица была показана в том же году разными авторами. ), доказательство регулярности предлагает другую точку зрения и проясняет связь с другими современными доказательствами.
• Лемму об удалении графов вместе с теоремой Эрдеша – Стоуна можно использовать, чтобы показать, что число неизоморфных графов $H$-бесплатные графики на $n$ вершин равно

  $$2^{(\pi (H)+o(1)){\binom {n}{2}}}$$

  где $\pi (H)=1-{\frac {1}{\chi (H)-1}}$ плотность Турана ​ $H$.

Тестирование недвижимости

• Лемма об удалении графа имеет применение для проверки свойств , поскольку она подразумевает, что для каждого графа либо граф находится рядом с $H$-свободный график или случайная выборка позволят легко найти копию $H$ в графике. Одним из результатов является то, что для любого фиксированного $\epsilon >0$, существует алгоритм постоянного времени, который с высокой вероятностью возвращает результат независимо от того, задано данное значение или нет. $n$-вершинный граф $G$ является $\epsilon$- далеко не так $H$-бесплатно. Здесь, $\epsilon$- далеко не так $H$-свободно означает, что по крайней мере $\epsilon n^{2}$ края должны быть удалены, чтобы удалить все копии $H$ в $G$.
• Лемма об удалении индуцированного графа была сформулирована Алоном, Фишером, Кривелевичем и Сегеди для характеристики проверяемых свойств графа.

См. также

• Лемма о счете
• Гипотеза Тузы