MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a repost of this question that I am posting here since it received no attention there.

What is the probability that a random edge coloring of $K_n$ with $m \geq n$ colors results in a proper coloring ?

By random edge coloring I mean that every edge is assigned a color from $\{1,\ldots,m\}$ uniformly at random.

If we define the event $E_i$ to mean that edge $e_i$ is not incident with an edge of the same color class of the event $V_i$ that vertex $v_i$ is incident with edges of distinct colors, then it is easy to get a bound for the above probabiity in terms of $Pr[E_i]$ or $Pr[V_i]$ by using the union bound.

The problem is that it appears that such approach only gives bounds that make sense only when $m = \mathcal(n^2)$ which is not interesting.

Hence I am wondering if there is a more sensitive way to bound/compute the above probability?

share|cite|improve this question
up vote 2 down vote accepted

Let $p(n)$ be this probability. Now consider you coloured $K_{n-1}$ successfully and add one new vertex. As the edges from the new vertex is coloured, there are simple bounds on how many colours are available. I get that the $i$-th new edge ($i$ starting at 0) has between $m-n+2-i$ and $m-n+2$ colours available. Therefore $$ \frac {(m-n+2)!}{m^{n-1} (m-2n+3)!} \le \frac{p(n)}{p(n-1)} \le \frac{(m-n+2)^{n-1}}{m^{n-1}}.$$ Multiply these ratios together to bound $p(n)$. The left bound starts to bite when $m\ge 2n-3$, the right bound earlier.

I'm sure this can be improved.

share|cite|improve this answer
Hm.. I am not able to obtain a constant lower bound for $p(n)$ from these bounds. Is it possible to do so? If not, can this be improved so that $O(n)$ edges guarantee that a random edge-coloring is proper with a probability of (say ) at least 1/2? – Jernej Oct 7 '14 at 9:56
@Jernej: I don't understand "O(n) edges". Do you mean colours? – Brendan McKay Oct 7 '14 at 10:38
Err - yes yes, colors! – Jernej Oct 7 '14 at 11:26
@Jerneq: You need $\Omega(n^2)$ colours just to have $\Omega(1)$ probability that the colours at a single vertex are distinct. This is the birthday paradox. – Brendan McKay Oct 7 '14 at 21:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.