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.     

Perfect Matchings and Perfect Powers

In the last decade there have been many results about special families of graphs whose number of perfect matchings is given by perfect or near perfect powers (N. Elkies et al., J. Algebraic Combin. 1 (1992), 111–132; B.-Y. Yang, Ph.D. thesis, Department of Mathematics, MIT, Cambridge, MA, 1991; J. Propp, New Perspectives in Geometric Combinatorics, Cambridge University Press, 1999). In this paper we present an approach that allows proving them in a unified way. We use this approach to prove a conjecture of James Propp stating that the number of tilings of the so-called Aztec dungeon regions is a power (or twice a power) of 13. We also prove a conjecture of Matt Blum stating that the number of perfect matchings of a certain family of subgraphs of the square lattice is a power of 3 or twice a power of 3. In addition we obtain multi-parameter generalizations of previously known results, and new multi-parameter exact enumeration results. We obtain in particular a simple combinatorial proof of Bo-Yin Yang's multivariate generalization of fortresses, a result whose previously known proof was quite complicated, amounting to evaluation of the Kasteleyn matrix by explicit row reduction. We also include a new multivariate exact enumeration of Aztec diamonds, in the spirit of Stanley's multivariate version.     

Characterization of Polytopes via Tilings with Similar Pieces

Generalizing results by Valette, Zamfirescu and Laczkovich, we will prove that a convex body K is a polytope if there are sufficiently many tilings which contain a tile similar to K. Furthermore, we give an example that this cannot be improved.     

The Kernel of the Adjacency Matrix of a Rectangular Mesh

   Abstract. Given an m × n rectangular mesh, its adjacency matrix A , having only integer entries, may be interpreted as a map between vector spaces over an arbitrary field K . We describe the kernel of A : it is a direct sum of two natural subspaces whose dimensions are equal to

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.

     

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.     

Detecting Combinatorial Hierarchy in Tilings Using Derived Voronoi Tessellations

Abstract. Tilings of R ² can display hierarchy similar to that seen in the limit sequences of substitutions. Self-similarity for tilings has been used as the standard generalization, but this viewpoint is limited because such tilings are analogous to limit points of constant-length substitutions. To generalize limit points of non-constant-length substitutions, we define hierarchy for infinite, labelled graphs, then extend this definition to tilings via their dual graphs. Examples of combinatorially substitutive tilings that are not self-similar are given. We then find a sufficient condition for detecting combinatorial hierarchy that is motivated by the characterization by Durand of substitutive sequences. That characterization relies upon the construction of the ``derived sequence'—a recoding in terms of reappearances of an initial block. Following this, we define the ``derived Vorono? tiling'—a retiling in terms of reappearances of an initial patch of tiles. Using derived Vorono? tilings, we obtain a sufficient condition for a tiling to be combinatorially substitutive.     

Fractal tiles associated with shift radix systems

Shift radix systems form a collection of dynamical systems depending on a parameter r which varies in the d-dimensional real vector space. They generalize well-known numeration systems such as beta-expansions, expansions with respect to rational bases, and canonical number systems. Beta-numeration and canonical number systems are known to be intimately related to fractal shapes, such as the classical Rauzy fractal and the twin dragon. These fractals turned out to be important for studying properties of expansions in several settings.In the present paper we associate a collection of fractal tiles with shift radix systems. We show that for certain classes of parameters r these tiles coincide with affine copies of the well-known tiles associated with beta-expansions and canonical number systems. On the other hand, these tiles provide natural families of tiles for beta-expansions with (non-unit) Pisot numbers as well as canonical number systems with (non-monic) expanding polynomials.We also prove basic properties for tiles associated with shift radix systems. Indeed, we prove that under some algebraic conditions on the parameter r of the shift radix system, these tiles provide multiple tilings and even tilings of the d-dimensional real vector space. These tilings turn out to have a more complicated structure than the tilings arising from the known number systems mentioned above. Such a tiling may consist of tiles having infinitely many different shapes. Moreover, the tiles need not be self-affine (or graph directed self-affine).     

Detecting Combinatorial Hierarchy in Tilings Using Derived Voronoi Tessellations

   Abstract. Tilings of R ² can display hierarchy similar to that seen in the limit sequences of substitutions. Self-similarity for tilings has been used as the standard generalization, but this viewpoint is limited because such tilings are analogous to limit points of constant-length substitutions. To generalize limit points of non-constant-length substitutions, we define hierarchy for infinite, labelled graphs, then extend this definition to tilings via their dual graphs. Examples of combinatorially substitutive tilings that are not self-similar are given. We then find a sufficient condition for detecting combinatorial hierarchy that is motivated by the characterization by Durand of substitutive sequences. That characterization relies upon the construction of the ``derived sequence'—a recoding in terms of reappearances of an initial block. Following this, we define the ``derived Vorono? tiling'—a retiling in terms of reappearances of an initial patch of tiles. Using derived Vorono? tilings, we obtain a sufficient condition for a tiling to be combinatorially substitutive.     

Convex pentagons that admit <Emphasis Type="Italic">i</Emphasis>-block transitive tilings

The problem of classifying the convex pentagons that admit tilings of the plane is a long-standing unsolved problem. Previous to this article, there were 14 known distinct kinds of convex pentagons that admit tilings of the plane. Five of these types admit tile-transitive tilings (i.e. there is a single transitivity class with respect to the symmetry group of the tiling). The remaining 9 types do not admit tile-transitive tilings, but do admit either 2-block transitive tilings or 3-block transitive tilings; these are tilings comprised of clusters of 2 or 3 pentagons such that these clusters form tile-2-transitive or tile-3-transitive tilings. In this article, we present some combinatorial results concerning pentagons that admit i-block transitive tilings for \(i \in \mathbb {N}\). These results form the basis for an automated approach to finding all pentagons that admit i-block transitive tilings for each \(i \in \mathbb {N}\). We will present the methods of this algorithm and the results of the computer searches so far, which includes a complete classification of all pentagons admitting i-block transitive tilings for \(i \le 4\), among which is a new 15th type of convex pentagon that admits a tile-3-transitive tiling.     

Upper Bounds for the Laplacian Graph Eigenvalues

We first apply non-negative matrix theory to the matrix K = D A, where D and A are the degree-diagonal and adjacency matrices of a graph G, respectively, to establish a relation on the largest Laplacian eigenvalue λ1 (G) of G and the spectral radius p(K) of K. And then by using this relation we present two upper bounds for λ1(G) and determine the extremal graphs which achieve the upper bounds.     

Self similar symmetric planar tilings

A new variant of the projection method yields aperiodic tilings of the plane with some rotational symmetry. In particular we display three tilings E _s with full D ₇-symmetry. Each of them is self similar. Further, there is an uncountable number of tilings E without any symmetry, but being almost equivalent to each of the symmetric tiling E _s , i.e. for each R > 0 there is a translation T(E) of E which is equal to E _s in all vertices but a set of error points which are distributed all over the plane but have mutual distance greater than R.      

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.     

Self-Replicating Tiles and Their Boundary

All self-replicating lattice tilings of the plane can be constructed using special iterated function systems (IFS). Certain self-replicating curves can be constructed using the recurrent set method (RS). A bijection between the IFS parameters and the RS parameters is such that the curve K produced by the RS parameters is the boundary of the tile T produced by the IFS parameters. The correspondence is algorithmic in that K can be drawn from the IFS data using turtle graphics and T can be drawn from the RS data using an IFS iteration. Received April 15, 1997, and in revised form November 13, 1997, and April 6, 1998.     

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.     

MULTIRESOLUTION ANALYSIS, SELF-SIMILAR TILINGS AND HAAR WAVELETS ON THE HEISENBERG GROUP

In this article, the properties of multiresolution analysis and self-similar tilings on the Heisenberg group are studied. Moreover, we establish a theory to construct an orthonormal Haar wavelet base in L^2（H^d） by using self-similar tilings for the acceptable dilations on the Heisenberg group.     

Invariant measures for non-primitive tiling substitutions

We consider self-affine tiling substitutions in Euclidean space and the corresponding tiling dynamical systems. It is well known that in the primitive case, the dynamical system is uniquely ergodic. We investigate invariant measures when the substitution is not primitive and the tiling dynamical system is non-minimal. We prove that all ergodic invariant probability measures are supported on minimal components, but there are other natural ergodic invariant measures, which are infinite. Under some mild assumptions, we completely characterize σ-finite invariant measures which are positive and finite on a cylinder set. A key step is to establish recognizability of non-periodic tilings in our setting. Examples include the “integer Sierpiński gasket and carpet” tilings. For such tilings, the only invariant probability measure is supported on trivial periodic tilings, but there is a fully supported σ-finite invariant measure that is locally finite and unique up to scaling.     

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.     

Equivalence of Self-similar and Pseudo-self-similar Tiling Spaces in ℝ<Superscript>2</Superscript>

Given a tiling T, one may form a related tiling, called the derived Voronoi tiling of T, based on a patch of tiles in T. Similarly, for a tiling space X, one can identify a patch which appears regularly in all tilings in X, and form a derived Voronoi space of tilings, based on that patch.