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`.

- Constructor Overview -- a summary of the many ways of making graphs and hypergraphs
- Graph -- a class for graphs
- HyperGraph -- a class for hypergraphs
- graph -- constructor for Graph
- hyperGraph -- constructor for HyperGraph
- isCM -- determines if a (hyper)graph is Cohen-Macaulay
- isBipartite -- determines if a graph is bipartite
- getGoodLeaf -- returns an edge that is a good leaf
- degreeVertex -- returns the degree of a vertex
- inducedHyperGraph -- returns the induced subgraph of a (hyper)graph
- simplicialComplexToHyperGraph -- makes a (hyper)graph from a simplicial complex
- edges -- gets the edges of a (hyper)graph
- independenceComplex -- returns the independence complex of a (hyper)graph