The authors consider the set of all tilings by dominoes (\(2\times 1\) rectangles) of a surface, possibly with boundary, consisting of unit squares. Convert this set into a graph by joining two tilings by an edge if they differ by a flip, i.e., a \(90^\circ\) rotation of a pair of side by side dominoes. Tilings of a rectangle of integral sides were counted by Kasteleyn. More recently Lieb and Loss, showed how to count tilings of general regions by making use of determinants. Conway and Lagarias studied the problem of tiling subsets of \(\mathbb{R}^2\) with a given set of tiles, by group-theoretical techniques. Thurston adopted these techniques to study domino tilings, producing a necessary and sufficient condition for a simply connected region of the plane to be tiled by dominoes.
Here, the authors are interested in studying \(T\), the set of all possible tilings of a fixed region. Given a tiling, they perform a “flip” by lifting two dominoes and placing them back in a different position. Clearly the two dominoes must form a square of side 2. Two tilings are adjacent in \(T\) if we move from one to the other by a flip. Turn \(T\) into a graph by joining adjacent tilings by edges, and define connected components of \(T\) and distance between tilings in the usual way. The authors obtain a very operational criterion for two tilings to belong to the same connected components of \(T\), giving simple formulas for distances, and a method to construct geodesics in this graph. If the region is simply connected, \(T\) is connected. By naturally adjoining to this graph higher-dimensional cells they obtain a CW-complex whose connected components are homotopically equivalent to points or circles. As a consequence for any region different from a torus or Klein bottle, all geodesics with common end points are equivalent in the following sense. Build a graph whose vertices are these geodesics, adjacent if they differ only by the order of two flips on disjoint squares. This graph is connected.
The techniques of the paper provide us with a fair understanding of the combinatorial, topological and metric structure of \(T\). Thus, for example, each connected component of \(T\) is a lattice. The authors give a simple formula for the distance between tilings and characterize the shortest routes between points. In a sense, all such routes are equivalent. A topological version of this statement is that \(T\) induces naturally a CW-complex whose connected components are contractable. More generally, the authors consider quadric surfaces and obtain analogous results to certain theorems.