In
geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
, a domino tiling of a region in the
Euclidean plane
In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
is a
tessellation
A tessellation or tiling is the covering of a surface, often a plane (mathematics), plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to high-dimensional ...
of the region by
domino
Dominoes is a family of tile-based games played with gaming pieces, commonly known as dominoes. Each domino is a rectangular tile, usually with a line dividing its face into two square ''ends''. Each end is marked with a number of spots (also ca ...
es, shapes formed by the union of two
unit square
In mathematics, a unit square is a square whose sides have length . Often, ''the'' unit square refers specifically to the square in the Cartesian plane with corners at the four points ), , , and .
Cartesian coordinates
In a Cartesian coordinate ...
s meeting edge-to-edge. Equivalently, it is a
perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
in the
grid graph
In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space , forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a latti ...
formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares.
Height functions
For some classes of tilings on a regular grid in two dimensions, it is possible to define a height function associating an integer to the
vertices of the grid. For instance, draw a chessboard, fix a node
with height 0, then for any node there is a path from
to it. On this path define the height of each node
(i.e. corners of the squares) to be the height of the previous node
plus one if the square on the right of the path from
to
is black, and minus one otherwise.
More details can be found in .
Thurston's height condition
describes a test for determining whether a simply-connected region, formed as the union of unit squares in the plane, has a domino tiling. He forms an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
that has as its vertices the points (''x'',''y'',''z'') in the three-dimensional
integer lattice
In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice in the Euclidean space whose lattice points are -tuples of integers. The two-dimensional integer lattice is also called the square lattice, or grid l ...
, where each such point is connected to four neighbors: if ''x'' + ''y'' is even, then (''x'',''y'',''z'') is connected to (''x'' + 1,''y'',''z'' + 1), (''x'' − 1,''y'',''z'' + 1), (''x'',''y'' + 1,''z'' − 1), and (''x'',''y'' − 1,''z'' − 1), while if ''x'' + ''y'' is odd, then (''x'',''y'',''z'') is connected to (''x'' + 1,''y'',''z'' − 1), (''x'' − 1,''y'',''z'' − 1), (''x'',''y'' + 1,''z'' + 1), and (''x'',''y'' − 1,''z'' + 1). The boundary of the region, viewed as a sequence of integer points in the (''x'',''y'') plane, lifts uniquely (once a starting height is chosen) to a path in this
three-dimensional graph A three-dimensional graph may refer to
* A graph (discrete mathematics), embedded into a three-dimensional space
* The graph of a function of two variables
In mathematics, the graph of a function f is the set of ordered pairs (x, y), where f(x ...
. A necessary condition for this region to be tileable is that this path must close up to form a simple closed curve in three dimensions, however, this condition is not sufficient. Using more careful analysis of the boundary path, Thurston gave a criterion for tileability of a region that was sufficient as well as necessary.
Counting tilings of regions
The number of ways to cover an
rectangle with
dominoes, calculated independently by and , is given by
When both ''m'' and ''n'' are odd, the formula correctly reduces to zero possible domino tilings.
A special case occurs when tiling the
rectangle with ''n'' dominoes: the sequence reduces to the
Fibonacci sequence
In mathematics, the Fibonacci numbers, commonly denoted , form a integer sequence, sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start ...
.
Another special case happens for squares with ''m'' = ''n'' = 0, 2, 4, 6, 8, 10, 12, ... is
These numbers can be found by writing them as the
Pfaffian
In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, ...
of an
skew-symmetric matrix
In mathematics, particularly in linear algebra, a skew-symmetric (or antisymmetric or antimetric) matrix is a square matrix whose transpose equals its negative. That is, it satisfies the condition
In terms of the entries of the matrix, if a_ ...
whose
eigenvalue
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
s can be found explicitly. This technique may be applied in many mathematics-related subjects, for example, in the classical, 2-dimensional computation of the
dimer-dimer correlator function in
statistical mechanics
In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...
.
The number of tilings of a region is very sensitive to boundary conditions, and can change dramatically with apparently insignificant changes in the shape of the region. This is illustrated by the number of tilings of an
Aztec diamond
In combinatorial mathematics, an Aztec diamond of order ''n'' consists of all squares of a square lattice whose centers (''x'',''y'') satisfy , ''x'', + , ''y'', ≤ ''n''. Here ''n'' is a fixed integer, and the square lattice consists of unit s ...
of order ''n'', where the number of tilings is 2
(''n'' + 1)''n''/2. If this is replaced by the "augmented Aztec diamond" of order ''n'' with 3 long rows in the middle rather than 2, the number of tilings drops to the much smaller number D(''n'',''n''), a
Delannoy number
In mathematics, a Delannoy number D describes the number of paths from the southwest corner (0, 0) of a rectangular grid to the northeast corner (''m'', ''n''), using only single steps north, northeast, or east. The Delannoy numbers are named aft ...
, which has only exponential rather than
super-exponential growth in ''n''. For the "reduced Aztec diamond" of order ''n'' with only one long middle row, there is only one tiling.
File:Diamant azteque.svg, An Aztec diamond of order 4, which has 1024 domino tilings
File:Diamant azteque plein.svg, One possible tiling
Tatami
Tatami
A is a type of mat used as a flooring material in traditional Japanese-style rooms. Tatamis are made in standard sizes, twice as long as wide, about 0.9 m by 1.8 m depending on the region. In martial arts, tatami are the floor used for traini ...
are Japanese floor mats in the shape of a domino (1x2 rectangle). They are used to tile rooms, but with additional rules about how they may be placed. In particular, typically, junctions where three tatami meet are considered auspicious, while junctions where four meet are inauspicious, so a proper tatami tiling is one where only three tatami meet at any corner. The problem of tiling an irregular room by tatami that meet three to a corner is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
.
Applications in statistical physics
There is a
one-to-one correspondence
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
between a periodic domino tiling and a ground state configuration of the fully-frustrated
Ising model
The Ising model () (or Lenz-Ising model or Ising-Lenz model), named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables that represent ...
on a two-dimensional periodic lattice. To see that, we note that at the ground state, each plaquette of the spin model must contain exactly one
frustrated interaction. Therefore, viewing from the
dual lattice
In the theory of lattices, the dual lattice is a construction analogous to that of a dual vector space. In certain respects, the geometry of the dual lattice of a lattice L is the reciprocal of the geometry of L , a perspective which underlie ...
, each frustrated edge must be "covered" by a ''1x2'' rectangle, such that the rectangles span the entire lattice and do not overlap, or a domino tiling of the dual lattice.
See also
*
Gaussian free field
In probability theory and statistical mechanics, the Gaussian free field (GFF) is a Gaussian random field, a central model of random surfaces (random height functions). gives a mathematical survey of the Gaussian free field.
The discrete version ...
, the scaling limit of the height function in the generic situation (e.g., inside the inscribed disk of a large aztec diamond)
*
Mutilated chessboard problem
The mutilated chessboard problem is a tiling puzzle posed by Max Black in 1946 that asks:
Suppose a standard 8×8 chessboard (or checkerboard) has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoe ...
, a puzzle concerning domino tiling of a 62-square area of a standard 8×8
chessboard
A chessboard is a used to play chess. It consists of 64 squares, 8 rows by 8 columns, on which the chess pieces are placed. It is square in shape and uses two colours of squares, one light and one dark, in a chequered pattern. During play, the bo ...
(or
checkerboard
A checkerboard (American English) or chequerboard (British English; see spelling differences) is a board of checkered pattern on which checkers (also known as English draughts) is played. Most commonly, it consists of 64 squares (8×8) of altern ...
)
*
Statistical mechanics
In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...
Notes
References
*
*
*
*
*
*
*
*
Further reading
*
*
*
*
*
*
*
*
{{Tessellation
Combinatorics
Exactly solvable models
Lattice models
Matching (graph theory)
Recreational mathematics
Statistical mechanics
Tiling puzzles