Double Aztec rectangles

We investigate the connection between lozenge tilings and domino tilings by introducing a new family of regions obtained by attaching two different Aztec rectangles. We prove a simple product formula for the generating functions of the tilings of the new regions, which involves the statistics as in the Aztec diamond theorem (Elkies et al. (1992) [2], [3]). Moreover, we consider the connection between the generating function and MacMahon's q-enumeration of plane partitions fitting in a given box     

Domino tilings of the expanded Aztec diamond

The expanded Aztec diamond is a generalized version of the Aztec diamond, with an arbitrary number of long columns and long rows in the middle. In this paper, we count the number of domino tilings of the expanded Aztec diamond. The exact number of domino tilings is given by recurrence relations of state matrices by virtue of the state matrix recursion algorithm, recently developed by the author to solve various two-dimensional regular lattice model enumeration problems.     

Alternating-Sign Matrices and Domino Tilings (Part I)

We introduce a family of planar regions, called Aztec diamonds, and study tilings of these regions by dominoes. Our main result is that the Aztec diamond of order n has exactly 2 ^n(n+1)/2 domino tilings. In this, the first half of a two-part paper, we give two proofs of this formula. The first proof exploits a connection between domino tilings and the alternating-sign matrices of Mills, Robbins, and Rumsey. In particular, a domino tiling of an Aztec diamond corresponds to a compatible pair of alternating-sign matrices. The second proof of our formula uses monotone triangles, which constitute another form taken by alternating-sign matrices; by assigning each monotone triangle a suitable weight, we can count domino tilings of an Aztec diamond.     

Enumeration of domino tilings of an Aztec rectangle with boundary defects

In this paper we enumerate domino tilings of an Aztec rectangle with arbitrary defects of size one on all boundary sides. This result extends previous work by different authors: Mills–Robbins–Rumsey and Elkies–Kuperberg–Larsen–Propp. We use the method of graphical condensation developed by Kuo and generalized by Ciucu, to prove our results; a common generalization of both Kuo's and Ciucu's result is also presented here.     

Domino Tiling Congruence Modulo 4

The number of domino tilings of a region with reflective symmetry across a line is combinatorially shown to depend on the number of domino tilings of particular subregions, modulo 4. This expands upon previous congruency results for domino tilings, modulo 2, and leads to a variety of corollaries, including that the number of domino tilings of a k × 2k rectangle is congruent to 1 mod 4.     

Alternating-Sign Matrices and Domino Tilings (Part II)

We continue the study of the family of planar regions dubbed Aztec diamonds in our earlier article and study the ways in which these regions can be tiled by dominoes. Two more proofs of the main formula are given. The first uses the representation theory of GL(n). The second is more combinatorial and produces a generating function that gives not only the number of domino tilings of the Aztec diamond of order n but also information about the orientation of the dominoes (vertical versus horizontal) and the accessibility of one tiling from another by means of local modifications. Lastly, we explore a connection between the combinatorial objects studied in this paper and the square-ice model studied by Lieb.     

Domino tilings of Aztec diamonds and squares

An Aztec diamond of rank n is a rhombus of side length n on the square grid. We give several new combinatorial proofs of known theorems about the numbers of domino tilings of diamonds and squares. We also prove generalizations of these theorems for the generating polynomials of some statistics of tilings. Some results here are new. For example, we describe how to calculate the rank of a tiling using special weights of edges on the square grid. Bibliography: 17 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 360, 2008, pp. 180–230.     

Laurent biorthogonal polynomials, q-Narayana polynomials and domino tilings of the Aztec diamonds

A Toeplitz determinant whose entries are described by a q-analogue of the Narayana polynomials is evaluated by means of Laurent biorthogonal polynomials which allow of a combinatorial interpretation in terms of Schröder paths. As an application, a new proof is given to the Aztec diamond theorem by Elkies, Kuperberg, Larsen and Propp concerning domino tilings of the Aztec diamonds. The proof is based on the correspondence with non-intersecting Schröder paths developed by Johansson.     

Computing a pyramid partition generating function with dimer shuffling

We verify a recent conjecture of Kenyon/Szendr?i by computing the generating function for pyramid partitions. Pyramid partitions are closely related to Aztec Diamonds; their generating function turns out to be the partition function for the Donaldson-Thomas theory of a non-commutative resolution of the conifold singularity {x₁x₂−x₃x₄=0}⊂C⁴. The proof does not require algebraic geometry; it uses a modified version of the domino shuffling algorithm of Elkies, Kuperberg, Larsen and Propp [Noam Elkies, Greg Kuperberg, Michael Larsen, James Propp, Alternating sign matrices and domino tilings. II, J. Algebraic Combin. 1 (3) (1992) 219-234].     

State matrix recursion method and monomer–dimer problem

The exact enumeration of pure dimer coverings on the square lattice was obtained by Kasteleyn, Temperley and Fisher in 1961. In this paper, we consider the monomer–dimer covering problem (allowing multiple monomers) which is an outstanding unsolved problem in lattice statistics. We have developed the state matrix recursion method that allows us to compute the number of monomer–dimer coverings and to know the partition function with monomer and dimer activities. This method proceeds with a recurrence relation of so-called state matrices of large size. The enumeration problem of pure dimer coverings and dimer coverings with single boundary monomer is revisited in partition function forms. We also provide the number of dimer coverings with multiple vacant sites. The related Hosoya index and the asymptotic behavior of its growth rate are considered. Lastly, we apply this method to the enumeration study of domino tilings of Aztec diamonds and more generalized regions, so-called Aztec octagons and multi-deficient Aztec octagons.     

Double Aztec diamonds and the tacnode process

Discrete and continuous non-intersecting random processes have given rise to critical “infinite-dimensional diffusions”, like the Airy process, the Pearcey process and variations thereof. It has been known that domino tilings of very large Aztec diamonds lead macroscopically to a disordered region within an inscribed ellipse (arctic circle in the homogeneous case), and a regular brick-like region outside the ellipse. The fluctuations near the ellipse, appropriately magnified and away from the boundary of the Aztec diamond, form an Airy process, run with time tangential to the boundary.     

Asymptotics of multivariate sequences, part III: Quadratic points

We consider a number of combinatorial problems in which rational generating functions may be obtained, whose denominators have factors with certain singularities. Specifically, there exist points near which one of the factors is asymptotic to a nondegenerate quadratic. We compute the asymptotics of the coefficients of such a generating function. The computation requires some topological deformations as well as Fourier–Laplace transforms of generalized functions. We apply the results of the theory to specific combinatorial problems, such as Aztec diamond tilings, cube groves, and multi-set permutations.     

An arctic circle theorem for Groves

In earlier work, Jockusch, Propp, and Shor proved a theorem describing the limiting shape of the boundary between the uniformly tiled corners of a random tiling of an Aztec diamond and the more unpredictable ‘temperate zone’ in the interior of the region. The so-called arctic circle theorem made precise a phenomenon observed in random tilings of large Aztec diamonds.Here we examine a related combinatorial model called groves. Created by Carroll and Speyer as combinatorial interpretations for Laurent polynomials given by the cube recurrence, groves have observable frozen regions which we describe precisely via asymptotic analysis of a generating function. Our approach also provides another way to prove the arctic circle theorem for Aztec diamonds.     

A New Simple Proof of the Aztec Diamond Theorem

The Aztec diamond of order n is the union of lattice squares in the plane intersecting the square \(|x|+|y|<n\). The Aztec diamond theorem states that the number of domino tilings of this shape is \(2^{n(n+1)/2}\). It was first proved by Elkies et al. (J. Algebraic Comb. 1(2):111–132, 1992). We give a new simple proof of this theorem.     

Non-intersecting paths, random tilings and random matrices

 We investigate certain measures induced by families of non-intersecting paths in domino tilings of the Aztec diamond, rhombus tilings of an abc-hexagon, a dimer model on a cylindrical brick lattice and a growth model. The measures obtained, e.g. the Krawtchouk and Hahn ensembles, have the same structure as the eigenvalue measures in random matrix theory like GUE, which can in fact can be obtained from non-intersecting Brownian motions. The derivations of the measures are based on the Karlin-McGregor or Lindstr?m-Gessel-Viennot method. We use the measures to show some asymptotic results for the models. Received: 1 December 2000 / Revised version: 20 May 2001 / Published online: 17 May 2002     

Singular Polynomials of Generalized Kasteleyn Matrices

Kasteleyn counted the number of domino tilings of a rectangle by considering a mutation of the adjacency matrix: a Kasteleyn matrix K. In this paper we present a generalization of Kasteleyn matrices and a combinatorial interpretation for the coefficients of the characteristic polynomial of KK* (which we call the singular polynomial), where K is a generalized Kasteleyn matrix for a planar bipartite graph. We also present a q-version of these ideas and a few results concerning tilings of special regions such as rectangles.     

Plane overpartitions and cylindric partitions

Generating functions for plane overpartitions are obtained using various methods such as nonintersecting paths, RSK type algorithms and symmetric functions. We extend some of the generating functions to cylindric partitions. Also, we show that plane overpartitions correspond to certain domino tilings and we give some basic properties of this correspondence.     

A variational principle for domino tilings

We formulate and prove a variational principle (in the sense of thermodynamics) for random domino tilings, or equivalently for the dimer model on a square grid. This principle states that a typical tiling of an arbitrary finite region can be described by a function that maximizes an entropy integral. We associate an entropy to every sort of local behavior domino tilings can exhibit, and prove that almost all tilings lie within (for an appropriate metric) of the unique entropy-maximizing solution. This gives a solution to the dimer problem with fully general boundary conditions, thereby resolving an issue first raised by Kasteleyn. Our methods also apply to dimer models on other grids and their associated tiling models, such as tilings of the plane by three orientations of unit lozenges.

     

Coupling functions for domino tilings of Aztec diamonds

The inverse Kasteleyn matrix of a bipartite graph holds much information about the perfect matchings of the system such as local statistics which can be used to compute local and global asymptotics. In this paper, we consider three different weightings of domino tilings of the Aztec diamond and show using recurrence relations, that we can compute the inverse Kasteleyn matrix. These weights are the one-periodic weighting where the horizontal edges have one weight and the vertical edges have another weight, the q^vol$q^{\mathrm{vol}}$ weighting which corresponds to multiplying the product of tile weights by q if we add a ‘box’ to the height function and the two-periodic weighting which exhibits a flat region with defects in the center.     

An optimal algorithm to generate tilings

We produce an algorithm that is optimal with respect to both space and execution time to generate all the lozenge (or domino) tilings of a hole-free, general-shape domain given as input.We first recall some useful results, namely the distributive lattice structure of the space of tilings and Thurston's algorithm for constructing a particular tiling. We then describe our algorithm and study its complexity.