This is a repost of this math.se 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?


1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$
    – Jernej
    Oct 7, 2014 at 9:56
  • $\begingroup$ @Jernej: I don't understand "O(n) edges". Do you mean colours? $\endgroup$ Oct 7, 2014 at 10:38
  • $\begingroup$ Err - yes yes, colors! $\endgroup$
    – Jernej
    Oct 7, 2014 at 11:26
  • $\begingroup$ @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. $\endgroup$ Oct 7, 2014 at 21:53

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.