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


As far as I can see, this question has a simple solution.

Let's limit ourselves to Hamiltonian cycles, and forget about the constraint that the coloring is legal.

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.

| cite | improve this answer | |
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Heinig Oct 1 '17 at 8:52
  • $\begingroup$ 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. $\endgroup$ – Peter Heinig Oct 1 '17 at 9:48
  • $\begingroup$ 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? $\endgroup$ – Peter Heinig Oct 1 '17 at 12:38
  • 1
    $\begingroup$ I agree with everything that you have said. I will make the changes. $\endgroup$ – Zur Luria Oct 1 '17 at 13:30

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.