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 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.     

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.     

A note on the structure of spaces of domino tilings

We study spaces of tilings, formed by tilings which are on a geodesic between two fixed tilings of the same domain (the distance is defined using local flips). We prove that each space of tilings is homeomorphic to an interval of tilings of a domain when flips are classically directed by height functions.     

The energy and spanning trees of the Aztec diamonds

The Aztec diamond was extensively studied in both graph theory and statistical physics. Knuth obtained a formula of the number of spanning trees of the Aztec diamond with the constrained boundary condition, which solved a conjecture posed by Stanley in 1994. In this paper, We give the formulae of the energy and the number of spanning trees of the Aztec diamond with the toroidal boundary condition.     

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 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     

A visual proof of a result of Knuth on spanning trees of Aztec diamonds in the case of odd order

The even Aztec diamond AD_n is known to have precisely four times more spanning trees than the odd Aztec diamond OD_n—this was conjectured by Stanley and first proved by Knuth. We present a short combinatorial proof of this fact in the case of odd n. Our proof works also for the more general case of odd-by-odd Aztec rectangles.     

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.     

Symmetry classes of spanning trees of Aztec diamonds and perfect matchings of odd squares with a unit hole

We say that two graphs are similar if their adjacency matrices are similar matrices. We show that the square grid G _n of order n is similar to the disjoint union of two copies of the quartered Aztec diamond QAD _n−1 of order n−1 with the path P _n ⁽²⁾ on n vertices having edge weights equal to 2. Our proof is based on an explicit change of basis in the vector space on which the adjacency matrix acts. The arguments verifying that this change of basis works are combinatorial. It follows in particular that the characteristic polynomials of the above graphs satisfy the equality P(G _n )=P(P _n ⁽²⁾)[P(QAD _n−1)]². On the one hand, this provides a combinatorial explanation for the “squarishness” of the characteristic polynomial of the square grid—i.e., that it is a perfect square, up to a factor of relatively small degree. On the other hand, as formulas for the characteristic polynomials of the path and the square grid are well known, our equality determines the characteristic polynomial of the quartered Aztec diamond. In turn, the latter allows computing the number of spanning trees of quartered Aztec diamonds. We present and analyze three more families of graphs that share the above described “linear squarishness” property of square grids: odd Aztec diamonds, mixed Aztec diamonds, and Aztec pillowcases—graphs obtained from two copies of an Aztec diamond by identifying the corresponding vertices on their convex hulls. We apply the above results to enumerate all the symmetry classes of spanning trees of the even Aztec diamonds, and all the symmetry classes not involving rotations of the spanning trees of odd and mixed Aztec diamonds. We also enumerate all but the base case of the symmetry classes of perfect matchings of odd square grids with the central vertex removed. In addition, we obtain a product formula for the number of spanning trees of Aztec pillowcases. Research supported in part by NSF grant DMS-0500616.     

Aztec Diamonds, Checkerboard Graphs, and Spanning Trees

This note derives the characteristic polynomial of a graph that represents nonjump moves in a generalized game of checkers. The number of spanning trees is also determined.     

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.     

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.

     

Doubly periodic lozenge tilings of a hexagon and matrix valued orthogonal polynomials

We analyze a random lozenge tiling model of a large regular hexagon, whose underlying weight structure is periodic of period 2 in both the horizontal and vertical directions. This is a determinantal point process whose correlation kernel is expressed in terms of non‐Hermitian matrix valued orthogonal polynomials (OPs). This model belongs to a class of models for which the existing techniques for studying asymptotics cannot be applied. The novel part of our method consists of establishing a connection between matrix valued and scalar valued OPs. This allows to simplify the double contour formula for the kernel obtained by Duits and Kuijlaars by reducing the size of a Riemann–Hilbert problem. The proof relies on the fact that the matrix valued weight possesses eigenvalues that live on an underlying Riemann surface of genus 0. We consider this connection of independent interest; it is natural to expect that similar ideas can be used for other matrix valued OPs, as long as the corresponding Riemann surface is of genus 0. The rest of the method consists of two parts, and mainly follows the lines of a previous work of Charlier, Duits, Kuijlaars and Lenells. First, we perform a Deift–Zhou steepest descent analysis to obtain asymptotics for the scalar valued OPs. The main difficulty is the study of an equilibrium problem in the complex plane. Second, the asymptotics for the OPs are substituted in the double contour integral and the latter is analyzed using the saddle point method. Our main results are the limiting densities of the lozenges in the disordered flower‐shaped region. However, we stress that the method allows in principle to rigorously compute other meaningful probabilistic quantities in the model.     

A shuffling theorem for reflectively symmetric tilings

The author and Rohatgi recently proved a ‘shuffling theorem’ for doubly-dented hexagons. In particular, they showed that shuffling removed unit triangles along a horizontal axis in a hexagon changes the tiling number by only a simple multiplicative factor. In this paper, we consider a similar phenomenon for a symmetry class of tilings, namely, the reflectively symmetric tilings. We also prove several shuffling theorems for halved hexagons.     

Lozenge tilings of hexagons with arbitrary dents

Eisenkölbl gave a formula for the number of lozenge tilings of a hexagon on the triangular lattice with three unit triangles removed from along alternating sides. In earlier work, the first author extended this to the situation when an arbitrary set of unit triangles is removed from along alternating sides of the hexagon. In this paper we address the general case when an arbitrary set of unit triangles is removed from along the boundary of the hexagon.     

Algorithm for determining pure pointedness of self-affine tilings

Overlap coincidence in a self-affine tiling in Rd is equivalent to pure point dynamical spectrum of the tiling dynamical system. We interpret the overlap coincidence in the setting of substitution Delone set in Rd and find an efficient algorithm to check the pure point dynamical spectrum. This algorithm is easy to implement into a computer program. We give the program and apply it to several examples. In the course of the proof of the algorithm, we show a variant of the conjecture of Urbański (Solomyak (2006) [40]) on the Hausdorff dimension of the boundaries of fractal tiles.     

Growth functions for semi-regular tilings of the hyperbolic plane

This paper studies the growth function, with respect to the generating set of edge identifications, of a surface group with fundamental domainD in the hyperbolic plane ann-gon whose angles alternate between /p and /q. The possibilities ofn,p andq for which a torsion-free surface group can have such a fundamental polygon are classified, and the growth functions are computed. Conditions are given for which the denominator of the growth function is a product of cyclotomic polynomials and a Salem polynomial.This work was supported in part by NSF Research Grants.     

The -spectrum and spanning trees of tensor products of bipartite graphs

Recently, Knuth and Ciucu independently proved the surprising fact, conjectured by Stanley, that one connected component of the tensor product of a path with itself (the so-called ``Aztec diamond graph') has four times as many spanning trees as the other connected component, independent of the length of the path. We show here that much more is true: the connected components of the tensor product of any connected bipartite multigraphs all have essentially the same -spectrum. It follows at once that there is a simple formula relating their numbers of spanning trees.

     

Approximation of multivariate distribution functions

In the paper the unknown distribution function is approximated with a known distribution function by means of Taylor expansion. For this approximation a new matrix operation — matrix integral — is introduced and studied in [PIHLAK, M.: Matrix integral, Linear Algebra Appl. 388 (2004), 315–325]. The approximation is applied in the bivariate case when the unknown distribution function is approximated with normal distribution function. An example on simulated data is also given.