Komplex nezávislosti - Independence complex

The komplex nezávislosti a graf je matematický objekt popisující nezávislé sady grafu. Formálně komplex nezávislosti neorientovaný graf G, označeno I (G), je abstraktní zjednodušený komplex (tj. rodina konečných množin uzavřených pod operací přijímání podmnožin), tvořená množinami vrcholů v nezávislé sady z G. Jakákoli podmnožina nezávislé množiny je sama o sobě nezávislou množinou, takže I (G) skutečně splňuje požadavek abstraktního zjednodušeného komplexu, že každá podskupina množiny v rodině by měla být také v rodině.

Každá nezávislá množina v grafu je a klika v jeho doplňkový graf a naopak. Proto se komplex nezávislosti grafu rovná klikový komplex jeho doplňkového grafu a naopak.

Homologické skupiny

Několik autorů studovalo vztahy mezi vlastnostmi grafu G = (PROTI, E) a homologické skupiny komplexu nezávislosti I (G).^[1] Zejména několik vlastností souvisejících s dominující sady v G zaručit, že někteří snížená homologie skupiny I (G) jsou triviální.

1. The celkový dominantní číslo G, označeno ${ displaystyle gamma _ {0} (G)}$, je minimální mohutnost sady celkem dominující sada z G - sada S tak, že každý vrchol V sousedí s vrcholem S. Li ${ displaystyle gamma _ {0} (G)> k}$ pak ${ displaystyle { tilde {H}} _ {k-1} (I (G)) = 0}$.^[2]

2. The celkové číslo dominance podmnožiny A z PROTI v G, označeno ${ displaystyle gamma _ {0} (G, A)}$, je minimální mohutnost sady S tak, že každý vrchol A sousedí s vrcholem S. The číslo dominance nezávislosti G, označeno ${ Displaystyle i gamma (G)}$, je maximum ve všech nezávislých sadách A v G, z ${ displaystyle gamma _ {0} (G, A)}$. Li ${ displaystyle i gamma (G)> k}$, pak ${ displaystyle { tilde {H}} _ {k-1} (I (G)) = 0}$.^[1][3]

3. The dominantní číslo z G, označeno ${ displaystyle gamma (G)}$, je minimální mohutnost a dominující sada G - sada S tak, že každý vrchol V S sousedí s vrcholem S. Všimněte si, že ${ displaystyle gamma _ {0} (G) geq gamma (G)}$. Li G je chordální graf a ${ displaystyle gamma (G)> k}$ pak ${ displaystyle { tilde {H}} _ {k-1} (I (G)) = 0}$.^[4]

4. The indukované odpovídající číslo z G, označeno ${ displaystyle mu (G)}$, je největší mohutnost indukované shody v G - shoda, která zahrnuje každou hranu spojující jakékoli dva vrcholy v podmnožině. Pokud existuje podmnožina A z PROTI takhle ${ displaystyle gamma _ {0} (G, A)> k + min [k, mu (G [A])]}$ pak ${ displaystyle { tilde {H}} _ {k-1} (I (G)) = 0}$.^[5] Toto je zevšeobecnění obou vlastností 1 a 2 výše.

5. The komplex dominující nezávislosti G, označeno I '(G), je abstraktní zjednodušený komplex nezávislých množin, které nejsou dominující sady z G. Je zřejmé, že '(G) je obsažen v I (G); označit mapu zařazení pomocí ${ displaystyle i: I '(G) to I (G)}$. Li G je chordální graf pak indukovaná mapa ${ displaystyle i _ {*}: { tilde {H}} _ {k} (I '(G)) na { tilde {H}} _ {k} (I (G))}$ je nula pro všechny ${ displaystyle k geq -1}$.^{[1]:Thm. 1.4} Toto je zobecnění vlastnosti 3 výše.

6. The zlomkové číslo dominance hvězd G, označeno ${ displaystyle gamma _ {s} ^ {*} (G)}$, je minimální velikost frakční hvězdné dominance G. Li ${ displaystyle gamma _ {s} ^ {*} (G)> k}$ pak ${ displaystyle { tilde {H}} _ {k-1} (I (G)) = 0}$.^{[1]:Thm. 1,5}

Související pojmy

Meshulamova hra je hra hraná v grafu G, které lze použít k výpočtu dolní meze na homologická konektivita komplexu nezávislosti G.

The odpovídající komplex grafu G, označeno M (G), je abstraktní zjednodušený komplex párování v G. Jedná se o komplex nezávislosti hranový graf z G.^[6][7]

The (m,n) - šachovnicový komplex je odpovídající komplex na úplném bipartitním grafu K._m,_n. Jedná se o abstraktní zjednodušený komplex všech sad pozic na m-podle-n šachovnice, na které je možné dát havrani aniž by každý z nich ohrožoval toho druhého.^[8][9]

The klikový komplex G je komplex nezávislosti doplňkový graf z G.

Viz také

• Sada nezávislá na duze

Reference