Exercise 2.7.5 of the probabilistic method

Question

Let $H$ be a graph, and let $n > |V(H)|$ be an integer.Suppose there is a graph on $n$ vertices and $t$ edges containing no copy of $H$, and suppose that $tk>n^2\log_en$. Show that there is a coloring of the edges of the complete graph on $n$ vertices by $k$ colors with no monochromatic copy of $H$.

Answer 1

About $3$ years ago, I downloaded a solution manual from https://radimentary.files.wordpress.com/2017/03/solutions_compilation.pdf, but this link no longer works. The author was Xiaoyu He. Maybe you can find it.

Anyway, here's a sketch of his solution to this problem.

Let $G$ be the graph with $n$ vertices and $t$ edges containing no copy of $H$. Consider $K_n$ as a labeled graph, make $k$ independent random relabelings of $G$ and color them with colors $1$ through $k$. Viewing the labeled copies of $G$ as subgraphs, of the labeled $K_n$, color each edge of $K_n$ with the color of the first copy of $G$ that it shows up in. Then $K_n$ contains no monochromatic $H$, because none of the $G$'s does.

To complete the proof, it must be shown that there is a non-zero probability that the $G$'s cover all the edges of $K_n$ so that the coloring described above can actually be carried out. A straightforward calculation shows that the expected number of uncolored edges is $<1$, so there must be a complete coloring.

Answer 2

Below is my solution when I met the problem in my homework before.

When $|V(H)| \leq 1$, it's not so meaningful, so we only need to care about the cases when $|V(H)| \geq 2$, and then $n \geq |V(H)| + 1 \geq 3$.

Let $G$ be such a graph on $n$ vertices and $t$ edges containing no copy of $H$. As we supposed that $tk > n^2 \log_e n > \binom{n}{2}$, maybe we can find some way to paste $k$ monochromatic copies of $G$ onto $K_n$ (some edges may be colored more than once, among the colors they are colored in, choosing any one can make the conclusion hold), where each edge is colored and no copy of $H$ exists in the graph.

So, let's randomly paste $k$ monochromatic copies of $G$ onto $K_n$, mathematically speaking, let $V(G) = [n]$ and $V(K_n) = \{v_i\}_{i \in [n]}$, for each color, we randomly pick a permutation of $[n]$, $\sigma: [n] \rightarrow \sigma([n])$, then for all $(i, j) \in E(V(G))$, we color the edge $(v_{\sigma(i)}, v_{\sigma(j)})$ in $K_n$ in that color (if it's already colored, then we simply recolor it). Let $X$ be the random variable of edges not colored, which is naturally the summation of $X_e$, the indicator random variable of $e$ being not colored, for all $e \in E(K_n)$, thus clearly, $$E[X_e] = (1 - \frac{2t(n-2)!}{n!})^k = (1 - \frac{2t}{n(n-1)})^k.$$ Therefore, \begin{align*} E[X] = & \sum_e E[X_e] \\ = & \sum_e (1 - \frac{2t}{n(n-1)})^k \\ = & \binom{n}{2} (1 - \frac{2t}{n(n-1)})^k \\ \leq & \frac{n(n-1)}{2} e^{-\frac{2tk}{n(n-1)}} \\ < & \frac{n^2}{2} e^{-2\log_e n} \\ = & \frac{1}{2}, \end{align*} as $X$ is an integer, there is a coloring by pasting $k$ monochromatic copies of $G$ with $X = 0$, i.e., each edge is colored, completing the proof.