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

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

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

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

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

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

Приложения

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