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.
This problem is a classical problem in probabilistic graph theory due to Erdos and can be found in pretty much any introductory course on probabilistic graph theory.
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}$)