thumb|350px|The '''independence complex''' of ''G''
The '''independence complex''' of a graph is a mathematical object describing the independent sets of the graph. Formally, the independence complex of an undirected graph ''G'', denoted by I(''G''), is an abstract simplicial complex (that is, a family of finite sets closed under the operation of taking subsets), formed by the sets of vertices in the independent sets of ''G''. Any subset of an independent set is itself an independent set, so I(''G'') is indeed closed under taking subsets.
Every independent set in a graph is a clique in its complement graph, and vice versa. Therefore, the independence complex of a graph equals the clique complex of its complement graph, and vice versa.
== Homology groups == Several authors studied the relations between the properties of a graph ''G'' = (''V'', ''E''), and the homology groups of its independence complex I(''G'').<ref name=":0">{{Cite journal|last=Meshulam|first=Roy|date=2003-05-01|title=Domination numbers and homology|journal=Journal of Combinatorial Theory, Series A|language=en|volume=102|issue=2|pages=321–330|doi=10.1016/S0097-3165(03)00045-1|issn=0097-3165|doi-access=free}}</ref> In particular, several properties related to the dominating sets in ''G'' guarantee that some reduced homology groups of I(''G'') are trivial.
1. The ''total'' ''domination number'' of G, denoted <math>\gamma_0(G)</math>, is the minimum cardinality of a total dominating set of ''G -'' a set ''S'' such that every vertex of V is adjacent to a vertex of ''S''. If <math>\gamma_0(G)>k</math> then <math>\tilde{H}_{k-1}(I(G))=0</math>.<ref>{{Cite book|last=Chudnovsky|first=Maria|title=Systems of disjoint representatives (M.Sc. thesis)|publisher=Technion, department of mathematics|year=2000|location=Haifa, Israel}}</ref>
2. The ''total domination number'' of a subset ''A'' of ''V'' in G, denoted <math>\gamma_0(G,A)</math>, is the minimum cardinality of a set ''S'' such that every vertex of ''A'' is adjacent to a vertex of ''S''. The ''independence domination number'' of G, denoted <math>i \gamma(G)</math>, is the maximum, over all independent sets ''A'' in ''G'', of <math>\gamma_0(G,A)</math>. If <math>i \gamma(G) > k</math>, then <math>\tilde{H}_{k-1}(I(G))=0</math>.<ref name=":0" /><ref>{{Cite journal|last1=Aharoni|first1=Ron|last2=Haxell|first2=Penny|date=2000|title=Hall's theorem for hypergraphs|journal=Journal of Graph Theory|volume=35|issue=2|pages=83–88|doi=10.1002/1097-0118(200010)35:2<83::aid-jgt2>3.0.co;2-v|issn=0364-9024}}</ref>
3. The ''domination number'' of ''G'', denoted <math>\gamma(G)</math>, is the minimum cardinality of a dominating set of G - a set ''S'' such that every vertex of V \ S is adjacent to a vertex of ''S''. Note that <math> \gamma_0(G)\geq \gamma(G) </math>. If ''G'' is a chordal graph and <math>\gamma(G)>k</math> then <math>\tilde{H}_{k-1}(I(G))=0</math>.<ref>{{Cite journal|last1=Aharoni|first1=Ron|last2=Berger|first2=Eli|last3=Ziv|first3=Ran|date=2002-07-01|title=A Tree Version of Kőnig's Theorem|journal=Combinatorica|volume=22|issue=3|pages=335–343|doi=10.1007/s004930200016|s2cid=38277360|issn=0209-9683}}</ref>
4. The ''induced matching number'' of ''G'', denoted <math>\mu(G)</math>, is the largest cardinality of an induced matching in ''G'' - a matching that includes every edge connecting any two vertices in the subset. If there exists a subset ''A'' of ''V'' such that <math>\gamma_0(G,A)>k+\min[k, \mu(G[A])]</math> then <math>\tilde{H}_{k-1}(I(G))=0</math>.<ref name=":3">{{Cite journal|last=Meshulam|first=Roy|date=2001-01-01|title=The Clique Complex and Hypergraph Matching|journal=Combinatorica|language=en|volume=21|issue=1|pages=89–94|doi=10.1007/s004930170006|s2cid=207006642|issn=1439-6912}}</ref> This is a generalization of both properties 1 and 2 above.
5. The ''non-dominating independence complex'' of G, denoted I'(''G''), is the abstract simplicial complex of the independent sets that are not dominating sets of ''G''. Obviously I'(''G'') is contained in I(''G''); denote the inclusion map by <math>i: I'(G)\to I(G)</math>. If ''G'' is a chordal graph then the induced map <math>i_*: \tilde{H}_k(I'(G))\to \tilde{H}_k(I(G))</math> is zero for all <math>k\geq -1</math>.<ref name=":0" />{{Rp|Thm.1.4}} This is a generalization of property 3 above.
6. The ''fractional star-domination number'' of G, denoted <math>\gamma^*_s(G)</math>, is the minimum size of a fractional star-dominating set in ''G''. If <math>\gamma^*_s(G)>k</math> then <math>\tilde{H}_{k-1}(I(G))=0</math>.<ref name=":0" />{{Rp|Thm.1.5}}
== Related concepts == '''Meshulam's game''' is a game played on a graph ''G'', that can be used to calculate a lower bound on the homological connectivity of the independence complex of ''G''.
The '''matching complex''' of a graph ''G'', denoted M(''G''), is an abstract simplicial complex of the matchings in ''G''. It is the independence complex of the line graph of ''G''.<ref>{{Cite journal|last1=Björner|first1=A.|last2=Lovász|first2=L.|last3=Vrećica|first3=S. T.|last4=Živaljević|first4=R. T.|date=1994|title=Chessboard Complexes and Matching Complexes|journal=Journal of the London Mathematical Society|language=en|volume=49|issue=1|pages=25–39|doi=10.1112/jlms/49.1.25|issn=1469-7750}}</ref><ref>{{Cite journal|last1=Reiner|first1=Victor|last2=Roberts|first2=Joel|date=2000-03-01|title=Minimal Resolutions and the Homology of Matching and Chessboard Complexes|journal=Journal of Algebraic Combinatorics|language=en|volume=11|issue=2|pages=135–154|doi=10.1023/A:1008728115910|issn=1572-9192|doi-access=free}}</ref>
The '''(''m'',''n'')-chessboard complex''' is the matching complex on the complete bipartite graph ''K<sub>m</sub>,<sub>n</sub>''. It is the abstract simplicial complex of all sets of positions on an ''m''-by-''n'' chessboard, on which it is possible to put rooks without each of them threatening the other.<ref>{{Cite journal|last1=Friedman|first1=Joel|last2=Hanlon|first2=Phil|date=1998-09-01|title=On the Betti Numbers of Chessboard Complexes|journal=Journal of Algebraic Combinatorics|language=en|volume=8|issue=2|pages=193–203|doi=10.1023/A:1008693929682|issn=1572-9192|doi-access=free|hdl=2027.42/46302|hdl-access=free}}</ref><ref>{{Cite journal|last=Ziegler|first=Günter M.|authorlink=Günter M. Ziegler|date=1994-02-01|title=Shellability of chessboard complexes|journal=Israel Journal of Mathematics|language=en|volume=87|issue=1|pages=97–110|doi=10.1007/BF02772986|doi-access=|s2cid=59040033|issn=1565-8511}}</ref>
The '''clique complex''' of G is the independence complex of the complement graph of ''G''.
== See also ==
== References == {{reflist}}
Category:Simplicial sets Category:Simplicial homology Category:Graph theory objects