# independenceComplex -- returns the independence complex of a (hyper)graph

## Synopsis

• Usage:
D = independenceComplex H
• Inputs:
• H, ,
• Outputs:
• D, , the independence complex associated to the (hyper)graph

## Description

This function associates to a (hyper)graph a simplicial complex whose faces correspond to the independent sets of the (hyper)graph. See, for example, the paper of A. Van Tuyl and R. Villarreal "Shellable graphs and sequentially Cohen-Macaulay bipartite graphs," Journal of Combinatorial Theory, Series A 115 (2008) 799-814.

 i1 : S = QQ[a..e]; i2 : g = graph {a*b,b*c,c*d,d*e,e*a} -- the 5-cycle o2 = Graph{edges => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}} ring => S vertices => {a, b, c, d, e} o2 : Graph i3 : independenceComplex g o3 = simplicialComplex | ce be bd ad ac | o3 : SimplicialComplex i4 : h = hyperGraph {a*b*c,b*c*d,d*e} o4 = HyperGraph{edges => {{a, b, c}, {b, c, d}, {d, e}}} ring => S vertices => {a, b, c, d, e} o4 : HyperGraph i5 : independenceComplex h o5 = simplicialComplex | bce ace abe acd abd | o5 : SimplicialComplex

Equivalently, the independence complex is the simplicial complex associated to the edge ideal of the (hyper)graph H via the Stanley-Reisner correspondence.

 i6 : S = QQ[a..e]; i7 : g = graph {a*b,b*c,a*c,d*e,a*e} o7 = Graph{edges => {{a, b}, {a, c}, {b, c}, {a, e}, {d, e}}} ring => S vertices => {a, b, c, d, e} o7 : Graph i8 : Delta1 = independenceComplex g o8 = simplicialComplex | ce be cd bd ad | o8 : SimplicialComplex i9 : Delta2 = simplicialComplex edgeIdeal g o9 = simplicialComplex | ce be cd bd ad | o9 : SimplicialComplex i10 : Delta1 === Delta2 o10 = true