Periods in missing lengths of rainbow cycles

Abstract

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 $\mathfrak{S}(G)=\{n\ge 2\;|\;\text{no $n$-cycleof$G$ is rainbow}\}$. Then $\mathfrak{S}(G)$ is a monoid with respect to the operation $n\circ m=n+m-2$, and thus there is a least positive integer $\pi (G)$, the period of $\mathfrak{S}(G)$, such that $\mathfrak{S}(G)$ contains the arithmetic progression $\{N+k\pi (G)|k\ge 0\}$ for some sufficiently large $N$. Given that $n\in \mathfrak{S}(G)$, what can be said about $\pi (G)$? Alexeev showed that $\pi (G)=1$ when $n\ge 3$ is odd, and conjectured that $\pi (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\in \mathfrak{S}(G)$ then $\pi (G)$ is a divisor of $p(n)$. Moreover, $\mathfrak{S}(G)$ contains the arithmetic progression $\{N+kp(n)|k\ge 0\}$ for some $N=O(n^2)$. The key observations are: If $2<n=2k\in \mathfrak{S}(G)$ then $3n-8\in \mathfrak{S}(G)$. If $16\ne n=4k\in \mathfrak{S}(G)$ then $3n-10\in \mathfrak{S}(G)$. The main result cannot be improved since for every $k>0$ there are $G$, $H$ such that $4k\in \mathfrak{S}(G)$, $\pi (G)=2$, and $4k+2\in \mathfrak{S}(H)$, $\pi (H)=4$.