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
math154
04.02.2013 21:44
This is a nice problem, so here are some hints.
For convenience, we can restrict ourselves to a subgraph $H$ of $G$ in which every vertex has "large" degree (here, for instance, at least $|E(G)|/|V(G)| = n/10$).
Hint 2Consider the following simpler (but related) problem: Fix $m\ge2$. At least how many $2m$-cycles must $G$ have? (An asymptotic lower bound in terms of $n$ is enough.)
Hint 3Let $u_{i,j}$ be the number of distinct (simple) paths of length $5$ (in $H$) between $v_i$ and $v_j$. Then $\frac{1}{\binom{n}{2}}\sum{u_{i,j}}$ is at least... (How does the color condition fit in?)
dgrozev
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?
math154
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.
Remon
28.05.2021 16:28
Is there any full solution？
Remon
28.06.2021 15:42
This question is totally different from the original version posted by math154.