Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.