Лема про видалення графа
Ле́ма про ви́далення графа стверджує, що якщо граф містить кілька копій даного підграфа, всі його копії можна виключити видаленням малого числа ребер[1]. Лему іноді називають ле́мою про ви́далення трику́тників у разі, коли підграф є трикутником[2].
Нехай — граф з вершинами. Тоді для будь-якого графа з вершинами, який має ізоморфних підграфів можна виключити всі ці підграфи, видаливши ребер з . Тут означає "o мале"[1].
Лему про видалення графа спочатку довели для випадку, коли підграф є трикутником, Імре З. Ружа і Ендре Семереді (1978), використавши лему регулярності Семереді[3]. Пізніше лему розширено на інші типи підграфів[4] — на орієнтовані графи[5] і гіперграфи[6]. Альтернативне доведення, що дає сильніші межі кількості ребер, які потрібно видалити, як функцію числа копій підграфа, опублікував 2011 року Якоб Фокс[1].
Ружа і Семереді сформулювали лему про видалення трикутників, щоб забезпечити підквадратичні верхні межі задачі Ружі — Семереді від розміру графів, у яких будь-яке ребро належить єдиному трикутнику. Лема про видалення графа застосовується в тестуванні властивостей[en], оскільки з неї випливає, що в будь-якому графі, або граф майже вільний від графа , або випадковими вибірками легко знайти копію у графі[5]. Лему про видалення гіперграфа можна використати для доведення теореми Семереді про існування довгих арифметичних прогресій у щільних підмножинах цілих чисел[6].
- ↑ а б в 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.
- ↑ Luca Trevisan. The Triangle Removal Lemma. — 2009. — Травень.
- ↑ Imre Z. Ruzsa, Endre Szemerédi. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II. — North-Holland, 1978. — Т. 18. — С. 939–945.
- ↑ 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.
- ↑ а б 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.
- ↑ а б 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.