Let $G$ be a graph of order $n$ with $m$ edges. Color each vertices uniformly at random with $q$ colors. It is easy to see that expected number of monochromatic edges (edge whose end vertices are of same color) equal to $\frac{m}{q}$. Let $t \leq \frac{m}{q}$, is it possible to show (assuming $q= o(m)$) $$ \mathbb{P}(\text{Monochromatic edges} \leq t)\leq e^{t-c\frac{m}{q}(1+o(1))} $$ where $c$ is an absolute constant. I tried using Janson's inequality but was unsuccessful.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Can you be more precise about the assumption $q<<m$? $\endgroup$– Yuval PeresCommented Nov 5, 2019 at 18:14
-
$\begingroup$ I am interested in the regime when $q=o(m)$ as $m$ goes to infinity. Let me know if I can clarify this more. Thank you. $\endgroup$– Suman ChakrabortyCommented Nov 5, 2019 at 18:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Such an estimate cannot hold in general. Here are two different counterexamples:
Consider a complete bipartite graph with $n/2$ nodes on each side and $m=n^2/4$ edges. Take $q$ bounded, e.g. $q=2$. Then for $q=2$, with probability $2^{-n}$ all left nodes are blue and all right nodes are red, so there are no monochromatic edges.
Consider $q$ large and let $m=(q\log q)/2$. Let $G$ be a star on $n=m+1$ nodes. By a standard coupon collector argument. with probability tending to 1, the $m$ nodes of the star leave $q^{1/2}(1+o(1)$ colors unused; if the central node takes ones of these colors, then there are no monochromatic edges. This has probability $q^{-1/2}(1+o(1)$.
answered Nov 5, 2019 at 22:56
-
$\begingroup$ The examples are very helpful. Thank you. $\endgroup$ Commented Nov 5, 2019 at 23:50