Using the Lovasz Local Lemma to Avoid Monochromatic Subgraphs in Kn

Let X_i be the event that the i-th K_k subgraph is monochromatic. Let A_i be the set of all K_k subgraphs that share an edge with the i-th K_k subgraph. Note that each K_k subgraph is included in exactly 2^(k choose 2) sets A_i.

We want to show that the probability of any X_i occurring is at most 1/2, so that we can apply the Lovasz Local Lemma. To do this, we need to find an appropriate dependency graph and show that the maximum degree is less than 1/2.

Let the vertices of the dependency graph be the events X_i. Draw an edge between X_i and X_j if and only if the corresponding K_k subgraphs share an edge. Note that the dependency graph is symmetric and has 2^(k choose 2) nodes.

We claim that each node in the dependency graph has at most (k-1)2^(k-1) neighbors. To see this, note that any K_k subgraph shares edges with exactly k-1 other K_k subgraphs, and each of these K_k subgraphs is included in exactly 2^(k-1) sets A_i. Thus, each node has degree at most (k-1)2^(k-1).

Now, we need to check that the Lovasz condition holds. That is, we need to show that

4k^2 / (k-n)^2 < 1/[(k-1)2^(k-1)]

Simplifying, we get

2^(2k) < k^(2n) / (k-n)^2

Taking logarithms, we get

2k log 2 < 2n log k - 2 log(k-n)

Since k > n, we can bound the right-hand side by

2n log k - 2 log n = 2 log k^n - 2 log n < 2 log k^2

Thus, it suffices to show that

2k log 2 < 4 log k

which is true for k >= 2.

Therefore, by the Lovasz Local Lemma, there exists a valid 2-coloring of the edges of Kn that avoids monochromatic K_k subgraphs.