Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 124 / 2 / iv

Put $C=A\cup B$. ThenGenerate a uniformly random complete $(m-1)$-partite graph by independently assigning one of $m-1$ colours to each vertex and joining vertices of different colours. Such a graph contains the clique on $W$ exactly when the colouring is injective on $W$.

Construct $C^{\ast }$ by adjoining one forced set at a time. There are at most $n^l$ possible sets of size at most $l$. If $W$ is newly forced by $W_1,\dots ,W_r$, then, conditional on $W$ being rainbow, the events that each $W_i$ is not rainbow depend on disjoint petals $W_i\setminus W$. Since $l^2\le m$, each has conditional probability at most $1/2$. Their simultaneous probability is therefore at most $2^{-r}$. A union bound over the at most $n^l$ closure steps givesThis is exactly the claimed proportion of complete $(m-1)$-partite graphs.