= 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>, so
$$
\mathbb P(A\text{ is monochromatic})=2\cdot2^{-6}=2^{-5}.
$$
Let $I_A$ be the <indicator random variable> for this event and let $Z=\sum_A I_A$ count the <monochromatic> copies. <Linearity of expectation> gives
$$
\mathbb EZ=\sum_A\mathbb E I_A=\binom n4\,2^{-5}.
$$
The <indicator random variables> for overlapping copies need not be <independent>. Averaging over all <edge colorings> ensures that at least one has $Z\leq\mathbb EZ$. Thus the <probabilistic method> proves
$$
\boxed{\text{Some two-colour edge coloring has }Z\leq\frac1{32}\binom n4.}
$$
For $0\leq 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.
Back to article page
