Macaulay2 » Documentation
Packages » EdgeIdeals :: allEvenHoles
next | previous | forward | backward | up | index | toc

allEvenHoles -- returns all even holes in a graph

Synopsis

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

See also

Ways to use allEvenHoles :

For the programmer

The object allEvenHoles is a method function.