Biklikkmentes gráf

A matematika, azon belül a gráfelmélet területén egy gráf akkor t-biklikk-mentes (biclique-free), t-páros klikkmentes vagy t-teljes páros gráf-mentes, ha nem tartalmazza a 2t-csúcsú, tehát a K_t,t teljes páros gráfot részgráfjaként. Egy gráfcsalád akkor biklikkmentes, ha létezik olyan t szám, amire a család összes gráfja t-biklikkmentes. A biklikkmentes gráfok a ritka gráfok családjának egyik legáltalánosabb tagjai. Fellépnek diszkrét geometriai illeszkedési problémák kapcsán és parametrizált komplexitású problémákban is előkerülnek.

Tulajdonságok

Ritkaság

A Kővári–Sós–Turán-tétel szerint az n-csúcsú t-biklikkmentes gráfok éleinek nagyságrendje O(n^{2 − 1/t}), ami jóval kevesebb egy sűrű gráf éleinél.^[1] Megfordítva, ha egy gráfcsaládot tiltott részgráfjai alapján határozunk meg, illetve a részgráfképzés műveletére nézve zárt és nem tartalmaz tetszőlegesen nagyméretű sűrű gráfokat, akkor szükségképpen t-biklikkmentes valamely t értékre, különben nagy, sűrű teljes páros gráfokat kellene tartalmaznia.

Alsó korlátként (Erdős, Hajnal & Moon 1964) sejtése szerint minden maximális t-biklikkmentes páros gráf (maximális olyan értelemben, hogy nem adható hozzá további él anélkül, hogy t-biklikk jönne létre) legalább (t − 1)(n + m − t + 1) élt tartalmaz, ahol n és m a bipartíció két oldalának csúcsszámai.^[2]

Kapcsolat más ritkagráf-családokkal

Egy d degeneráltságú gráf szükségképpen (d + 1)-biklikkmentes. Ráadásul a sehol sem sűrű gráfok osztálya biklikkmentes. Általánosabban, ha létezik n-csúcsú gráf, ami a gráfcsalád egyetlen tagjának sem 1 mélységű korlátos mélységű minorja, akkor a család n-biklikkmentes, hiszen az összes n-csúcsú gráf a K_n,n 1 mélységű sekély minorja. Ily módon a biklikkmentes gráfcsaládok a ritka gráfok két, legáltalánosabb osztályát egyesítik.^[3]

Alkalmazások

Diszkrét geometria

A diszkrét geometria területén fellépő illeszkedési gráfok számos fajtája biklikkmentes. Erre egyszerű példa, hogy az euklideszi síkon véges számú pont és egyenes illeszkedési gráfja sohasem tartalmazza a K_2,2 részgráfot.^[4]

Parametrizált komplexitás

A parametrizált komplexitás területén a biklikkmentes gráfok olyan algoritmusokban bukkannak fel, melyek hatékonyan kezelnek megfelelően kicsi bemeneti értékekkel rendelkező ritka gráfokat. Konkrétan a t-biklikkmentes gráfokban a k méretű domináló csúcshalmaz keresése rögzített paraméter mellett kezelhető, ha a paraméter k + t, még akkor is, ha meggyőző bizonyítékok mutatnak arra, hogy ez nem lehetséges, ha kizárólag k a paraméter. Hasonló eredményeket igazoltak a domináló halmaz-probléma több változatára.^[3] Ugyanezzel a paraméterezéssel tesztelhető az is, hogy valamely, legfeljebb k méretű domináló halmaz átvihető-e egy másikba csúcsok hozzáadásának és törlésének láncolatán keresztül, miközben a domináló tulajdonság megmarad.^[5]

Jegyzetek

1. Kővári, T.; T. Sós, V. & Turán, P. (1954), "On a problem of K. Zarankiewicz", Colloquium Math. 3: 50–57, <http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3110.pdf>. Kővári Tamás, T. Sós Vera és Turán Pál munkája a biklikk-mentes páros gráfok élszámával foglalkozik, de a valószínűségi módszer standard alkalmazásával ugyanezt a korlátot tetszőleges gráfokra is el lehet érni.
2. Erdős, P.; Hajnal, A. & Moon, J. W. (1964), "A problem in graph theory", The American Mathematical Monthly 71: 1107–1110, doi:10.2307/2311408, <http://www.renyi.hu/~p_erdos/1964-02.pdf>.
3. Telle, Jan Arne & Villanger, Yngve (2012), "FPT algorithms for domination in biclique-free graphs", in Epstein, Leah & Ferragina, Paolo, Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings, vol. 7501, Lecture Notes in Computer Science, Springer, pp. 802–812, DOI 10.1007/978-3-642-33090-2_69.
4. Kaplan, Haim; Matoušek, Jiří & Sharir, Micha (2012), "Simple proofs of classical theorems in discrete geometry via the Guth–Katz polynomial partitioning technique", Discrete and Computational Geometry 48 (3): 499–517, DOI 10.1007/s00454-012-9443-3. Lásd a Lemma 3.1-et és az azt követő megjegyzéseket.
5. Lokshtanov, Daniel; Mouawad, Amer E. & Panolan, Fahad et al. (2015), "Reconfiguration on sparse graphs", in Dehne, Frank; Sack, Jörg-Rüdiger & Stege, Ulrike, Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015, Proceedings, vol. 9214, Lecture Notes in Computer Science, Springer, pp. 506–517, doi:10.1007/978-3-319-21840-3_42, <http://folk.uib.no/amo110/assets/papers/WADS2015TW.pdf>. Hozzáférés ideje: 2017-05-24 Archiválva 2017. november 13-i dátummal a Wayback Machine-ben Archivált másolat. [2017. november 13-i dátummal az eredetiből archiválva]. (Hozzáférés: 2017. május 24.)Archivált másolat. [2017. november 13-i dátummal az eredetiből archiválva]. (Hozzáférés: 2017. május 24.).