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 ?
\left
and\right
. $\endgroup$ – joriki May 11 '20 at 18:01