Spring 2016

Equitable Rectangular Dissections of a Square

Friday, Feb. 26, 2016 11:40 am12:25 pm

Add to Calendar


Calvin Lab

We study equitable rectangular dissections of an n x n lattice region into n rectangles of  area n, where n=2^k for an even integer k.  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 has edges that are dyadic intervals.  We consider a weighted version of these Markov chains, where the weight of each rectangular dissection (or dyadic tiling) is exponential in the total edge length.  We show there is a phase transition in the dyadic setting where the mixing time is unknown only at the critical point.  The behavior for general rectangular dissections is more subtle, and the chain requires exponential time above and below a unique critical point, but for two different reasons, and remains open at the critical point.