allEvenHoles -- returns all odd holes in a graph

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.

i1 : R = QQ[a..f];

i2 : G = cycle(R,6);

i3 : allEvenHoles G

o3 = {{a, b, c, d, e, f}}

o3 : List

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

i5 : allEvenHoles H --two 4-cycles

o5 = {{a, b, c, d}, {a, d, e, f}}

o5 : List