Vertex Coloring with Bound on Number of Monochromatic Edges

Question

Problem:

Let G be a graph with m edges. Prove that the vertices of G can be colored red and blue so that the number k of non-monochromatic edges satisfies $$\frac{m}{2}-\sqrt{m} \leq k \leq \frac{m}{2}+\sqrt{m}$$

Idea for Proof:

Edit:

Color each vertex red or blue independently with probability $\frac{1}{2}$. Let $A_e$ be the event that e is non-monochromatic and let $X_e$ be its indicator. So $X_e = 1$ if e is non-monochromatic and $X_e = 0$ if e is monochromatic. Let $X = \sum_{e\in E(G)} X_e$, giving the number of non-chromatic edges.

Then, each edge is non-monochromatic with probability $\frac{1}{2}$, so $E[X]=\frac{m}{2}$.

To use Chernoff's inequality we need independence of the random variables.

Claim: for any two edges $e=uv,f=xy \in E(G)$, $X_e$ and $X_f$ are independent random variables.

Case 1: The two edges do not share a vertex. There are $2^4=16$ color assignments for the four vertices u, v, x, and y. There are exactly 4 color assignments where both e and f are non-monochromatic. Then the probability that both e and f are non-monochromatic is $\frac{4}{16}=\frac{1}{4}$.

i.e. $P[X_e=1$ and $X_f=1]=\frac{1}{4} = \frac{1}{2}\cdot \frac{1}{2} = P[X_e=1]\cdot P[X_f=1]$.

Case 2: The two edges share one vertex.

Then there are $2^3=8$ possible color assignment for the three vertices u, v=x, and y (assuming WLOG v=x). There are exactly 2 color assignments where both e and f are non-monochromatic. Then the probability that both e and f are non-monochromatic is $\frac{2}{8}=\frac{1}{4}$.

i.e. $P[X_e=1$ and $X_f=1]=\frac{1}{4} = \frac{1}{2}\cdot \frac{1}{2} = P[X_e=1]\cdot P[X_f=1]$.

Now is it possible to use Chernoff's? Chernoff's: (under certains conditions of the r.v.'s), for any $t\geq0$, $$P[X\geq E[X] + t] \leq e^{\frac{-t^2}{2Var[X]+t/3}}$$ And in this situation, $t=\sqrt{m}$?

Answer 1

We cannot use Chernoff bounds, because the variables $(X_e)_{e \in E(G)}$ are not, in fact, independent.

Consider a graph with vertices $1, 2, 3$ and edges $12, 13, 23$. Then $X_{12}, X_{13}, X_{23}$ have a nontrivial relationship: $X_{12} + X_{13} + X_{23}$, the total number of non-monochromatic edges, can be either $0$ (if all three vertices are the same color) or $2$ (otherwise). It cannot be $1$ or $3$. That means that if we know $X_{12}$ and $X_{13}$, then we can deduce $X_{23}$: the variables are not independent.

What they are - and what your argument shows they are - is pairwise independent. One consequence of that is that the sum $X = \sum_{e \in E(G)} X_e$ has the same variance as the binomial distribution. We can see this by computing \begin{align} \mathbb E[X^2] &= \mathbb E\left[\left(\sum_{e \in E(G)} X_e\right)^2\right] \\ &= \sum_{e \in E(G)} \mathbb E[X_e^2] + \sum_{\substack{e, f \in E(G) \\ e \ne f}} \mathbb E[X_e X_f] \\ &= \sum_{e \in E(G)} \frac12 + \sum_{\substack{e, f \in E(G) \\ e \ne f}} \frac14 \\ &= \frac12 m + \frac14 m(m-1) = \frac14 m^2 + \frac14m. \end{align} Meanwhile, $\mathbb E[X] = \frac12m$, so $\operatorname{Var}[X] = \mathbb E[X^2] - \mathbb E[X]^2 = \frac14m$.

(Side note: this calculation only relied on knowing $\mathbb E[X_e X_f] = \mathbb E[X_e] \mathbb E[X_f]$, which is why we get the same result any time that we have pairwise independent random variables.)

For a Chernoff bound, all $m$ of the variables must be mutually independent. But when we only have pairwise independence, we can exploit that using Chebyshev's inequality. This says that $$ \Pr[ |X - \mathbb E[X]| \ge t] \le \frac{\operatorname{Var}[X]}{t^2} $$ and in our case, if we set $t = \sqrt m$, we get $\Pr[ |X - \frac12m| \ge \sqrt m] \le \frac14$.

With probability at least $\frac34$, we have $\frac12 m - \sqrt m \le X \le \frac12m + \sqrt m$, which means in particular that some such outcome must exist.