<?xml version="1.0" encoding="utf-8" ?> <!-- for emacs: -*- coding: utf-8 -*- -->
<!-- Apache may like this line in the file .htaccess: AddCharset utf-8 .html -->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0 plus SVG 1.1//EN" "http://www.w3.org/2002/04/xhtml-math-svg/xhtml-math-svg-flat.dtd" >
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head><title>Extended Example -- an extended example using EdgeIdeals</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="_get__Cliques.html">next</a> | <a href="_edges.html">previous</a> | <a href="_get__Cliques.html">forward</a> | <a href="_edges.html">backward</a> | up | <a href="index.html">top</a> | <a href="master.html">index</a> | <a href="toc.html">toc</a> | <a href="http://www.math.uiuc.edu/Macaulay2/">Macaulay2 web site</a></div>
</td>
</tr>
</table>
<hr/>
<div><h1>Extended Example -- an extended example using EdgeIdeals</h1>
<div><p>This is an example from the write-up of the <em>EdgeIdeals</em> package in the <em>Journal of Software for Algebra and Geometry: Macaulay 2</em>.</p>
<p>At the heart of the <em>EdgeIdeals</em> package are two new classes that are entitled <a href="___Hyper__Graph.html" title="a class for hypergraphs">HyperGraph</a> and <a href="___Graph.html" title="a class for graphs">Graph</a>. The <a href="___Hyper__Graph.html" title="a class for hypergraphs">HyperGraph</a> class can only be used to represent hypergraphs. The class <a href="___Graph.html" title="a class for graphs">Graph</a> extends from <a href="___Hyper__Graph.html" title="a class for hypergraphs">HyperGraph</a> and inherits all of the methods of <a href="___Hyper__Graph.html" title="a class for hypergraphs">HyperGraph</a>. Functions have been made that accept objects of either type as input.</p>
<p>In our example below, we illustrate Theorem 6.4.7 from R. Villarreal's <em>Monomial Algebras</em>, 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.</p>
<table class="examples"><tr><td><pre>i1 : R = QQ[x_1..x_3,y_1..y_3];</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>i3 : isCM G and isBipartite G
o3 = true</pre>
</td></tr>
</table>
<p>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.</p>
<table class="examples"><tr><td><pre>i4 : L = getGoodLeaf(G)
o4 = {x , y }
1 1
o4 : List</pre>
</td></tr>
<tr><td><pre>i5 : degreeVertex(G,y_1)
o5 = 1</pre>
</td></tr>
<tr><td><pre>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 , x , y , y ]
2 3 2 3
vertices => {x , x , y , y }
2 3 2 3
o6 : HyperGraph</pre>
</td></tr>
</table>
<p>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.</p>
<table class="examples"><tr><td><pre>i7 : K = simplicialComplexToHyperGraph independenceComplex H;</pre>
</td></tr>
<tr><td><pre>i8 : edges K
o8 = {{x , x }, {x , y }, {y , y }}
2 3 3 2 2 3
o8 : List</pre>
</td></tr>
</table>
<p>Above, we formed the independence complex of <tt>H</tt>, that is, the simplicial complex whose facets correspond to the maximal independent sets of <tt>H</tt>. We then change the type from a simplicial complex to a hypergraph, which we call <tt>K</tt>. Notice that these edges give a shelling.</p>
<table class="examples"><tr><td><pre>i9 : use ring K;</pre>
</td></tr>
<tr><td><pre>i10 : A = apply(edges(K), e->append(e, y_1));</pre>
</td></tr>
<tr><td><pre>i11 : B = apply(edges inducedHyperGraph(K, {x_2,x_3}), e-> append(e, x_1));</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>i13 : independenceComplex(G)
o13 = | y_1y_2y_3 x_3y_1y_2 x_2x_3y_1 x_1x_2x_3 |
o13 : SimplicialComplex</pre>
</td></tr>
</table>
<p>Using the method found in the proof of Theorem 6.4.7 from R. Villarreal's <em>Monomial Algebras</em>, 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 <tt>G</tt>.</p>
</div>
<div class="single"><h2>See also</h2>
<ul><li><span><a href="___Constructor_sp__Overview.html" title="a summary of the many ways of making graphs and hypergraphs">Constructor Overview</a> -- a summary of the many ways of making graphs and hypergraphs</span></li>
<li><span><a href="___Graph.html" title="a class for graphs">Graph</a> -- a class for graphs</span></li>
<li><span><a href="___Hyper__Graph.html" title="a class for hypergraphs">HyperGraph</a> -- a class for hypergraphs</span></li>
<li><span><a href="_graph.html" title="constructor for Graph">graph</a> -- constructor for Graph</span></li>
<li><span><a href="_hyper__Graph.html" title="constructor for HyperGraph">hyperGraph</a> -- constructor for HyperGraph</span></li>
<li><span><a href="_is__C__M.html" title="determines if a (hyper)graph is Cohen-Macaulay">isCM</a> -- determines if a (hyper)graph is Cohen-Macaulay</span></li>
<li><span><a href="_is__Bipartite.html" title="determines if a graph is bipartite">isBipartite</a> -- determines if a graph is bipartite</span></li>
<li><span><a href="_get__Good__Leaf.html" title="returns an edge that is a good leaf">getGoodLeaf</a> -- returns an edge that is a good leaf</span></li>
<li><span><a href="_degree__Vertex.html" title="returns the degree of a vertex">degreeVertex</a> -- returns the degree of a vertex</span></li>
<li><span><a href="_induced__Hyper__Graph.html" title="returns the induced subgraph of a (hyper)graph">inducedHyperGraph</a> -- returns the induced subgraph of a (hyper)graph</span></li>
<li><span><a href="_simplicial__Complex__To__Hyper__Graph.html" title="makes a (hyper)graph from a simplicial complex">simplicialComplexToHyperGraph</a> -- makes a (hyper)graph from a simplicial complex</span></li>
<li><span><a href="_edges.html" title="gets the edges of a (hyper)graph">edges</a> -- gets the edges of a (hyper)graph</span></li>
<li><span><a href="_independence__Complex.html" title="returns the independence complex of a (hyper)graph">independenceComplex</a> -- returns the independence complex of a (hyper)graph</span></li>
</ul>
</div>
</div>
</body>
</html>
