= Solution
Put $C=A\cup B$. Then
$$
\delta_\cup(\langle A\rangle,\langle B\rangle)
=\langle C^*\rangle-\langle C\rangle.
$$
Generate 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^*$ 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,\ldots,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\leq 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 gives
$$
\mathbb P\!\left(
G\in\langle C^*\rangle-\langle C\rangle
\right)
\leq n^l2^{-r}.
$$
This is exactly the claimed proportion of complete $(m-1)$-partite graphs.
Back to article page
