Självständighetskomplex

Oberoendekomplexet för en graf är ett matematiskt objekt som beskriver de oberoende uppsättningarna av grafen. Formellt är oberoendekomplexet för en oriktad graf G , betecknad med I( G ), ett abstrakt förenklat komplex (det vill säga en familj av ändliga mängder slutna under operationen att ta delmängder), bildad av uppsättningarna av hörn i den oberoende uppsättningar av G. _ Varje delmängd av en oberoende uppsättning är i sig en oberoende uppsättning, så I( G ) är verkligen sluten med delmängder.

Varje oberoende uppsättning i en graf är en klick i dess komplementgraf , och vice versa. Därför är oberoendekomplexet för en graf lika med klickkomplexet för dess komplementgraf, och vice versa.

Homologigrupper

Flera författare studerade sambanden mellan egenskaperna hos en graf G = ( V , E ), och homologigrupperna i dess oberoendekomplex I( G ). I synnerhet garanterar flera egenskaper relaterade till de dominerande uppsättningarna i G att vissa reducerade homologigrupper av I( G ) är triviala.

1. Det totala dominanstalet för G, betecknat ${\displaystyle \gamma _{0}(G)} ,$ är den lägsta kardinaliteten för en total dominerande uppsättning av G - en mängd S så att varje vertex av V är intill en spets av S . Om $\gamma _{0}(G)>k$ så ${\tilde {H}}_{k-1 }(I(G))=0$ .

2. Det totala dominanstalet för en delmängd A av V i G, betecknad $\gamma _{0}(G,A)$ , är den minsta kardinaliteten för en mängd S så att varje vertex av A ligger intill en spets av S . Oberoendedominanstalet för G, betecknat ${\displaystyle i\gamma (G)} ,$ är det maximala, över alla oberoende mängder A i G , av $\gamma _{ 0}(G,A)$ . Om $i\gamma (G)>k$ , då ${\tilde {H}}_{k-1} (I(G))=0$ .

3. Dominanstalet för G , betecknat $\gamma (G)$ , är minimikardinaliteten för en dominerande uppsättning av G - en mängd S så att varje vertex av V \ S ligger intill en vertex av S. _ Observera att $\gamma _{0}(G)\geq \gamma (G)$ . Om G är en ackordsgraf och $\gamma (G)>k$ så är ${\tilde {H}}_{k -1}(I(G))=0$ .

4. Det inducerade matchningstalet för G , betecknat ${\displaystyle \mu (G)} ,$ är den största kardinaliteten av en inducerad matchning i G - en matchning som inkluderar varje kant som förbinder två hörn i delmängden. Om det finns en delmängd A av V så att $\gamma _{0}(G,A)>k+\min[ k,\mu (G[A])]$ sedan ${\tilde {H}}_{k-1}(I(G))=0$ . Detta är en generalisering av både egenskap 1 och 2 ovan.

5. Det icke-dominerande oberoende komplexet av G, betecknat I'( G ), är det abstrakta förenklade komplexet av de oberoende mängderna som inte är dominerande mängder av G . Uppenbarligen finns I'( G ) i I( G ); beteckna inklusionskartan med $i:I'(G)\to I(G)$ . Om G är en ackordsgraf så är den inducerade kartan ${\displaystyle i_{*}:{\tilde {H}}_{ k}(I'(G))\till {\tilde {H}}_{k}(I(G))} är noll$ för alla $k\geq -1$ . Detta är en generalisering av egenskap 3 ovan.

6. Bråktalet stjärndominerande antal för G, betecknat $\gamma _{s}^{*}(G)$ , är minimistorleken för en bråkdel stjärndominerande mängd i G . Om $\gamma _{s}^{*}(G)>k$ så ${\tilde {H} }_{k-1}(I(G))=0$ .

Relaterade begrepp

Meshulams spel är ett spel som spelas på en graf G , som kan användas för att beräkna en nedre gräns för den homologiska anslutningen av oberoendekomplexet G .

Matchningskomplexet för en graf G , betecknad M( G ) , är ett abstrakt förenklat komplex av matchningarna i G . Det är oberoendekomplexet för linjediagrammet för G .

( m , n )-schackbrädekomplexet är det matchande komplexet på den kompletta tvådelade grafen K _m , _n . Det är det abstrakta enkla komplexet av alla uppsättningar positioner på ett m -by- n schackbräde , på vilket det är möjligt att sätta torn utan att var och en av dem hotar den andra.

Klickkomplexet av G är oberoendekomplexet för komplementgrafen för G .

Se även

• Regnbågsoberoende set