Macaulay2 » Documentation
Packages » EdgeIdeals :: independenceComplex
next | previous | forward | backward | up | index | toc

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 = 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

See also

Ways to use independenceComplex :

For the programmer

The object independenceComplex is a method function.