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

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

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

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

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

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

Приложения

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