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

## Synopsis

• Usage:
s = smallestCycleSize(G)
• Inputs:
• G, , 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 .