6
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Jernej
    Commented Oct 7, 2014 at 9:56
  • $\begingroup$ @Jernej: I don't understand "O(n) edges". Do you mean colours? $\endgroup$
    – Brendan McKay
    Commented Oct 7, 2014 at 10:38
  • $\begingroup$ Err - yes yes, colors! $\endgroup$
    – Jernej
    Commented Oct 7, 2014 at 11:26
  • $\begingroup$ @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. $\endgroup$
    – Brendan McKay
    Commented Oct 7, 2014 at 21:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .