Graafiteoriassa t - beaclick - free graafi on graafi, jossa ei ole täydellisiä kaksiosaisia graafia , joissa on 2 t kärkipistettä K t , t aligraafina. Graafiperhe on vapaa biklikeistä, jos on olemassa luku t siten, että perheen kaikki graafit ovat vapaita t -klikeistä. Polkupyörättömien kaavioiden perheet ovat yksi yleisimmistä harvalukuisten kaavioiden perhetyypeistä . Ne syntyvät kombinatorisen geometrian esiintymisongelmissa ja niitä käytetään myös parametrisessa kompleksisuusteoriassa .
Kovari -Cos-Turan-lauseen mukaan missä tahansa t -pyörättömässä graafissa, jossa on n kärkeä, on O ( n 2 − 1/ t ) reunaa, ts. graafi on paljon harvinaisempi kuin tiheä graafi [1] . Päinvastoin, jos graafiperhe määritellään kielletyillä aligraafilla tai se on suljettu alagraafien ottamisen alaisena eikä sisällä tiheitä, mielivaltaisen suurikokoisia graafisia, siinä ei saa olla t -klikkejä joillekin t : ille , muuten perheen tulee sisältää mielivaltaisen suuria tiheitä. täydelliset kaaviot, kaksiosaiset kaaviot.
Alarajana Erdős, Hajnal ja Muun [2] arvelivat , että kaikilla maksimaalisella t -kaksiklikittomalla kaksiosaisella graafilla (johon ei voida lisätä reunaa luomatta t -kaksiklikkiä) on vähintään ( t − 1)( n ) + m − t + 1) reunat, missä n ja m ovat pisteiden lukumäärä graafin jokaisessa osassa [3] .
Graafi, jossa on degeneraatio d , on välttämättä vapaa ( d + 1) -biklikeistä. Lisäksi kaksiklikkivapaiden graafien perhe ei saa olla missään tiheä, mikä tarkoittaa, että mille tahansa luvulle k on olemassa graafi, joka ei ole minkään perheen graafin k - matala molli . Erityisesti, jos on olemassa n - pisteinen graafi, joka ei ole 1-matala molli, niin perheen tulee olla vapaa n -klikkeistä, koska kaikki n -pisteiset graafit ovat graafin K n , n 1-matalia molliarvoja . Siten kaksiklikkittömät graafiperheet yhdistävät kaksi yleisintä harvalukuisten graafien luokkaa [4] .
Kombinatorisessa geometriassa monen tyyppisten ilmaantuvuuskaavioiden tiedetään olevan vapaita bi-klikeistä. Yksinkertaisena esimerkkinä voidaan todeta, että euklidisen tason äärellisen pisteiden ja viivojen joukon insidenssikaavio ei todellakaan sisällä K 2,2 -osagraafia [5] .
Biklikkivapaita graafeja käytetään parametrisessa kompleksisuusteoriassa kehittämään algoritmeja, jotka ovat tehokkaita harvassa graafissa, jossa on riittävän pienet syöttöparametrit. Erityisesti hallitsevan k - koon joukon löytäminen t -kaksoisnapsautusvapaissa kaavioissa on kiinteän parametrin ratkaistava ongelma k + t -parametrilla , vaikka on hyviä syitä, että tämä ei ole mahdollista vain k -parametrilla ilman t :tä . Samat tulokset pätevät moniin hallitsevan joukkoongelman muunnelmiin [4] . Sen tarkistaminen, onko hallitsevan joukon kokoa enintään k , voidaan myös muuntaa toiseksi tarkistukseksi samalla parametrisoinnilla ketjuttamalla kärkien lisäykset ja poistot, säilyttäen dominanssiominaisuuden [6] .