DIMACS Discrete Mathematics Seminar

Title:

Generating random surfaces, tilings and eulerian orientations

Speaker:

Dana Randall

Institute for Advanced Study and DIMACS

Place:

Seminar Room 431, CoRE Building,

Busch Campus, Rutgers University.

Time:

4:30 PM

Tuesday, February 14, 1995

Abstract:

We consider the problems of efficiently generating random dimer configurations (or tilings) and random Eulerian orientations on a finite region of a two-dimensional lattice. Thurston, Conway and Lagarias showed that given arbitrary boundary conditions on a region of the lattice, the set of dimer coverings map bijectively to a set of piecewise linear surfaces with a fixed boundary. Similarly, the set of Eulerian orientations, or configurations of the ice model in statistical mechanics, are known to correspond bijectively with ``solid-on-solid'' surfaces where the difference in height between any two neighboring points is exactly one. We define a natural Markov chain for each family of surfaces and show that each will converge quickly to the uniform distribution over configurations. The proofs of the convergence rates rely on simple coupling arguments. (This is joint work with M. Luby and A. Sinclair.)

Document last modified on February 9, 1995