Tilings

✨ Summary

Overview

This paper is an expository survey of mathematical tiling problems, ranging from elementary puzzles to results involving combinatorics, algebra, probability, mathematical logic, electrical networks, and crystallography. It presents tilings as coverings of a region by prescribed pieces without overlap and organizes the discussion around existence, enumeration, approximation, structure, randomness, transformations, and infinite-plane behavior. The paper is based on Richard Stanley’s Clay Public Lecture at the IAS/Park City Mathematics Institute in July 2004. (claymath.org)

Main mathematical ideas

• Existence and obstructions: Simple coloring arguments prove impossibility results, such as the inability to tile a chessboard with two opposite corners removed using dominoes, or a 10 × 10 board with 1 × 4 rectangles. More sophisticated invariants, including nonabelian group-valued invariants, detect information that ordinary colorings cannot capture. Conway’s characterization of triangular hexagon arrays tiled by tribones is given as an example.
• Exact enumeration: The survey presents the Fisher–Temperley–Kasteleyn formula for domino tilings of even rectangles and the particularly simple formula (2^{n(n+1)/2}) for domino tilings of the Aztec diamond of order (n). The underlying methods include Pfaffians, determinants, and transfer matrices.
• Asymptotic enumeration: Rather than focusing only on exact counts, the paper compares exponential growth rates through “degrees of freedom per square.” It contrasts square regions with Aztec diamonds and introduces the Catalan-constant-based growth constant for large square boards.
• Certificates of impossibility: Hall’s marriage theorem is applied to domino tilings. If a region is not tileable, one can identify a collection of cells of one color having fewer neighboring cells of the other color, yielding a concise and verifiable obstruction.
• Rectangles tiled by rectangles: The de Bruijn–Klarner characterization is stated for when an (m\times n) rectangle can be tiled by (a\times b) rectangles. The paper also discusses tiling a square with similar rectangles and the role of algebraic numbers and the real parts of their conjugate roots.
• Perfect squared rectangles: A correspondence between squared-rectangle dissections and electrical networks is developed. Square side lengths correspond to electrical currents, while the governing equations correspond to Kirchhoff’s laws and Ohm’s law. This explains uniqueness up to scaling for a proposed layout, although positivity and distinctness of the resulting lengths are additional constraints.
• Random tilings: Random domino tilings can display large-scale deterministic structure despite local disorder. For large Aztec diamonds, the Arctic circle theorem describes a frozen outer region surrounding a fluctuating central region.
• Relations between tilings: A local flip replaces two parallel dominoes in a 2 × 2 square by the perpendicular pair. Thurston’s theorem states that for a region without holes, any domino tiling can be transformed into any other through a sequence of such flips.
• Infinite and aperiodic tilings: The survey discusses an unresolved tiling problem involving infinitely many rectangles whose total area is one, undecidability phenomena for polyomino tilings, the 17 plane crystallographic groups, and Penrose tilings. These examples show how tiling theory connects finite combinatorial questions with infinite structures and mathematical logic.

Influence and dissemination

The paper appears to have functioned primarily as an accessible survey and teaching resource rather than as a source of a single new theorem. It was subsequently published in The Mathematical Intelligencer, translated into German and Spanish, used as the basis for a 2006 tilings seminar, and recommended in later expository material such as Proofs from the Book. It is also cited by later work discussing self-similar polygonal tilings. These records document continued expository and educational use, but do not by themselves establish that the paper introduced the underlying research results it surveys. (klein.mit.edu)