Abstract
The authors study rectangular dissections of an n x n lattice region into rectangles of area n, where n = 2 super( k) for an even integer k. They 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 super( u), (s + 1)2 super( u))x(t2 super( v), (t+1)2 super( v)); where s; t; u and v are nonnegative integers. They consider a weighted version of these Markov chains where, given a parameter lambda > 0; they would like to generate each rectangular dissection (or dyadic tiling) sigma with probability proportional to lambda super( | sigma |) where | sigma | is the total edge length. The authors show there is a phase transition in the dyadic setting: when lambda < 1; the edge-ipping chain mixes in time O(n super( 2) log n), and when lambda > 1; the mixing time is exp( Omega (n super( 2))).