# Complete graph coloring with cycle restriction

We have a complete graph with $n$ vertices. Each edge is colored in one of $c$ colors such that no two incident edges have the same color. Assume that no two cycles of the same size have the same set of colors. Prove $c$ is at least $n^2/50000000$.

The problem was posted a long time ago on AoPS but there is still no solution.

• This kind of "open problem" question might be better suited to mathoverflow.net – JRyan Sep 30 '17 at 11:38
• @JRyan What do you mean? $5 \geq 16/50000000$ is most certainly true. – orlp Sep 30 '17 at 12:00
• Quite right, thought the inequality was the other way around. Need more sleep! Thanks! – JRyan Sep 30 '17 at 12:10

Consider all cycles of size $k$. There are $\binom nk \cdot \frac{k!}{2k}$ different ways to choose the cycle: you choose $k$ vertices, then you choose a permutation of them, then you divide by all $2k$ rotations and reflections of the cycle. On the other hand, the number of ways to choose a set of at most $k$ colors is $$\binom c1 + \binom c2 + \dots + \binom ck.$$ So we have the inequality $$\binom nk \cdot \frac{k!}{2k} \le \binom c1 + \binom c2 + \dots + \binom ck$$ for all $k$.
We'll set $k = n/2$, put a lower bound on the left-hand side of the inequality, and an upper bound on the right-hand side.
For the right-hand side, the standard bound puts it at $\left(\frac{ce}{k}\right)^k = \left(\frac{2ce}{n}\right)^{n/2}$ at most. For the left-hand side, we have $$\binom nk \cdot \frac{k!}{2k} = \frac{n!}{(n/2)!(n)} = \frac{(n-1)!}{(n/2)!} = (n-1)(n-2)(\dots)(n/2+1) \ge (n/2)^{n/2-1}.$$ So we get $$(n/2)^{n/2-1} \le \left(\frac{2ce}{n}\right)^{n/2} \implies \frac e2 n (n/2)^{1-1/n} \le c.$$
We can rewrite this lower bound on $c$ as $$\frac e2 \frac{n^2}{n^{1/n} 2^{1-1/n}} = \left(\frac {e}{2 n^{1/n}2^{1-1/n}}\right) n^2 = \left(\frac {e}{4 (n/2)^{1/n}}\right) n^2.$$ The coefficient of $n^2$ is minimized when $n=5$, and $\frac{e}{4(5/2)^{1/5}}$ is comfortably bigger than $\frac1{50000000}$.