I'm currently working on the exercises of Noga Alon's book "The Probabilistic method". One exercise said that we are given a graph $H$ with $p$ vertices and that there exists a graph $G$ with $n > p$ vertices and $m$ edges containing no copy of $H$.
We have to prove that if we have $k > \frac{n^2ln(n)}m$ and we can find a $k$-coloring of a complete graph $K_n$ with $k$ colors then there exists a graph with no monochromatic $H$. I know this should be proved with probabilistic method, I just don't know how. Could any one give me a hint?
Best Answer
Suppose we have $k$ copies of $G$, $i.e. $ $G_{1}$,$G_{2}$, $...$ $G_{k}$, where all edges of $G_{i}$ are colored by color $i$. Now successively and randomly lay $G_{i}$ on top of $K_{n}$. $i.e. $ color a random copy of $G_{i}$ in $K_{n}$ with color $i$. We ignore the previous coloring of the edge that has been colored more than once. The very last coloring of the edge matters. If there is a monochromatic subgraph of $K_{n}$, then the subgraph must be a subgraph of $G_{i}$ which contains no subgraph $H$. That is to say, coloring the $K_{n}$ this way, there can be no monochromatic $H$. Thus, it is sufficient to show it is possible to color the whole $K_{n}$ in this way.
Let $X_{e}$ be the random variable which indicates whether $e\in{E}$ is colored by some $G_{i}$.
$X_e=\cases {1,&if $e\in{E}\wedge{e\notin{\cup{G_{i}}}}$\cr 0,&\text{else}\cr}$
It's easy to see $E[X_e]=\left(1-\frac{m}{\binom{n}{2}}\right)^{k}.$ Let $X$ be the random variable which indicates the number of such edges. By the linearity of expectation, we have $E[X]=\sum_{e\in{E}}[X_e]=\binom{n}{2}\left(1-\frac{m}{\binom{n}{2}}\right)^{k}$<=$\frac{n^2}{2}\left(1-\frac{2m}{n^2}\right)^k$<=$\frac{n^2}{2}e^\frac{-2km}{n^2}$, given that $k>\frac{n^2\ln{n}}{m}$, the above inequality$\frac{n^2}{2}e^\frac{-2m}{n^2}$<$\frac{n^2}{2}e^{-2\ln{n}}=\frac{1}{2}$. So we have a $X$ such that $X<\frac{1}{2}$, $i.e. X=0$, which means it's possible to color all of the edges of $K_{n}$ in this way.