Domino tiling

In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominos, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a perfect matching in the grid graph formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares.An Aztec diamond of order 4, with 1024 domino tilingsOne possible tiling In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominos, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a perfect matching in the grid graph formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares. 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 A 0 {displaystyle A_{0}} with height 0, then for any node there is a path from A 0 {displaystyle A_{0}} to it. On this path define the height of each node A n + 1 {displaystyle A_{n+1}} (i.e. corners of the squares) to be the height of the previous node A n {displaystyle A_{n}} plus one if the square on the right of the path from A n {displaystyle A_{n}} to A n + 1 {displaystyle A_{n+1}} is black, and minus one otherwise. More details can be found in Kenyon & Okounkov (2005). William Thurston (1990) 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 that has as its vertices the points (x,y,z) in the three-dimensional integer lattice, 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 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. The number of ways to cover an m × n {displaystyle m imes n} rectangle with m n 2 {displaystyle {frac {mn}{2}}} dominoes, calculated independently by Temperley & Fisher (1961) and Kasteleyn (1961), 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 2 × n {displaystyle 2 imes n} rectangle with n dominoes: the sequence reduces to the Fibonacci sequence (sequence A000045 in the OEIS) (Klarner & Pollack 1980). 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 of an m n × m n {displaystyle mn imes mn} skew-symmetric matrix whose eigenvalues 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.