Lemma för borttagning av grafer

Grafborttagningslemmat säger att om en graf innehåller flera kopior av en given subgraf , så kan alla dess kopior elimineras genom att ta bort ett litet antal kanter [1] . Lemma kallas ibland triangelborttagningslemma när subgrafen är en triangel [2] .

Formulering

Låt det finnas en graf med hörn. Sedan för alla grafer med hörn som har isomorfa subgrafer kan man eliminera alla dessa subgrafer genom att ta bort kanter från . Här betyder det "o liten" [1] . $H$ $h$ $G$ $n$ $o(n^{h})$ $H$ $o(n^{2})$ $G$ $o$

Bevis och generaliseringar

Graph Removal Lemma bevisades ursprungligen för fallet där subgrafen är en triangel 1978 av Imre Z. Rouge och Endre Szemeredy med hjälp av Szemeredys Regularity Lemma [3] . Senare utvidgades lemmat till andra typer av subgrafer [4] — riktade grafer [5] och hypergrafer [6] . Ett alternativt bevis som ger starkare gränser för antalet kanter som ska tas bort som en funktion av antalet subgrafkopior publicerades av Jacob Fox 2011 [1] .

Applikationer

Rouge och Szemerédy formulerade triangelborttagningslemmat för att ge subkvadratiska övre gränser för Rouge-Szemerédy-problemet på storleken på grafer där vilken kant som helst tillhör en enda triangel . Lemmat för borttagning av grafer har applikationer i egenskapstestning , eftersom det antyder att i vilken graf som helst, antingen är grafen nästan graffri eller så kan slumpmässiga prover lätt hitta en kopia i grafen [5] . Lemmat för borttagning av hypergraf kan användas för att bevisa Szemerédys teorem om förekomsten av långa aritmetiska progressioner i täta delmängder av heltal [6] . $H$ $H$

Anteckningar

↑ 1 2 3 Jacob Fox. Ett nytt bevis på grafborttagningslemma // Annals of Mathematics . - 2011. - T. 174 , nr. 1 . — S. 561–579 . - doi : 10.4007/annals.2011.174.1.17 .
↑ Luca Trevisan. Lemma för borttagning av triangeln . - 2009. - Maj.
↑ Imre Z. Ruzsa, Endre Szemerédi. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), vol. II. - Nord-Holland, 1978. - T. 18 . — S. 939–945 .
↑ Paul Erdős, Peter Frankl, Vojtěch Rödl. Det asymptotiska antalet grafer som inte innehåller en fast subgraf och ett problem för hypergrafer utan exponent // Graphs and Combinatorics. - 1986. - Vol. 2 , nummer. 2 . — S. 113–121 . - doi : 10.1007/BF01788085 .
↑ 1 2 Noga Alon, Asaf Shapira. Testa subgrafer i riktade grafer // Journal of Computer and System Sciences. - 2004. - T. 69 , nr. 3 . — S. 353–382 . - doi : 10.1016/j.jcss.2004.04.008 .
↑ 1 2 Terence Tao. En variant av lemma för borttagning av hypergraf // Journal of Combinatorial Theory. - 2006. - T. 113 , nr. 7 . - S. 1257-1280 . - doi : 10.1016/j.jcta.2005.11.006 .