Campuses:

Phase Transitions in Random Dyadic Tilings and Rectangular Dissections

Thursday, March 19, 2015 - 11:20am - 12:00pm
Klaus 1116
Sarah Miracle (Georgia Institute of Technology)
We study rectangular dissections of an n x n lattice region into rectangles of area n, where n = 2^k 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 = [s2^u,(s+1)2^u] x [t2^v,(t+1)2^v], 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 \lambda > 0, we would like to generate each rectangular dissection (or dyadic tiling) r with probability proportional to \lambda^r, where r is the total edge length. We show there is a phase transition in the dyadic setting: when \lambda 1, the mixing time is exp(\Omega(n^2)). Simulations suggest that the chain converges quickly when \lambda = 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 \lambda > 1. Surprisingly, the chain also requires exponential time when \lambda