next | previous | forward | backward | up | top | index | toc | directory | Macaulay 2 web site

allOddHoles -- returns all odd 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 odd hole is an odd induced cycle of length at least 5.
i1 : R = QQ[x_1..x_6];
i2 : G = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6}) --5-cycle and a triangle

o2 = Graph{edges => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }}}
                       1   2     2   3     3   4     1   5     4   5     1   6     5   6
           ring => R
           vertices => {x , x , x , x , x , x }
                         1   2   3   4   5   6

o2 : Graph
i3 : allOddHoles G --only the 5-cycle should appear

o3 = {{x , x , x , x , x }}
        1   2   3   4   5

o3 : List
i4 : H = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6,x_1*x_4}) --no odd holes

o4 = Graph{edges => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }}}
                       1   2     2   3     1   4     3   4     1   5     4   5     1   6     5   6
           ring => R
           vertices => {x , x , x , x , x , x }
                         1   2   3   4   5   6

o4 : Graph
i5 : allOddHoles H

o5 = {}

o5 : List

See also

Ways to use allOddHoles :