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

Question

Suppose we color the edges $\{1,\ldots, {n \choose 2}\}$ of the complete graph on $n$ vertices with $m$ colors each edge being assigned a color picked uniformly at random from $\{1,\ldots, m\}.$

I would like to estimate the probability that the obtained random coloring is proper, that is all edges incident with a vertex $v$ are colored with different colors.

One way to do this is as follows. Suppose $E_i$ is the event that the edge $e_i$ of $K_n$ is colored with a color that already occurs at its adjacent edges. Then $$Pr[E_i] = \frac{1}{m} (1 - (1-\frac{1}{m})^{2n-4})$$ and thus the probability that $G$ is not colored properly is estimated as $$Pr[E_1\cup \ldots E_{n \choose 2}] \leq \frac{n(n-1)}{2m} (1 - (1-\frac{1}{m})^{2n-4} )$$

Now this is not a good estimate since the right hand size is larger then one for any $m$ that is not "large enough".

Another way to estimate this is to define the event $V_i$ to be that the $i$th vertex of our graph is incident with edges of distinct colors and use a similar estimate. But again the given bound is not very sharp.

Hence I am wondering is there a more delicate way to estimate the mentioned probability? Is this known? Is there a different way to model this ?

Answer 1

A possible strategy is the following (I did not work on details, e.g. might work for even/odd $n$ only, and the expressions may not be accurate, but the general idea is hopefully clear) -

Starting from a graph with no edge, we add colored edges in iterations, such that in iteration $i$ each node has degree $2i$ (or $i$ for even $n$?). Let $p_i$ be the probability of success until the end of iteration $i$, and $q_i$ the probability of failing before the end of iteration $i$. Then considering we add $n$ new edges in iteration $i$, we have:

$$ p_{i-1} \cdot \left(1-\frac{4i}{m}\right)^n \le p_i \le p_{i-1} \cdot \left(1-\frac{2i}{m}\right)^n$$

which makes it easy to estimate the desired probability $p_{n/2}$. Also, the failure probability can be estimated combining the above with the following:

$$q_i = q_{i-1} + (1-q_{i-1})\cdot (1-p_{i})$$

Though I'm not sure if this is a sufficiently delicate solution!