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

Теорема в теории графов

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

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

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

Пусть будет графом с вершинами. Лемма об удалении графа утверждает, что для любого существует константа такая, что для любого графа с вершинами с меньшим числом подграфов, изоморфных , можно удалить все копии , удалив не более ребер из . ^[1] ${\displaystyle H}$ ${\displaystyle h}$ ${\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 o}$

В случае, когда — треугольник, результирующая лемма называется леммой об удалении треугольника . ${\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 h}$ ${\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 d}$ ${\displaystyle (x,y)\in (X\times Y)}$ ${\displaystyle d}$ ${\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 (V_{i},V_{j})}$не является -регулярным, ${\displaystyle \epsilon /4}$
• плотность меньше , или ${\displaystyle d(V_{i},V_{j})}$ ${\displaystyle \epsilon /2}$
• либо имеет не более вершин . ${\displaystyle V_{i}}$ ${\displaystyle V_{j}}$ ${\displaystyle (\epsilon /4M)n}$

Эта процедура удаляет большинство ребер. Если существует треугольник с вершинами в после удаления этих ребер, то лемма о подсчете треугольников говорит нам, что есть по крайней мере тройки в , которые образуют треугольник. Таким образом, мы можем взять ${\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}$

Приложения

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

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

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

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

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

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

Тестирование свойств

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

Смотрите также

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

Ссылки

1. Fox, Jacob (2011), «Новое доказательство леммы об удалении графа», Annals of Mathematics , вторая серия, 174 (1): 561–579, arXiv : 1006.1300 , doi : 10.4007/annals.2011.174.1.17, MR  2811609, S2CID  8250133
2. Тревизан, Лука (13 мая 2009 г.), «Лемма об удалении треугольника», в теории
3. Roth, KF (1953), «О некоторых множествах целых чисел», Журнал Лондонского математического общества , 28 (1): 104–109, doi :10.1112/jlms/s1-28.1.104, MR  0051853
4. Tao, Terence (2006), «Вариант леммы об удалении гиперграфа», Журнал комбинаторной теории , Серия A, 113 (7): 1257–1280, arXiv : math/0503572 , doi : 10.1016/j.jcta.2005.11.006, MR  2259060, S2CID  14337591
5. Алон, Нога ; Шапира, Асаф (2004), «Тестирование подграфов в ориентированных графах», Журнал компьютерных и системных наук , 69 (3): 353–382, doi : 10.1016/j.jcss.2004.04.008 , MR  2087940
6. Ружа, Издательство ; Семереди, Э. (1978), «Тройные системы без шести точек, несущих три треугольника», Комбинаторика (Труды пятого венгерского коллоквиума, Кестхей, 1976), Vol. II , коллок. Математика. Соц. Янош Бояи, том. 18, Амстердам и Нью-Йорк: Северная Голландия, стр. 939–945, MR  0519318.
7. Erdős, P. ; Frankl, P. ; Rödl, V. (1986), "Асимптотическое число графов, не содержащих фиксированный подграф, и проблема для гиперграфов, не имеющих экспоненты", Graphs and Combinatorics , 2 (2): 113–121, doi :10.1007/BF01788085, MR  0932119, S2CID  16839886
8. Füredi, Zoltán (1995). "Экстремальные гиперграфы и комбинаторная геометрия". В Chatterji, SD (ред.). Труды Международного конгресса математиков . Базель: Birkhäuser. стр. 1343–1352. doi :10.1007/978-3-0348-9078-6_129. ISBN 978-3-0348-9078-6.
9. Комлос, Янош; Саркози, Габор Н.; Семереди, Эндре (1 марта 1997 г.). «Лемма о разрушении». Комбинаторика . 17 (1): 109–123. дои : 10.1007/BF01196135. ISSN  1439-6912. S2CID  6720143.
10. Комлош, Янош (1999). «Лемма о раздутии». Комбинаторика, вероятность и вычисления . 8 (1–2): 161–176. doi :10.1017/S0963548398003502. ISSN  1469-2163. S2CID  6720143.
11. Conlon, David ; Fox, Jacob (2013), "Graph removal lemmas", в Blackburn, Simon R.; Gerke, Stefanie; Wildon, Mark (ред.), Surveys in Combinatorics 2013 , London Mathematical Society Lecture Note Series, т. 409, Кембридж, Великобритания: Cambridge University Press, стр. 1–49, arXiv : 1211.3487 , doi :10.1017/CBO9781139506748.002, ISBN 978-1-107-65195-1, MR  3156927, S2CID  2658118
12. Алон, Нога ; Фишер, Эльдар; Кривелевич, Михаэль ; Сегеди, Марио (2000), «Эффективное тестирование больших графов», Combinatorica , 20 (4): 451–476, doi :10.1007/s004930070001, MR  1804820, S2CID  44645628
13. Gowers, WT (1997). "Нижние границы типа башни для леммы Семереди о равномерности". Геометрический и функциональный анализ . 7 (2): 322–337. doi :10.1007/PL00001621. S2CID  115242956.
14. Солимози, Дж. (2003), «Заметка об обобщении теоремы Рота», Дискретная и вычислительная геометрия , алгоритмы и комбинаторика, 25 : 825–827, doi :10.1007/978-3-642-55566-4_39, ISBN 978-3-642-62442-1, MR  2038505, S2CID  53973423
15. Алон, Н. (2001-10-14). "Тестирование подграфов в больших графах". Труды 42-го симпозиума IEEE по основам компьютерной науки . FOCS '01. США: IEEE Computer Society. стр. 434–441. doi :10.1109/SFCS.2001.959918. ISBN 978-0-7695-1390-4. S2CID  12484006.
16. Эрдеш, П .; Симоновиц, М. (1966). «Предельная теорема в теории графов». Студия Sci. Математика. Хунг . 1 : 51–57.
17. Эрдёш, П. (1966). «Некоторые недавние результаты по экстремальным задачам в теории графов». Теория графов, Международный симпозиум. Рим : 118–123.
18. Эрдёш, П. (1966). «О некоторых новых неравенствах, касающихся экстремальных свойств графов». Теория графов, Proc. Coll. Тихань, Венгрия : 77–81.
19. Эрдёш, П.; Катона , Г. (1966). «Метод решения экстремальных задач в теории графов». Теория графов, Proc. Coll. Тихань : 279–319.
20. Алон, Нога ; Шапира, Асаф (2008), «Характеристика свойств (естественного) графа, проверяемых с односторонней ошибкой», SIAM Journal on Computing , 37 (6): 1703–1727, doi :10.1137/06064888X, MR  2386211