Complete-bipartite Ramsey completion lemma
= Complete-bipartite Ramsey completion lemma
The completion form of dependent random choice starts with $t=k-O(\log k)$ vertices having at least $c2^{-t}n$ common neighbours in one colour. Reapplying common-neighbourhood sampling inside the remaining polynomial-size set either completes these vertices to a monochromatic $K_{k,k}$ in that colour or produces a $K_{k,k}$ in the other colour. It yields
$$
R(K_{k,k})=O((\log k)2^k).
$$