next | previous | forward | backward | up | top | index | toc | Macaulay2 website
EdgeIdeals :: independenceComplex

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

Synopsis

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 = | 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 = | 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 = | ce be cd bd ad |

o8 : SimplicialComplex
i9 : Delta2 = simplicialComplex edgeIdeal g

o9 = | ce be cd bd ad |

o9 : SimplicialComplex
i10 : Delta1 == Delta2

o10 = true

See also

Ways to use independenceComplex :

For the programmer

The object independenceComplex is a method function.