# The Maximimum Monochromatic k-Cliques for Complete Graph

Show: For a complete graph $$K_{n}$$, there is a coloring of the edges with $$2$$ colors, such that the number of monochromatic $$k$$-Cliques is a maximum of $$\binom{n}{k}2^{1-\binom{k}{2}}$$.

I do not know where to begin on this exercise. As a hint, our professor gave us the following pre-exercise, which I have been able to solve:

Let $$n \in \mathbb N$$, and $$\mathcal{K}$$ be the set of permutations possible for a set $$\{1,...,n\}$$. Let $$\sigma \in \mathcal{K},$$ such that $$\sigma: [n] \to [n]$$ is a randomly selected permutation. Find the probability space, define random variable $$X$$ as the number of fixed points and find $$\mathbb E[X]$$.

How do the two questions fit together? I am lost.

• I do not know about those random graph and just google about that. And I found people.cs.pitt.edu/~kirk/cs3150spring06/HW6_B.pdf Problem 6.2A has a similar question - which the number there is the expected number of monochromatic clique. But I do not quite follow how is that related to "at most".
– BGM
Nov 20, 2018 at 16:17

Denote by $$I_{x_1,...,x_k}$$ the indicator function of the k-clique of vertices $${x_1,...,x_k}$$(for a random coloring of $$K_n$$). Thus $$I_{x_1,...,x_k}$$ is 1 if $${x_1,...,x_k}$$ is monochromatic or 0 else. Then the total number of monochromatic k-Cliques is equal to $$\sum_{x_1,...,x_k}I_{x_1,...,x_k}$$ where the sum is taken over all $${n\choose k}$$ groups of k-vertices in the graph. The expected number of monochromatic k-Cliques is then equal to $${n\choose k}P({x_1,...,x_k}$$ is monochromatic $$) = {n\choose k}2^{1-{k\choose 2}}$$, by linearity of expectation and also by $$E(I_A)=P(A)$$, for any event set A, so you can find at least one graph with $${n\choose k}2^{1-{k\choose 2}}$$ monochromatic k-Cliques.
For completion, note that $$P({x_1,...,x_k}$$ is monochromatic $$) = 2^{1-{k\choose 2}}$$ because $${x_1,...,x_k}$$ is monochromatic if it is either red or blue(whence the factor of 1 in its exponent and the probability that each of its $$k \choose 2$$ edges is red is exactly $$\frac{1}{2}$$)