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

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

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

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