The phase transition for dyadic tilings

Abstract:

A dyadic tile of order $n$ is any rectangle obtained from the unit square by $n$ successive bisections by horizontal or vertical cuts. Let each dyadic tile of order $n$ be available with probability $p$, independent of the others. We prove that for $p$ sufficiently close to $1$, there exists a set of pairwise disjoint available tiles whose union is the unit square, with probability tending to $1$ as $n\to \infty$, as conjectured by Joel Spencer in 1999. In particular, we prove that if $p=7/8$, such a tiling exists with probability at least $1-(3/4)^n$. The proof involves a surprisingly delicate counting argument for sets of unavailable tiles that prevent tiling.