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

Extended Example -- an extended example using EdgeIdeals

This is an example from the write-up of the EdgeIdeals package in the Journal of Software for Algebra and Geometry: Macaulay 2.

At the heart of the EdgeIdeals package are two new classes that are entitled HyperGraph and Graph. The HyperGraph class can only be used to represent hypergraphs. The class Graph extends from HyperGraph and inherits all of the methods of HyperGraph. Functions have been made that accept objects of either type as input.

In our example below, we illustrate Theorem 6.4.7 from R. Villarreal's Monomial Algebras, which says that the independence complex of a Cohen-Macaulay bipartite graph has a simplicial shelling. We begin by creating a graph and verifying the Cohen-Macaulay and bipartite properties.

i1 : R = QQ[x_1..x_3,y_1..y_3];
i2 : G = graph(R,{x_1*y_1,x_2*y_2,x_3*y_3, x_1*y_2,x_1*y_3,x_2*y_3})

o2 = Graph{edges => {{x , y }, {x , y }, {x , y }, {x , y }, {x , y }, {x , y }}}
                       1   1     2   2     3   3     1   2     1   3     2   3
           ring => R
           vertices => {x , x , x , y , y , y }
                         1   2   3   1   2   3

o2 : Graph
i3 : isCM G and isBipartite G

o3 = true

When defining a (hyper)graph, the user specifies the vertex set by defining a polynomial ring, while the edges are written as a list of square-free monomials (there are alternative ways of listing the edges). A (hyper)graph is stored as a hash table which contains the list of edges, the polynomial ring, and the list of vertices.

i4 : L = getGoodLeaf(G)

o4 = {x , y }
       1   1

o4 : List
i5 : degreeVertex(G,y_1)

o5 = 1
i6 : H = inducedHyperGraph(G, vertices(G) - set(L))

o6 = HyperGraph{edges => {{x , y }, {x , y }, {x , y }}}
                            2   2     3   3     2   3
                ring => QQ[x ..y ]
                            2   3
                vertices => {x , x , y , y }
                              2   3   2   3

o6 : HyperGraph

A Cohen-Macaulay bipartite graph must contain a leaf, which we retrieve above. We remove the leaf, to form the induced graph, and at the same time, we identify the vertex of degree one in the leaf.

i7 : K = simplicialComplexToHyperGraph independenceComplex H;
i8 : edges K

o8 = {{x , x }, {x , y }, {y , y }}
        2   3     3   2     2   3

o8 : List

Above, we formed the independence complex of H, that is, the simplicial complex whose facets correspond to the maximal independent sets of H. We then change the type from a simplicial complex to a hypergraph, which we call K. Notice that these edges give a shelling.

i9 : use ring K;
i10 : A = apply(edges(K), e->append(e, y_1));
i11 : B = apply(edges inducedHyperGraph(K, {x_2,x_3}), e-> append(e, x_1));
i12 : shelling = join(A,B)

o12 = {{x , x , y }, {x , y , y }, {y , y , y }, {x , x , x }}
         2   3   1     3   2   1     2   3   1     2   3   1

o12 : List
i13 : independenceComplex(G)

o13 = | y_1y_2y_3 x_3y_1y_2 x_2x_3y_1 x_1x_2x_3 |

o13 : SimplicialComplex

Using the method found in the proof of Theorem 6.4.7 from R. Villarreal's Monomial Algebras, we now can form a shelling of the original independence complex. Notice that our shelling is a permutation of the facets of the independence complex defined from G.

See also