Лемма об удалении графа (Lybbg kQ r;glyunn ijgsg)

Перейти к навигации Перейти к поиску

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

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

[править | править код]

Пусть будет граф с вершинами. Тогда для любого графа с вершинами, который имеет изоморфных подграфов, можно исключить все эти подграфы путём удаления рёбер из . Здесь означает «o малое»[1].

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

[править | править код]

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

Приложения

[править | править код]

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

Примечания

[править | править код]
  1. 1 2 3 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.
  2. Luca Trevisan. The Triangle Removal Lemma. — 2009. — Май. Архивировано 4 апреля 2019 года.
  3. Imre Z. Ruzsa, Endre Szemerédi. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II. — North-Holland, 1978. — Т. 18. — С. 939–945.
  4. 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.
  5. 1 2 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.
  6. 1 2 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.