This function returns the size of the smallest induced cycle of a graph. It is based upon Theorem 2.1 in the paper "Restricting linear syzygies: algebra and geometry" by Eisenbud, Green, Hulek, and Popsecu. This theorem states that if G is graph, then the edge ideal of the complement of G satisfies property N_{2,p}, that is, the resolution of I(G^c) is linear up to the p-th step, if and only if the smallest induced cycle of G has length p+3. The algorithm looks at the resolution of the edge ideal of the complement to determine the size of the smallest cycle.
i1 : T = QQ[x_1..x_9]; |
i2 : g = graph {x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_5*x_6,x_6*x_7,x_7*x_8,x_8*x_9,x_9*x_1} -- a 9-cycle
o2 = Graph{edges => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }}}
1 2 2 3 3 4 4 5 5 6 6 7 7 8 1 9 8 9
ring => T
vertices => {x , x , x , x , x , x , x , x , x }
1 2 3 4 5 6 7 8 9
o2 : Graph
|
i3 : smallestCycleSize g o3 = 9 |
i4 : h = graph {x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_5*x_6,x_6*x_7,x_7*x_8,x_8*x_9} -- a tree (no cycles)
o4 = Graph{edges => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }}}
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9
ring => T
vertices => {x , x , x , x , x , x , x , x , x }
1 2 3 4 5 6 7 8 9
o4 : Graph
|
i5 : smallestCycleSize h o5 = infinity o5 : InfiniteNumber |
i6 : l = graph {x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_5*x_6,x_6*x_7,x_7*x_8,x_8*x_9,x_9*x_1,x_1*x_4}
o6 = Graph{edges => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }}}
1 2 2 3 1 4 3 4 4 5 5 6 6 7 7 8 1 9 8 9
ring => T
vertices => {x , x , x , x , x , x , x , x , x }
1 2 3 4 5 6 7 8 9
o6 : Graph
|
i7 : smallestCycleSize l o7 = 4 |
Note that G is a tree if and only if smallestCycleSize G is infinity.
The object smallestCycleSize is a method function.