Лема про видалення графа

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

Формулювання

Нехай $H$ — граф з $h$ вершинами. Тоді для будь-якого графа $G$ з $n$ вершинами, який має $o(n^{h})$ ізоморфних $H$ підграфів можна виключити всі ці підграфи, видаливши $o(n^{2})$ ребер з $G$. Тут $o$ означає "o мале".

Доведення та узагальнення

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

Застосування

Ружа і Семереді сформулювали лему про видалення трикутників, щоб забезпечити підквадратичні верхні межі задачі Ружі — Семереді від розміру графів, у яких будь-яке ребро належить єдиному трикутнику. Лема про видалення графа застосовується в тестуванні властивостей, оскільки з неї випливає, що в будь-якому графі, або граф майже вільний від графа $H$, або випадковими вибірками легко знайти копію $H$ у графі. Лему про видалення гіперграфа можна використати для доведення теореми Семереді про існування довгих арифметичних прогресій у щільних підмножинах цілих чисел.

Див. також

• Теорема про кутики