PROFILPELAJAR.COM

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

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

Пусть $H$ будет граф с $h$ вершинами. Тогда для любого графа $G$ с $n$ вершинами, который имеет $o(n^{h})$ изоморфных $H$ подграфов, можно исключить все эти подграфы путём удаления $o(n^{2})$ рёбер из $G$ . Здесь $o$ означает «o малое»^[1].

Доказательства и обобщения

Лемму об удалении графа первоначально доказали для случая, когда подграфом является треугольник, в 1978 Имре З. Ружа и Эндре Семереди, используя Лемму регулярности Семереди^[3]. Позднее лемма была расширена на другие типы подграфов^[4] — на ориентированные графы^[5] и гиперграфы^[6]. Альтернативное доказательство, дающее более сильные границы о числе рёбер, которые нужно удалить, как функцию числа копий подграфа, опубликовал Якоб Фокс в 2011^[1].

Приложения

Ружа и Семереди сформулировали лемму об удалении треугольника, чтобы обеспечить подквадратичные верхние границы для проблемы Ружи — Семереди от размера графов, в которых любое ребро принадлежит единственному треугольнику. Лемма об удалении графа имеет приложения в тестировании свойств^[англ.], поскольку из неё следует, что в любом графе, либо граф почти свободен от $H$ графа, либо случайные выборки легко найдут копию $H$ в графе^[5]. Лемма об удалении гиперграфа может быть использована для доказательства теоремы Семереди о существовании длинных арифметических прогрессий в плотных подмножествах целых чисел^[6].

Примечания

↑ ¹ ² ³ Jacob Fox. A new proof of the graph removal lemma // Annals of Mathematics. — 2011. — Т. 174, вып. 1. — С. 561–579. — doi:10.4007/annals.2011.174.1.17.
↑ Luca Trevisan. The Triangle Removal Lemma. — 2009. — Май. Архивировано 4 апреля 2019 года.
↑ Imre Z. Ruzsa, Endre Szemerédi. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II. — North-Holland, 1978. — Т. 18. — С. 939–945.
↑ Paul Erdős, Peter Frankl, Vojtěch Rödl. The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent // Graphs and Combinatorics. — 1986. — Т. 2, вып. 2. — С. 113–121. — doi:10.1007/BF01788085.
↑ ¹ ² Noga Alon, Asaf Shapira. Testing subgraphs in directed graphs // Journal of Computer and System Sciences. — 2004. — Т. 69, вып. 3. — С. 353–382. — doi:10.1016/j.jcss.2004.04.008.
↑ ¹ ² Terence Tao. A variant of the hypergraph removal lemma // Journal of Combinatorial Theory. — 2006. — Т. 113, вып. 7. — С. 1257–1280. — doi:10.1016/j.jcta.2005.11.006.