Past exam of the computer science course of the University of Oxford / 2015 / Probability and computing / 3 / d / Solution

Colour each edge of the complete graph $K_n$ independently red or blue, with probability $1/2$ for each colour. Every four-element subset $A$ of vertices determines exactly one copy of $K_4$, containing six edges. These six edges are all red with probability $2^{-6}$ and all blue with probability $2^{-6}$. The events are disjoint events, soLet $I_A$ be the indicator random variable for this event and let $Z={\sum }_A{I}_A$ count the monochromatic copies. Linearity of expectation givesThe indicator random variables for overlapping copies need not be independent. Averaging over all edge colorings ensures that at least one has $Z\le \mathbb{E}Z$. Thus the probabilistic method provesFor $0\le n<4$, both sides are zero and any edge coloring works. Copies are counted by their four-vertex subsets, rather than by their $4!$ possible labellings.