Generalized Ramsey Numbers in the Hypercube

Abstract

We study the generalized Ramsey numbers $f(Q_n,C_k,q)$, that is, the minimum number of colors needed to edge-color the hypercube $Q_n$ so that every copy of the cycle $C_k$ has at least $q$ colors. Our main result is that for any integers $k,q$ satisfying $k\ge 6$ and $3\le q\le k/2+1$, we have $f(Q_n,C_k,q)=o\left(n^{\frac{k/2-1}{k-q+1}}\right).$ We also prove a few other upper and lower bounds in the special cases $k=4$ and $k=6$. This continues the line of research initiated by Faudree, Gyárfás, Lesniak, and Schelp and Mubayi and Stading who studied the case $k=q$, and by Conder who considered the case $k=6$ and $q=2$.

12 pages, 3 figures