Krdytkyu

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 ${nchoose k}$ groups of k-vertices in the graph. The expected number of monochromatic k-Cliques is then equal to ${nchoose k}P({x_1,...,x_k}$ is monochromatic $) = {nchoose k}2^{1-{kchoose 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 ${nchoose k}2^{1-{kchoose 2}}$ monochromatic k-Cliques.

For completion, note that $P({x_1,...,x_k}$ is monochromatic $) = 2^{1-{kchoose 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}$)