Consider a graph $G$ with $n$ vertices and at least $n^2/10$ edges. Suppose that each edge is colored in one of $c$ colors such that no two incident edges have the same color. Assume further that no cycles of size $10$ have the same set of colors. Prove that there is a constant $k$ such that $c$ is at least $kn^\frac{8}{5}$ for any $n$. David Yang.
Problem
Source: ELMO Shortlist 2012, C7
Tags: combinatorics proposed, combinatorics
04.02.2013 21:44
This is a nice problem, so here are some hints.
28.03.2013 06:51
I also think it is a nice problem. Could You give a little bit more details about hint 2 and 3?
28.03.2013 17:35
dgrozev wrote: Could You give a little bit more details about hint 2 and 3? Hmm, I don't remember all the details (I might've fakesolved it when I made my last post ), but I think it goes something like this: Order the $c^5$ possible $5$-tuples of colors and let $t_k$ be the number of pairs $(i,j)$ with some simple $5$-edge-path from $v_i$ to $v_j$ having the $k$th tuple of colors. Note that for fixed $k,i,j$, there can be at most one such path from $v_i$ to $v_j$ (by the edge-incidence condition). Then we have \[ \sum_k t_k = \sum_{(i,j)} u_{i,j} = \Omega(n^6), \]and \[ \sum \binom{t_k}{2} \ge c^5\binom{\Omega(n^6)/c^5}{2} = c^{-5} \Omega(n^{12}). \]Now it suffices to show that $\sum \binom{t_k}{2} = O(n^4)$, but I don't remember how to do this. (We can interpret $\sum \binom{t_k}{2}$ as $\sum_{(i,j),(i',j')}\#(\text{color-tuples shared})$, but there are lots of bad cases.) BTW, I've posted the original (easier?) version here.
28.05.2021 16:28
Is there any full solution?
28.06.2021 15:42
This question is totally different from the original version posted by math154.