# Complete graph coloring with cycle restriction

The following question is probably open (It was posted on AoPS a long time ago, but no one has a solution)

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$.

I have no idea how to solve this. Helps will be really appreciate

Theorem: Let $c$ be an edge-coloring of $K_n$ such that no two Hamiltonian cycles have the same set of colors. Then $c\geq (1+o(1))\left(\frac{n}{e}\right)^2$.
Proof: There are $(n-1)!/2$ Hamiltonian cycles, and $\sum_{i=1}^{n} \binom{c}{i}$ subsets of $c$ of size at most $n$. As each Hamiltonian cycle corresponds to a different such subset, we get the inequality $$(n-1)!/2 \leq \sum_{i=1}^{n} \binom{c}{i}.$$ Recalling that $(n-1)!/2=((1+o(1))\left(\frac{n}{e}\right))^n$ and that (for $c>2n$, which we can assume here) $\sum_{i=1}^{n} \binom{c}{i}=((1+o(1))\left(\frac{c \cdot e}{n}\right))^n$, we have $$((1+o(1))\left(\frac{n}{e}\right))^n\leq\left(\frac{c \cdot e}{n}\right)^n ,$$ which yields the theorem.
• Just a minor inessential point: the most usual convention these days is that $K^n$ has $\frac12(n-1)!$ Hamilton cycles=(undirected simple 2-regular spanning subgraphs), not $(n-1)!$. Just check your formula for $K^3$, which has 1 Hamilton cycle only. And it is this convention which is the appropriate one for your proof, since the idea of a direction of Hamilton cycles is unrelated to the idea of counting not-necessarily-proper edge-colorings thereof. – Peter Heinig Oct 1 '17 at 8:52
• Just to add a quantity of useful context and interconnectedness: a relevant MO-thread on 'initial sums of the familiar sum $\sum_{0\leq i\leq n}\binom{n}{i}=2^n$ ' is this MO thread. Estimating such sums is essential to carrying through Zur Luria's proof. – Peter Heinig Oct 1 '17 at 9:48
• While your proof seems essentially correct, I personally think the use of $(n-1)!$ instead of $\frac12(n-1)!$, and moreover the use of $\sum_{i=1}^{n-1}\binom{c}{i}$ instead of $\sum_{i=1}^{n}\binom{c}{i}$ (after all, a Hamilton cycle in $K^n$ has $n$ edges, not $n-1$) are almost-wrong, or puzzling at least. Note that from the correct terms there results a weaker inequality, namely $\frac12(n-1)!\leq\sum_{i=1}^{n}\binom{c}{i}$, which is weaker in that it has both a smaller small side and a larger large side. Your argument seems to get through though. Do you agree? – Peter Heinig Oct 1 '17 at 12:38