Lema odstranění grafu

Lema odstranění grafu říká, že pokud graf obsahuje více kopií daného podgrafu , pak všechny jeho kopie lze odstranit odstraněním malého počtu hran [1] . Lema se někdy nazývá lemma odstranění trojúhelníku , když podgrafem je trojúhelník [2] .

Formulace

Nechť existuje graf s vrcholy. Pak pro jakýkoli graf s vrcholy, který má izomorfní podgrafy , lze odstranit všechny tyto podgrafy odstraněním hran z . Zde to znamená "o malý" [1] . $H$ $h$ $G$ $n$ $o(n^{h})$ $H$ $o(n^{2})$ $G$ $Ó$

Důkazy a zobecnění

Lemma odstranění grafu bylo původně prokázáno pro případ, kdy podgrafem je trojúhelník, v roce 1978 Imre Z. Rouge a Endre Szemeredy pomocí Szemeredyho lemma pravidelnosti [3] . Později bylo lemma rozšířeno na další typy podgrafů [4] — řízené grafy [5] a hypergrafy [6] . Alternativní důkaz poskytující silnější hranice počtu hran, které mají být odstraněny v závislosti na počtu kopií podgrafu, publikoval Jacob Fox v roce 2011 [1] .

Aplikace

Rouge a Szemerédy formulovali lemma odstranění trojúhelníku, aby poskytli subkvadratické horní hranice pro Rouge-Szemerédyho problém o velikosti grafů, ve kterých jakákoli hrana patří jedinému trojúhelníku . Lema odstranění grafu má aplikace v testování vlastností , protože z něj vyplývá, že v jakémkoli grafu je buď graf téměř bez grafu , nebo náhodné vzorky snadno najdou kopii v grafu [5] . Lema odstranění hypergrafu lze použít k prokázání Szemerédyho věty o existenci dlouhých aritmetických posloupností v hustých podmnožinách celých čísel [6] . $H$ $H$

Poznámky

↑ 1 2 3 Jacob Fox. Nový důkaz lemmatu odstranění grafu // Annals of Mathematics . - 2011. - T. 174 , č.p. 1 . — S. 561–579 . - doi : 10.4007/annals.2011.174.1.17 .
↑ Luca Trevisan. Lemma odstranění trojúhelníku . - 2009. - Květen.
↑ Imre Z. Ruzsa, Endre Szemerédi. Kombinatorika (Proc. Fifth Hungarian Colloq., Keszthely, 1976), sv. II. - North-Holland, 1978. - T. 18 . — S. 939–945 .
↑ Paul Erdős, Peter Frankl, Vojtěch Rödl. Asymptotický počet grafů neobsahujících pevný podgraf a problém pro hypergrafy bez exponentu // Grafy a kombinatorika. - 1986. - Vol. 2 , vydání. 2 . — S. 113–121 . - doi : 10.1007/BF01788085 .
↑ 1 2 Noga Alon, Asaf Shapira. Testování podgrafů v orientovaných grafech // Journal of Computer and System Sciences. - 2004. - T. 69 , č. 3 . — S. 353–382 . - doi : 10.1016/j.jcss.2004.04.008 .
↑ 1 2 Terence Tao. Varianta lemmatu odstranění hypergrafu // Journal of Combinatorial Theory. - 2006. - T. 113 , č. 7 . - S. 1257-1280 . - doi : 10.1016/j.jcta.2005.11.006 .