# allEvenHoles -- returns all even holes in a graph

## Synopsis

• Usage:
L = allEvenHoles G
• Inputs:
• G, ,
• Outputs:
• L, a list, returns all even holes contained in G.

## Description

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.

See C.A. Francisco, H.T. Ha, A. Van Tuyl, "Algebraic methods for detecting odd holes in a graph." (2008) Preprint. arXiv:0806.1159v1.

 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