4
$\begingroup$

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

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 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
    Commented Oct 1, 2017 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
    Commented Oct 1, 2017 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
    Commented Oct 1, 2017 at 12:38
  • 1
    $\begingroup$ I agree with everything that you have said. I will make the changes. $\endgroup$
    – Zur Luria
    Commented Oct 1, 2017 at 13:30
  • $\begingroup$ (This is perhaps naive, but) out of interest, does the inequality $\left(\frac{n}{e}\right)^n\leq \sum_{i=1}^n{c\choose i}$ hold for general values of $c$? Or just those corresponding to edge colourings? $\endgroup$
    – a196884
    Commented Sep 28, 2022 at 16:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .