ABSTRACT:
This talk concerns lattice triangulations, i.e., triangulations of the 
integer points in a polygon in the plane whose vertices are also integer 
points.  Lattice triangulations have been studied extensively both as 
geometric objects in their own right and by virtue of applications in 
algebraic geometry.  Our focus is on random triangulations in which a 
triangulation $T$ has weight $\lambda^{|T|}$, where $\lambda$ is a 
positive real parameter and $|T|$ is the total length of the edges in 
$T$.  Empirically, this model exhibits a "phase transition" at 
$\lambda=1$ (corresponding to the uniform distribution): for 
$\lambda<1$ distant edges behave essentially independently, while for 
$\lambda>1$ very large regions of aligned edges appear.  We substantiate 
this picture as follows.  For $\lambda<1$ sufficiently small, we show 
that correlations between edges decay exponentially with distance 
(suitably defined), and also that the Glauber dynamics (a local Markov 
chain based on flipping edges) is rapidly mixing (in time polynomial in 
the number of edges).  This dynamics has been proposed by several authors 
as an algorithm for generating random triangulations.  By contrast, for 
$\lambda>1$ we show that the mixing time is exponential.  These are 
apparently the first rigorous quantitative results on the structure and 
dynamics of random lattice triangulations. 
(Joint work with Pietro Caputo, Fabio Martinelli and Alexandre Stauffer.)

BIO:
Alistair Sinclair is a professor at the Computer Science division at 
UC Berkeley and Associate Director of the Simons Institute for Theory of Computing. 
His research interests include the design and analysis of randomized algorithms, 
computational applications of stochastic processes and nonlinear dynamical systems, 
Monte Carlo methods in Statistical Physics, and combinatorial optimization. With  
Mark Jerrum, Sinclair investigated the mixing behavior of Markov chains to construct 
approximation algorithms for counting problems such as the computing the permanent, 
with applications in diverse fields such as matching algorithms, geometric algorithms, 
mathematical programming, statistics, physics-inspired applications, and dynamical 
systems. This work has been highly influential in theoretical computer science and 
was recognized with the Gödel Prize in 1996; a further breakthrough (also joint with 
Eric Vigoda) led to Sinclair and his co-authors receiving the Fulkerson Prize in 2006.