# Vertex Coloring with Bound on Number of Monochromatic Edges

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}$$?

• The number of non-monochromatic edges is not $|E(G)|-X$. That would imply you can count the non-monochromatic edges just by counting the red and blue vertices. But it also matters how you arrange them; e.g., if half the vertices are red and half are blue along an even cycle, they can alternate (for $0$ monochromatic edges) or come in two big monochromatic blocks (for $m-2$ monochromatic edges). Feb 19, 2020 at 15:13
• @MishaLavrov okay, yes I see that now... I edited my idea. Does this make it possible to Chernoff's? Is that even what I am to be using? (it just seems like it would work for this problem)
– user641658
Feb 20, 2020 at 20:21

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.