I was reading Noga Alon's Probabilistic Methods and came across this question which I am unable to prove.
There is a two-coloring of $K_n$ where $K_n$ is a complete graph of $n$ vertices with at most $${{n}\choose{\alpha}}*2^{1-{{\alpha}\choose{2}}}$$ monochromatic $K_{\alpha}$.
Presumably $\alpha$ is a positive integer $\le n$, and this is talking about an edge colouring, not a vertex colouring. Since this is about Probabilistic Methods, colour each edge randomly 0 or 1, independently and with equal probabilities. For any given $K_\alpha$ subgraph, the probability that this is monochromatic, i.e. that all $\alpha \choose 2$ edges are coloured the same, is $2^{1 - {\alpha \choose 2}}$. There are $n \choose \alpha$ such subgraphs, so the expected number of monochromatic $K_\alpha$ subgraphs is then ${n \choose \alpha} 2^{1-{\alpha \choose 2}}$. Thus it must be possible for the number of monochromatic $K_\alpha$ subgraphs to be at most this number.