# Probability that a random edge coloring of the complete graph is proper

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?

-

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.
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
@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