Phase Transitions in Random Dyadic Tilings and Rectangular

We study rectangular dissections of an n × n lattice region into rectangles of area n, where n = 2k for an even integer k. We show that there is a natural edge-flipping Markov chain that connects the state space. A similar edge-flipping chain is also known to connect the state space when restricted to dyadic tilings, where each rectangle is required to have the form R = [s2u, (s + 1)2u]×[t2v, (t+1)2v], where s, t, u and v are nonnegative integers. The mixing time of these chains is open. We consider a weighted version of these Markov chains where, given a parameter λ> 0, we would like to generate each rectangular dissection (or dyadic tiling) σ with probability proportional to λ|σ|, where |σ | is the total edge length. We show there is a phase transition in the dyadic setting: when λ < 1, the edge-flipping chain mixes in time O(n2 log n), and when λ> 1, the mixing time is exp(Ω(n2)). Simulations suggest that the chain converges quickly when λ = 1, but this case remains open. The behavior for general rectangular dissections is more subtle, and even establishing ergodicity of the chain requires a careful inductive argument. As in the dyadic case, we show that the edge-flipping Markov chain for rectangular dissections requires exponential time when λ> 1. Surprisingly, the chain also requires exponential time when λ < 1, which we show using a different argument. Simulations suggest that the chain converges quickly at the isolated point λ = 1