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

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

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

Формулировка [ править ]

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

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

Доказательство [ править ]

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

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

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

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

Точнее, предположим, что подмножества вершин в попарно -регулярны , и предположим, что все плотности ребер не меньше . Тогда количество троек , образующих треугольник в , не менее

X,Y,Z

G

\epsilon

d_{XY},d_{XZ},d_{YZ}

2\epsilon

(x,y,z)\in X\times Y\times Z

x,y,z

G

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

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

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

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

Обобщения [ править ]

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

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

Приложения [ править ]

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

Ссылки [ править ]

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

[f11-1] Б с Фоксом, Иаков (2011), "Новое доказательство графа удаления леммы" Анналы математики , второй серия, 174 (1): 561-579, Arxiv : 1006.1300 , DOI : 10,4007 / annals.2011.174. 1.17 , Руководство по ремонту 2811609 CS1 maint: discouraged parameter (link)

[t09-2] Тревизан, Лука (13 мая 2009 г.), «Лемма об удалении треугольника» , в теории CS1 maint: discouraged parameter (link)

[roth-3] Б Roth, К. Ф. (1953), "О некоторых множествах целых чисел", журнал Лондонского математического общества , 28 (1): 104-109, DOI : 10.1112 / jlms / s1-28.1.104 , MR 0051853 CS1 maint: discouraged parameter (link)

[tao-4] Тао, Теренс (2006), «Вариант леммы об удалении гиперграфа», Журнал комбинаторной теории , серия A, 113 (7): 1257–1280, arXiv : math / 0503572 , doi : 10.1016 / j. jcta.2005.11.006 , MR 2259060 CS1 maint: discouraged parameter (link)

[as-5] Алон, Нога ; Шапира, Асаф (2004), "Тестирование подграфы в ориентированных графах", журнал компьютерных и системных наук , 69 (3): 353-382, DOI : 10.1016 / j.jcss.2004.04.008 , MR 2087940

[rs78-6] Ружа, ИЗ ; Семереди Э. (1978), "Тройные системы без шести точек, несущие три треугольника", Комбинаторика (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II , коллок. Математика. Soc. Янош Бойяи, 18 , Амстердам и Нью-Йорк: Северная Голландия, стр. 939–945, MR 0519318

[efr-7] Эрдеш, П .; Frankl, P .; Редль, В. (1986), «Асимптотическое число графов , не содержащих фиксированный подграфа и проблему для гиперграфов , не имеющих показателя», графы и комбинаторики , 2 (2): 113-121, DOI : 10.1007 / BF01788085 , МР 0932119

[afk-8] Алон, Нога ; Фишер, Эльдар; Кривелевич Михаил ; Szegedy, Марио (2000), "Эффективное тестирование больших графов", Combinatorica , 20 (4): 451-476, DOI : 10.1007 / s004930070001 , MR 1804820

[s03-9] Solymosi, J. (2003), «Примечание об обобщении теоремы Рота», Дискретная и вычислительная геометрия , алгоритмы и комбинаторика, 25 : 825–827, DOI : 10.1007 / 978-3-642-55566-4_39 , ISBN 978-3-642-62442-1, Руководство по ремонту 2038505 , S2CID 53973423

[as08-10] Алон, Нога ; Шапира, Асаф (2008), "Характеризация (природный) граф свойств тестируемых с односторонний ошибкой", SIAM журнал по вычислениям , 37 (6): 1703-1727, DOI : 10,1137 / 06064888X , МР 2386211

[1]