Лемма об удалении графа - Graph removal lemma

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

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

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

Позволять ${\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}$.^[1]

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

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

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

Лемма об удалении графа была первоначально доказана для случая, когда подграф является треугольником формулой Имре З. Ружа и Эндре Семереди в 1978 г., используя Лемма Семереди о регулярности.^[6] Ключевым элементом доказательства является лемма о треугольнике.

Неформально, если подмножества вершин ${\displaystyle X,Y,Z}$ из ${\displaystyle G}$ "случайны" с попарными плотность краев ${\displaystyle d_{XY},d_{XZ},d_{YZ}}$, то ожидаем количество троек ${\displaystyle (x,y,z)\in X\times Y\times Z}$ такой, что ${\displaystyle x,y,z}$ сформировать треугольник в ${\displaystyle G}$ быть

$${\displaystyle d_{XY}d_{XZ}d_{YZ}\cdot |X||Y||Z|.}$$

Более точно, предположим, что подмножества вершин ${\displaystyle X,Y,Z}$ из ${\displaystyle G}$ попарно ${\displaystyle \epsilon }$-обычный, и предположим, что плотности ребер ${\displaystyle d_{XY},d_{XZ},d_{YZ}}$ все по крайней мере ${\displaystyle 2\epsilon }$. Тогда количество троек ${\displaystyle (x,y,z)\in X\times Y\times Z}$ такой, что ${\displaystyle x,y,z}$ сформировать треугольник в ${\displaystyle G}$ по крайней мере

$${\displaystyle (1-2\epsilon )(d_{XY}-\epsilon )(d_{XZ}-\epsilon )(d_{YZ}-\epsilon )\cdot |X||Y||Z|.}$$

Чтобы доказать лемму об удалении треугольника, рассмотрим ${\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}.}$$

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

Лемма об удалении треугольника была распространена на общие подграфы Эрдёшем, Франклом и Рёдлем в 1986 г.^[7] Доказательство аналогично доказательству леммы об удалении треугольника и использует обобщение леммы о подсчете треугольников: лемма о подсчете графов.

Обобщения

Позднее лемма об удалении графа была распространена на ориентированные графы^[5] и чтобы гиперграфы.^[4] Альтернативное доказательство, обеспечивающее более строгие ограничения количества ребер, которые необходимо удалить, в зависимости от количества копий подграфа, было опубликовано Джейкоб Фокс в 2011.^[1]

Версия для индуцированные подграфы было доказано Алоном, Фишером, Кривелевичем и Сегеди в 2000 г.^[8] В нем говорится, что для любого графа ${\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}}$ края. Заметим, что доказательство леммы об удалении графа нелегко распространить на индуцированные подграфы, поскольку при заданном регулярном разбиении множества вершин графа ${\displaystyle G}$, теперь становится неясным, добавлять или удалять все ребра между неправильными парами. Эту проблему необходимо устранить с помощью лемма о сильной регулярности.^[8]

Приложения

• Ружа и Семереди сформулировали лемму об удалении треугольника, чтобы обеспечить субквадратичный верхняя граница на Проблема Ружи – Семереди от размера графиков, в которых каждое ребро принадлежит уникальному треугольнику. Это приводит к доказательству теоремы Рота.^[3]
• Лемму об удалении треугольника также можно использовать для доказательства теорема углов, который утверждает, что любое подмножество ${\displaystyle [n]^{2}}$ который не содержит выровненного по оси равнобедренного прямоугольного треугольника, имеет размер ${\displaystyle o(n^{2})}$.^[9]
• В лемма об удалении гиперграфа можно использовать для доказательства Теорема Семереди о существовании длительного арифметические прогрессии в плотных подмножествах целых чисел.^[4]
• Лемма об удалении графа имеет приложения для проверка собственности, потому что это означает, что для каждого графа либо граф находится рядом с ${\displaystyle H}$-свободный график или случайная выборка легко найдет копию ${\displaystyle H}$ в графике.^[5] Один результат состоит в том, что для любого фиксированного ${\displaystyle \epsilon >0}$, Существует постоянный алгоритм времени, который возвращается с высокой вероятностью независимо от того, ${\displaystyle n}$-вершинный граф ${\displaystyle G}$ является ${\displaystyle \epsilon }$-далекий от ${\displaystyle H}$-свободный.^[10] Здесь, ${\displaystyle \epsilon }$-далее от того, чтобы быть ${\displaystyle H}$-бесплатно означает, что по крайней мере ${\displaystyle \epsilon n^{2}}$ края необходимо удалить, чтобы удалить все копии ${\displaystyle H}$ в ${\displaystyle G}$.
• Лемма об удалении индуцированного графа была сформулирована Алоном, Фишером, Кривелевичем и Сегеди для характеристики свойств проверяемого графа.^[8]

Рекомендации

1. Фокс, Джейкоб (2011), «Новое доказательство леммы об удалении графа», Анналы математики, Вторая серия, 174 (1): 561–579, arXiv:1006.1300, Дои:10.4007 / летопись.2011.174.1.17, МИСТЕР  2811609
2. Тревизан, Лука (13 мая 2009 г.), "Лемма об удалении треугольника", в теории
3. Рот, К.Ф. (1953), «О некоторых наборах целых чисел», Журнал Лондонского математического общества, 28 (1): 104–109, Дои:10.1112 / jlms / s1-28.1.104, МИСТЕР  0051853
4. Тао, Теренс (2006), «Вариант леммы об удалении гиперграфа», Журнал комбинаторной теории, Серия А, 113 (7): 1257–1280, arXiv:математика / 0503572, Дои:10.1016 / j.jcta.2005.11.006, МИСТЕР  2259060
5. Алон, Нога; Шапира, Асаф (2004), "Тестирование подграфов в ориентированных графах", Журнал компьютерных и системных наук, 69 (3): 353–382, Дои:10.1016 / j.jcss.2004.04.008, МИСТЕР  2087940
6. Ружа, И.З.; Семереди, Э. (1978), «Тройные системы без шести точек, несущие три треугольника», Комбинаторика (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Коллок. Математика. Soc. Янош Бойяи, 18, Амстердам и Нью-Йорк: Северная Голландия, стр. 939–945, МИСТЕР  0519318
7. Эрдеш, П.; Франкл, П.; Рёдль, В. (1986), «Асимптотическое число графов, не содержащих фиксированного подграфа, и проблема для гиперграфов без экспоненты», Графы и комбинаторика, 2 (2): 113–121, Дои:10.1007 / BF01788085, МИСТЕР  0932119
8. Алон, Нога; Фишер, Эльдар; Кривелевич Михаил; Сегеди, Марио (2000), «Эффективное тестирование больших графов», Комбинаторика, 20 (4): 451–476, Дои:10.1007 / s004930070001, МИСТЕР  1804820
9. Солимози, Дж. (2003), «Замечание об обобщении теоремы Рота», Дискретная и вычислительная геометрия, Алгоритмы и комбинаторика, 25: 825–827, Дои:10.1007/978-3-642-55566-4_39, ISBN  978-3-642-62442-1, МИСТЕР  2038505, S2CID  53973423
10. Алон, Нога; Шапира, Асаф (2008), «Характеристика (естественных) свойств графа, проверяемых с односторонней ошибкой», SIAM Журнал по вычислениям, 37 (6): 1703–1727, Дои:10.1137 / 06064888X, МИСТЕР  2386211