Лема про видалення трикутників

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

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

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

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

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

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

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

Див. також

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

Примітки

1. Jacob Fox. A new proof of the graph removal lemma // Annals of Mathematics. — 2011. — Т. 174, вип. 1. — С. 561–579. — DOI:10.4007/annals.2011.174.1.17.
2. Luca Trevisan. The Triangle Removal Lemma. — 2009. — Травень.
3. Imre Z. Ruzsa, Endre Szemerédi. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II. — North-Holland, 1978. — Т. 18. — С. 939–945.
4. Paul Erdős, Peter Frankl, Vojtěch Rödl. The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent // Graphs and Combinatorics. — 1986. — Т. 2, вип. 2. — С. 113–121. — DOI:10.1007/BF01788085.
5. Noga Alon, Asaf Shapira. Testing subgraphs in directed graphs // Journal of Computer and System Sciences. — 2004. — Т. 69, вип. 3. — С. 353–382. — DOI:10.1016/j.jcss.2004.04.008.
6. Terence Tao. A variant of the hypergraph removal lemma // Journal of Combinatorial Theory. — 2006. — Т. 113, вип. 7. — С. 1257–1280. — DOI:10.1016/j.jcta.2005.11.006.