Coloring the cube with rainbow cycles (Q1953479)

Summary: For every even positive integer \(k\geq 4\) let \(f(n,k)\) denote the minimim number of colors required to color the edges of the \(n\)-dimensional cube \(Q_n\), so that the edges of every copy of the \(k\)-cycle \(C_k\) receive \(k\) distinct colors. \textit{R. J. Faudree} et al. [J. Graph Theory 17, No. 5, 607--612 (1993; Zbl 0788.05042)] proved that \(f(n,4)=n\) for \(n=4\) or \(n>5\). We consider larger \(k\) and prove that if \(k \equiv 0\) (mod 4), then there are positive constants \(c_1, c_2\) depending only on \(k\) such that \[ c_1n^{k/4} < f(n,k) < c_2 n^{k/4}. \] Our upper bound uses an old construction of \textit{R. C. Bose} and \textit{S. Chowla} [Comment. Math. Helv. 37, 141--147 (1962; Zbl 0109.03301)] of generalized Sidon sets. For \(k \equiv 2\) (mod 4), the situation seems more complicated. For the smallest case \(k=6\) we show that \[ 3n-2 \leq f(n, 6) < n^{1+o(1)} \] with the lower bound holding for \(n \geq 3\). The upper bound is obtained from Behrend's construction of a subset of integers with no three term arithmetic progression.