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

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

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

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

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

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

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

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

Див. також

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