smallestCycleSize -- returns the size of the smallest induced cycle of a graph

Synopsis

Usage:

s = smallestCycleSize(G)
Inputs:
- G, a graph, the input
Outputs:
- s, an integer, the size of the smallest induced cycle

Description

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.

Ways to use smallestCycleSize:

smallestCycleSize(Graph)

For the programmer

The object smallestCycleSize is a method function.