Lema de eliminare a graficelor

Lema de îndepărtare a grafului afirmă că, dacă un graf conține mai multe copii ale unui subgraf dat , atunci toate copiile acestuia pot fi eliminate prin eliminarea unui număr mic de muchii [1] . Lema este uneori numită lema de îndepărtare a triunghiului când subgraful este un triunghi [2] .

Formulare

Să fie un grafic cu vârfuri. Apoi, pentru orice graf cu vârfuri care are subgrafe izomorfe , se pot elimina toate aceste subgrafe eliminând muchiile din . Aici înseamnă „o mic” [1] . $H$ $h$ $G$ $n$ $o(n^{h})$ $H$ $o(n^{2})$ $G$ $o$

Dovezi și generalizări

Lema de eliminare a graficelor a fost demonstrată inițial pentru cazul în care subgraful este un triunghi în 1978 de către Imre Z. Rouge și Endre Szemeredy folosind Lema de regularitate a lui Szemeredy [3] . Ulterior, lema a fost extinsă la alte tipuri de subgrafe [4] —grafice direcționate [5] și hipergrafe [6] . O dovadă alternativă care oferă limite mai puternice asupra numărului de muchii care trebuie eliminate în funcție de numărul de copii subgraf a fost publicată de Jacob Fox în 2011 [1] .

Aplicații

Rouge și Szemerédy au formulat lema de eliminare a triunghiului pentru a furniza limite superioare subquadratice pentru problema Rouge–Szemerédy pe dimensiunea graficelor în care orice muchie aparține unui singur triunghi . Lema de eliminare a graficului are aplicații în testarea proprietăților , deoarece implică faptul că în orice grafic, fie graficul este aproape fără grafic , fie eșantioanele aleatoare pot găsi cu ușurință o copie în grafic [5] . Lema de eliminare a hipergrafului poate fi folosită pentru a demonstra teorema lui Szemerédy asupra existenței unor progresii aritmetice lungi în submulțimi dense de numere întregi [6] . $H$ $H$

Note

↑ 1 2 3 Jacob Fox. O nouă dovadă a lemei de eliminare a graficelor // Analele matematicii . - 2011. - T. 174 , nr. 1 . — S. 561–579 . - doi : 10.4007/annals.2011.174.1.17 .
↑ Luca Trevisan. Lema de eliminare a triunghiului . - 2009. - Mai.
↑ Imre Z. Ruzsa, Endre Szemerédi. Combinatorică (Proc. Al cincilea coloc maghiar, Keszthely, 1976), voi. II. - Olanda de Nord, 1978. - T. 18 . — S. 939–945 .
↑ Paul Erdős, Peter Frankl, Vojtěch Rödl. Numărul asimptotic de grafice care nu conțin un subgraf fix și o problemă pentru hipergrafele fără exponent // Grafice și combinatorie. - 1986. - Vol. 2 , numărul. 2 . — S. 113–121 . - doi : 10.1007/BF01788085 .
↑ 1 2 Noga Alon, Asaf Shapira. Testarea subgrafelor în grafice direcționate // 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. O variantă a lemei de eliminare a hipergrafului // Journal of Combinatorial Theory. - 2006. - T. 113 , nr. 7 . - S. 1257-1280 . - doi : 10.1016/j.jcta.2005.11.006 .