<?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>allEvenHoles -- returns all even holes in a graph</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="_all__Odd__Holes.html">next</a> | <a href="_adjacency__Matrix.html">previous</a> | <a href="_all__Odd__Holes.html">forward</a> | <a href="_adjacency__Matrix.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>allEvenHoles -- returns all even holes in a graph</h1>
<div class="single"><h2>Synopsis</h2>
<ul><li><div class="list"><dl class="element"><dt class="heading">Usage: </dt><dd class="value"><div><tt>L = allEvenHoles G</tt></div>
</dd></dl>
</div>
</li>
<li><div class="single">Inputs:<ul><li><span><tt>G</tt>, <span>a <a href="___Graph.html">graph</a></span></span></li>
</ul>
</div>
</li>
<li><div class="single">Outputs:<ul><li><span><tt>L</tt>, <span>a <a href="../../Macaulay2Doc/html/___List.html">list</a></span>, returns all even holes contained in <tt>G</tt>.</span></li>
</ul>
</div>
</li>
</ul>
</div>
<div class="single"><h2>Description</h2>
<div><p>The method is based on work of Francisco-Ha-Van Tuyl, looking at the associated primes of the square of the Alexander dual of the edge ideal. An even hole is an even induced cycle (necessarily of length at least four). The algorithm for allEvenHoles uses an observation of Mermin. Fix an edge, and split this edge into two different edges, introducing a new vertex. Find all the odd holes in that graph. Do that for each edge in the graph, one at a time, and pick out all the odd holes containing the additional vertex. Dropping this vertex from each of the odd holes gives all the even holes in the original graph.</p>
<div>See C.A. Francisco, H.T. Ha, A. Van Tuyl, "Algebraic methods for detecting odd holes in a graph." (2008) Preprint. <tt>arXiv:0806.1159v1</tt>.</div>
<table class="examples"><tr><td><pre>i1 : R = QQ[a..f];</pre>
</td></tr>
<tr><td><pre>i2 : G = cycle(R,6);</pre>
</td></tr>
<tr><td><pre>i3 : allEvenHoles G
o3 = {{a, b, c, d, e, f}}
o3 : List</pre>
</td></tr>
<tr><td><pre>i4 : H = graph(monomialIdeal(a*b,b*c,c*d,d*e,e*f,a*f,a*d)) --6-cycle with a chord
o4 = Graph{edges => {{a, b}, {b, c}, {a, d}, {c, d}, {d, e}, {a, f}, {e, f}}}
ring => R
vertices => {a, b, c, d, e, f}
o4 : Graph</pre>
</td></tr>
<tr><td><pre>i5 : allEvenHoles H --two 4-cycles
o5 = {{a, b, c, d}, {a, d, e, f}}
o5 : List</pre>
</td></tr>
</table>
</div>
</div>
<div class="single"><h2>See also</h2>
<ul><li><span><a href="_all__Odd__Holes.html" title="returns all odd holes in a graph">allOddHoles</a> -- returns all odd holes in a graph</span></li>
<li><span><a href="_has__Odd__Hole.html" title="tells whether a graph contains an odd hole">hasOddHole</a> -- tells whether a graph contains an odd hole</span></li>
</ul>
</div>
<div class="waystouse"><h2>Ways to use <tt>allEvenHoles</tt> :</h2>
<ul><li>allEvenHoles(Graph)</li>
</ul>
</div>
</div>
</body>
</html>
