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

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

Пусть ${\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].