Show that if C(n,k) * 2^{1 - C(k,2)} < 1 then some two-colouring of the edges of the complete graph on n vertices has no monochromatic clique on k vertices, and check that n = 32 works for k = 10.

Show that if C(n,k) * 2^{1 - C(k,2)} < 1 then some two-colouring of the edges of the complete graph on n vertices has no monochromatic clique on k vertices, and check that n = 32 works for k = 10.

Approach: Colour each edge independently, bound the probability that one fixed k-set comes out monochromatic, then apply a union bound over all k-sets to show the failure probability stays below one.

The union bound gives P(some monochromatic k-clique) <= C(n,k) 2^{1 - C(k,2)}, so whenever that quantity is below 1 a random colouring has positive probability of avoiding every monochromatic clique, which proves a good colouring exists. Take a random colouring of the C(n,2) edges, red or blue independently with probability 1/2. A fixed set of k vertices spans C(k,2) internal edges, all one colour with probability 2 * 2^{-C(k,2)}, and summing over the C(n,k) sets gives the bound. For k = 10 and n = 32, C(32,10) = 64512240 and 2^{-44} = 5.68 * 10^{-14}, whose product is 3.7 * 10^{-6} < 1, so the Ramsey number satisfies R(10,10) > 32, which is 2^{k/2} at k = 10. The probabilistic method gives no construction, and no explicit colouring is known that matches this bound.

Follow-up: How much does the Lovasz local lemma improve this bound?

Key concepts: union bound, probabilistic method, ramsey number, random colouring.