Domino tiling
Domino tiling refers to the covering of a finite region in the plane, typically composed of unit squares such as a rectangular m × n grid, using dominoes—each a 1 × 2 or 2 × 1 rectangle formed by two adjacent unit squares—such that every square is covered exactly once without overlaps or gaps.[1][2] Such tilings exist for an m × n grid if and only if the total number of squares mn is even, ensuring the region can be bipartitioned into equal sets of black and white squares under a checkerboard coloring.[1][2] The study of domino tilings originated as a combinatorial puzzle in the early 20th century, but gained prominence in 1961 through independent solutions by Percy Kasteleyn and by Harold Temperley and Michael Fisher, who connected it to the dimer model in statistical mechanics for calculating partition functions of lattice gases.[3][1] In graph theory terms, a domino tiling corresponds to a perfect matching in the dual bipartite graph of the region, where vertices represent squares and edges connect adjacent pairs, allowing the number of tilings to be computed via the permanent or Pfaffian of the adjacency matrix.[2][1] For the specific case of a 2 × n grid, the number of distinct tilings is given by the (n + 1)th Fibonacci number, where the Fibonacci sequence is defined as F_1 = 1, F_2 = 1, and F_k = F_{k-1} + F_{k-2} for k > 2, reflecting the recursive nature of placements.[2][1] More generally, for an m × n grid with m even, Kasteleyn's method yields an exact closed-form formula involving a double product over cosines: T(m, n) = \prod_{j=1}^{m/2} \prod_{k=1}^n \left( 4 \cos^2 \frac{\pi j}{m+1} + 4 \cos^2 \frac{\pi k}{n+1} \right)^{1/2}, enabling efficient computation via determinants.[1][2] Beyond rectangles, domino tilings extend to arbitrary polyomino regions that have an even number of squares and equal numbers of black and white squares under a checkerboard coloring; stronger necessary conditions for tileability, using combinatorial group theory, were established by John Conway and Jeffrey Lagarias in 1990.[4] For simply connected regions, the space of tilings is connected under local flips.[3] Applications span statistical physics, where tilings model dimer coverings to compute free energies and phase transitions in two-dimensional systems, and computer science, where counting tilings is polynomial-time solvable for planar graphs but NP-hard for generalized variants on non-planar surfaces.[2][3] These connections highlight domino tilings as a foundational problem in enumerative combinatorics, bridging discrete mathematics with physical models.[1]Fundamentals
Definition and Basic Properties
A domino tiling of a finite region in the plane, typically a polyomino or a portion of the square grid, is a covering of that region using 1×2 or 2×1 rectangles known as dominoes, such that the dominoes have disjoint interiors, do not overlap, and their union exactly fills the region without gaps.[5] Each domino covers precisely two adjacent unit squares, either horizontally or vertically.[5] A fundamental property of any region admitting a domino tiling is that its total area must be even, as each domino contributes an area of 2, ensuring the parity condition for complete coverage.[6] Moreover, the square grid underlying the region is bipartite, allowing a black-white coloring of the squares such that adjacent squares receive different colors; in any valid tiling, each domino covers exactly one black square and one white square, so the region must contain an equal number of black and white squares.[7] This colorability argument provides a necessary condition for tilability and can demonstrate impossibility in certain cases. For example, a 2×n rectangle can always be tiled with dominoes when n is a positive integer, as illustrated by the simplest case of a 2×2 grid, which admits two tilings: either two horizontal dominoes stacked vertically or two vertical dominoes side by side. A 4×4 grid expands this to more configurations, such as all vertical dominoes in columns, all horizontal in rows, or mixed arrangements like a central 2×2 block of verticals surrounded by horizontals, highlighting the combinatorial variety while maintaining the even-area and balanced-coloring properties. The number of such tilings for the 2×n case follows the Fibonacci sequence, offering an initial glimpse into enumeration patterns.[8] A classic illustration of the coloring condition's power is the mutilated 8×8 chessboard, where two opposite corners (both the same color, say white) are removed, leaving 30 white squares and 32 black squares; since no domino can cover two squares of the same color, a tiling is impossible despite the even total area of 62.[9] Such examples underscore the interplay between geometric structure and graph-theoretic bipartiteness in determining tilability.Historical Development
The mutilated chessboard problem, a classic tiling puzzle involving dominoes, was first formally proposed by philosopher Max Black in his 1946 book Critical Thinking, where he posed the question of whether a standard 8×8 chessboard with two opposite corners removed could be covered by 31 dominoes, each covering two adjacent squares.[9] This puzzle, which demonstrates impossibility through a simple coloring argument (removing two squares of the same color leaves an imbalance), gained popularity in recreational mathematics and highlighted early interest in tiling constraints, though dominoes themselves trace back to ancient Chinese tile games from around 1120 CE, with European adoption by the 18th century.[10] Early enumerative efforts, such as Percy MacMahon's work on rectangular tilings in 1916, laid groundwork for formal study.[11] In the mid-20th century, domino tiling transitioned from puzzles to rigorous mathematical study, particularly through connections to statistical mechanics. In 1961, physicist Pieter W. Kasteleyn developed the Pfaffian method to count the exact number of domino tilings of planar regions, expressing it as the square root of a determinant of a specially oriented adjacency matrix, a breakthrough motivated by dimer models in physics.[12] Independently that same year, H. N. V. Temperley and Michael E. Fisher arrived at a similar result using determinant techniques for lattice coverings, establishing the foundations for enumerating perfect matchings in bipartite graphs and linking tilings to partition functions in two-dimensional systems. These works formalized domino tilings as a model for solving broader problems in combinatorics and physics during the 1960s. Further advancements in the 1980s and 1990s deepened the theoretical framework. William Thurston introduced height functions in 1990 to characterize valid domino tilings of simply connected regions, assigning integer heights to vertices such that adjacent heights differ by ±1 or ±3, providing a criterion for tileability without explicit construction.[13] A key milestone came in 1992 with the introduction of the Aztec diamond by Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp, a centered square region whose tilings exhibit arctic circle phenomena in random configurations, connecting enumerative combinatorics to probabilistic limits. Influential figures shaped the field's evolution. Solomon Golomb (1932–2016), a pioneering combinatorialist, coined the term "polyominoes" in 1953 while studying connected unions of squares, including dominoes as the simplest case, and explored their tiling properties in his seminal 1965 book Polyominoes: Puzzles, Patterns, Problems, and Packings. Richard Stanley, a leading enumerative combinatorialist, applied symmetric function theory to count domino tilings of regions like rectangles and Aztec diamonds, linking them to plane partitions and alternating-sign matrices in works from the 1980s onward.[14] James Propp, a mathematician at the University of Massachusetts Lowell, popularized domino tilings through puzzles, research groups, and expository articles in the 1990s, notably advancing enumeration techniques and random tiling statistics via the Aztec diamond.[14] These contributions have influenced modern applications in statistical mechanics, where dimer models simulate phase transitions and critical phenomena.Representational Frameworks
Height Functions
Height functions offer a bijective correspondence between domino tilings of a simply connected planar region and certain integer-valued functions on the vertices of the region. A height function assigns an integer height to each vertex in the region such that the absolute difference in heights between two adjacent vertices connected by a grid edge is either 1 or 3. Specifically, if the connecting edge is not crossed by a domino (i.e., separates squares covered by different dominoes or is on the boundary), the heights differ by ±1; if the edge is crossed by a domino (i.e., is the internal shared boundary between the two squares of a domino), the difference is ±3. The sign of the difference depends on the orientation of the traversal relative to a fixed checkerboard coloring of the squares, where black and white squares alternate. This setup interprets the tiling as a stepped surface in three dimensions, with dominoes representing height steps of 3 units and uncrossed edges as 1-unit changes.[15] To construct a height function from a given domino tiling, assign height 0 to one base vertex and propagate heights to adjacent vertices according to the difference rules: traversing an edge crossed by a horizontal domino increases or decreases the height by 3 depending on whether the traversal goes from the "lower" to "higher" side or vice versa (with sign determined by the coloring), while edges crossed by vertical dominoes follow analogous rules rotated by 90 degrees; uncrossed edges change height by 1 in the appropriate direction. The resulting heights are path-independent due to a net change of 4 around each unit square plaquette and are defined up to an additive constant; they are considered modulo 4, reflecting the four possible local configurations around a plaquette due to the bipartite nature of the grid. Distinct tilings correspond precisely to distinct equivalence classes of such height functions with fixed boundary values, establishing the bijection.[15] These height functions possess notable properties, including unimodality, where the heights along any path from boundary to interior exhibit a single peak, and convexity, meaning the function lies below its tangent planes in a discrete sense, facilitating analysis of the tiling space as a distributive lattice under local flips. Moreover, height functions relate directly to perfect matchings in the dual graph of the region, where vertices represent squares, edges connect adjacent squares, and the matching encodes the domino placements via the ±3 differences across the crossed edges.[16][15] As an illustrative example, consider a 2×4 rectangle, a simply connected region with even area. Fix boundary conditions by setting the bottom-left vertex to height 0 and propagating along the boundary: the bottom row vertices might have heights 0, 1, 2, 3, with upper rows adjusted accordingly based on the tiling. For the all-horizontal tiling (horizontal dominoes in each row), the heights form a flat stepped surface with differences of 3 across the vertical internal edges of each domino and 1 along horizontal edges. An alternative all-vertical tiling shifts the heights, creating a different equivalence class modulo 4, while maintaining fixed boundary values that ensure compatibility with the region's parity.Thurston's Height Condition
In 1990, William Thurston established a precise criterion for determining whether a given height function on the vertices of a simply connected polyomino region corresponds to an actual domino tiling, leveraging the structure of Conway's tiling groups to encode tiling configurations via integer-valued heights.[15] This theorem provides both a necessary and sufficient condition for realizability, enabling efficient algorithmic checks for tileability.[17] The formal statement of Thurston's theorem is as follows: Let R \subset \mathbb{Z}^2 be a simply connected polyomino with vertex set V(R), and let h: V(R) \to \mathbb{Z} be an integer-valued function with h(0,0) = 0. Then h is the height function of a domino tiling of R if and only if it satisfies the following slope conditions:(i) For any two vertices x = (a_1, b_1), y = (a_2, b_2) \in V(R) with a_1 \equiv a_2 \pmod{2} and b_1 \equiv b_2 \pmod{2}, h(x) - h(y) \equiv 0 \pmod{4}.
(ii) For every boundary edge (x, y) in \partial R, oriented such that the interior white square (in the chessboard coloring) lies to the left, h(x) - h(y) = 1.
(iii) For every internal edge (x, y) \in E(R), |h(x) - h(y)| \leq 3. These conditions ensure that height changes across edges are "balanced," forming consistent paths around each face with a net increase of 4 in the counterclockwise direction (reflecting the four unit steps around an untiled square face, adjusted for domino placements that effectively reroute the path with a +3/-1 pair across the domino). Forbidden configurations include height drops exceeding 3 on any edge (violating the Lipschitz-like bound) or parity mismatches that prevent reconstruction of tiles.[17][15] The proof relies on topological arguments within the Cayley graph of the tiling group, where the height function arises as a homomorphism to \mathbb{Z} (the abelianization capturing net displacements). To show sufficiency, one constructs the maximal height function by iteratively placing dominoes at boundary-determined local maxima, ensuring no interior violations; this process terminates with a tiling if the conditions hold, as lifts to the universal cover avoid intersections akin to train tracks in the plane. Equivalence to non-intersecting lattice paths follows by mapping the height gradients to path elevations, where valid heights correspond to non-crossing configurations in the dual graph. Necessity is verified by direct integration along tiling boundaries, confirming the local rules.[15][17] For illustration, consider a 4×4 grid region with 8 black and 8 white squares. A valid height function for the all-horizontal tiling might assign heights starting at 0 on the bottom-left vertex, increasing by 1 along horizontal edges and by 3 vertically across each horizontal domino pair (e.g., row vertices: 0,1; next row: 2,3; and so on, satisfying parity and bounds). An invalid function, such as one with a +4 jump on an internal horizontal edge, violates condition (iii), corresponding to an impossible "overhang" that cannot be resolved by any domino placement, as it implies a disconnected or overlapping tile.[17]