Periods in missing lengths of rainbow cycles

A cycle in an edge‐colored graph is said to be rainbow if no two of its edges have the same color. For a complete, infinite, edge‐colored graph G , define\documentclass{article}\usepackage{amssymb}\usepackage[mathscr]{euscript}\footskip=0pc \pagestyle{empty}\begin{document}\begin{eqnarray*} {\mathscr{G}}({G}) = \{ {n} \ge {2} | {\rm {no}}\, {n{-}{\rm {cycle \, of}}} \,{{G}}\, {{\rm {is}\, {\rm {rainbow}}}}\}.\end{eqnarray*}\end{document} Then ( G ) is a monoid with respect to the operation n ∘ m = n + m −2, and thus there is a least positive integer π( G ), the period of ( G ), such that ( G ) contains the arithmetic progression { N + k π( G )| k ⩾0} for some sufficiently large N . Given that n ∈( G ), what can be said about π( G )? Alexeev showed that π( G )=1 when n ⩾3 is odd, and conjectured that π( G ) always divides 4. We prove Alexeev's conjecture: Let p ( n )=1 when n is odd, p ( n )=2 when n is divisible by four, and p ( n )=4 otherwise. If 2< n ∈( G ) then π( G ) is a divisor of p ( n ). Moreover, ( G ) contains the arithmetic progression { N + kp ( n )| k ⩾0} for some N = O ( n 2 ). The key observations are: If 2< n =2 k ∈( G ) then 3 n −8∈( G ). If 16≠ n =4 k ∈( G ) then 3 n −10∈( G ). The main result cannot be improved since for every k >0 there are G , H such that 4 k ∈( G ), π( G )=2, and 4 k + 2∈( H ), π( H )=4. © 2009 Wiley Periodicals, Inc. J Graph Theory