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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.