Tiling problems have a long tradition in combinatorics and in statistical mechanics. One of the central problems is understanding the statistical structure of the patterns obtained when randomly tiling a large domain. As noticed by N. Elkies and J. Propp a decade ago, random tilings of a large planar domain may exhibit phase segregation; the density of tiles has a smooth (non-constant) variation in some regions of the domain in coexistence with a frozen region where the density of tiles is constant. In the corresponding surface picture the frozen region corresponds to a facet of constant slope while in the complement one has a rounded surface.
In a very influential paper of 1986, M. Kardar, G. Parisi, and Y.C. Zhang introduced growth processes of random deposition type without surface diffusion. A particular much studied one-dimensional model is the corner growth model with discrete time updating, which is isomorphic to the interface in the dimer tiling of the Aztec diamond. The stochastic growth of the line separating the frozen from the non-frozen region is induced by the random shuffling algorithm, which from a tiling of a domain of linear size N generates a corresponding one of a domain of linear size N+1 with the correct statistical weight.
During the last decade there has been enormous progress in elucidating the picture. For example, it was proven that for the random tiling of a domain in the triangular lattice by rhombi (dimer models on the hexagonal lattice) the limit shapes are algebraic curves (R. Kenyon, A. Okounkov). In the non-frozen region the fluctuations in such models have the statistics of a massless Gaussian free field (R. Kenyon). With the exception of singular points the borderline separating the frozen and non-frozen regions is governed by the Airy process (M. Prähofer, H. Spohn, A. Okounkov, N. Reshetikhin). At singular points the fluctuations are described by the Pearcy process and similar determinantal processes (A. Okounkov, N. Reshetikhin). As noted by K. Johansson these stochastic processes are closely related to the asymptotics of discrete orthogonal polynomials. He also first understood the deep connection between tilings of particular domains and one-dimensional KPZ growth. This discovery triggered an explosion of activities as a result of which the interconnections were elucidated in considerable detail, in particular the central role of extended determinantal processes, of Dyson's Brownian motion, and of low rank perturbations of random matrices. There are good reasons to expect that the structure of fluctuations is universal and holds for a much wider class of models.
Tiling problems are also closely related to the theory of random partitions and representation theory. This is particularly transparent for tilings of domains on a triangular lattice by rhombi, developed in the contributions of A. Borodin, A. Okounkov, and G. Olshanski.
