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 ?

  • $\begingroup$ You can get properly sized parentheses (and other paired delimiters) that adjust to the size of their content by preceding them with \left and \right. $\endgroup$
    – joriki
    May 11 '20 at 18:01

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!


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.