• Images
• Videos
• Documents
• Books
• Articles

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 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).

Thurston's height condition

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.

Counting tilings of regions

The number of ways to cover an m × n {\displaystyle m\times n} rectangle with m n 2 {\displaystyle {\frac {mn}{2}}} dominoes, calculated independently by Temperley & Fisher (1961) and Kasteleyn (1961), is given by ∏ j = 1 ⌈ m 2 ⌉ ∏ k = 1 ⌈ n 2 ⌉ ( 4 cos 2 ⁡ π j m + 1 + 4 cos 2 ⁡ π k n + 1 ) . {\displaystyle \prod _{j=1}^{\lceil {\frac {m}{2}}\rceil }\prod _{k=1}^{\lceil {\frac {n}{2}}\rceil }\left(4\cos ^{2}{\frac {\pi j}{m+1}}+4\cos ^{2}{\frac {\pi k}{n+1}}\right).} (sequence A099390 in the OEIS)

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\times n} rectangle with n dominoes: the sequence reduces to the Fibonacci sequence.¹

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\times 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.

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 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, 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.

Tatami

Tatami 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.³

Applications in statistical physics

There is a one-to-one correspondence between a periodic domino tiling and a ground state configuration of the fully-frustrated Ising model on a two-dimensional periodic lattice.⁴ At the ground state, each plaquette of the spin model must contain exactly one frustrated interaction. Therefore, viewing from the dual lattice, 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, 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, a puzzle concerning domino tiling of a 62-square area of a standard 8×8 chessboard (or checkerboard)
• Statistical mechanics

Notes

• Barahona, Francisco (1982), "On the computational complexity of Ising spin glass models", Journal of Physics A: Mathematical and General, 15 (10): 3241–3253, Bibcode:1982JPhA...15.3241B, doi:10.1088/0305-4470/15/10/028, MR 0684591
• Erickson, Alejandro; Ruskey, Frank (2013), "Domino tatami covering is NP-complete", in Lecroq, Thierry; Mouchard, Laurent (eds.), Combinatorial Algorithms: 24th International Workshop, IWOCA 2013, Rouen, France, July 10-12, 2013, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8288, Heidelberg: Springer, pp. 140–149, arXiv:1305.6669, doi:10.1007/978-3-642-45278-9_13, ISBN 978-3-642-45277-2, MR 3162068, S2CID 12738241
• Kasteleyn, P. W. (1961), "The statistics of dimers on a lattice, I: The number of dimer arrangements on a quadratic lattice", Physica, 27 (12): 1209–1225, Bibcode:1961Phy....27.1209K, doi:10.1016/0031-8914(61)90063-5
• Kenyon, Richard; Okounkov, Andrei (2005), "What is ... a dimer?" (PDF), Notices of the American Mathematical Society, 52 (3): 342–343
• Klarner, David; Pollack, Jordan (1980), "Domino tilings of rectangles with fixed width", Discrete Mathematics, 32 (1): 45–52, doi:10.1016/0012-365X(80)90098-9, MR 0588907, Zbl 0444.05009
• Ruskey, Frank; Woodcock, Jennifer (2009), "Counting fixed-height Tatami tilings", Electronic Journal of Combinatorics, 16 (1): R126, doi:10.37236/215, MR 2558263
• Thurston, W. P. (1990), "Conway's tiling groups", American Mathematical Monthly, 97 (8), Mathematical Association of America: 757–773, doi:10.2307/2324578, JSTOR 2324578
• Temperley, H. N. V.; Fisher, Michael E. (1961), "Dimer problem in statistical mechanics – an exact result", Philosophical Magazine, 6 (68): 1061–1063, Bibcode:1961PMag....6.1061T, doi:10.1080/14786436108243366

Further reading

• Bodini, Olivier; Latapy, Matthieu (2003), "Generalized tilings with height functions" (PDF), Morfismos, 7 (1): 47–68, arXiv:2101.08347, archived from the original (PDF) on 2021-11-25, retrieved 2021-09-19
• Faase, F. J. (1998), "On the number of specific spanning subgraphs of the graphs G × P n {\displaystyle G\times P_{n}} ", Ars Combinatoria, 49: 129–154, MR 1633083
• Hock, J. L.; McQuistan, R. B. (1984), "A note on the occupational degeneracy for dimers on a saturated two-dimensional lattice space", Discrete Applied Mathematics, 8: 101–104, doi:10.1016/0166-218X(84)90083-0, MR 0739603
• Kenyon, Richard (2000), "The planar dimer model with boundary: a survey", in Baake, Michael; Moody, Robert V. (eds.), Directions in mathematical quasicrystals, CRM Monograph Series, vol. 13, American Mathematical Society, pp. 307–328, ISBN 0-8218-2629-8, MR 1798998
• Propp, James (2005), "Lambda-determinants and domino-tilings", Advances in Applied Mathematics, 34 (4): 871–879, arXiv:math.CO/0406301, doi:10.1016/j.aam.2004.06.005, S2CID 15679557
• Sellers, James A. (2002), "Domino tilings and products of Fibonacci and Pell numbers", Journal of Integer Sequences, 5 (Article 02.1.2): 12, Bibcode:2002JIntS...5...12S
• Stanley, Richard P. (1985), "On dimer coverings of rectangles of fixed width", Discrete Applied Mathematics, 12: 81–87, doi:10.1016/0166-218x(85)90042-3, MR 0798013
• Wells, David (1997), The Penguin Dictionary of Curious and Interesting Numbers (revised ed.), London: Penguin, p. 182, ISBN 0-14-026149-4

References

1. Klarner & Pollack 1980. - Klarner, David; Pollack, Jordan (1980), "Domino tilings of rectangles with fixed width", Discrete Mathematics, 32 (1): 45–52, doi:10.1016/0012-365X(80)90098-9, MR 0588907, Zbl 0444.05009 https://doi.org/10.1016%2F0012-365X%2880%2990098-9 ↩

2. Ruskey & Woodcock 2009. - Ruskey, Frank; Woodcock, Jennifer (2009), "Counting fixed-height Tatami tilings", Electronic Journal of Combinatorics, 16 (1): R126, doi:10.37236/215, MR 2558263 https://www.combinatorics.org/ojs/index.php/eljc/article/view/v16i1r126 ↩

3. Erickson & Ruskey 2013. - Erickson, Alejandro; Ruskey, Frank (2013), "Domino tatami covering is NP-complete", in Lecroq, Thierry; Mouchard, Laurent (eds.), Combinatorial Algorithms: 24th International Workshop, IWOCA 2013, Rouen, France, July 10-12, 2013, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8288, Heidelberg: Springer, pp. 140–149, arXiv:1305.6669, doi:10.1007/978-3-642-45278-9_13, ISBN 978-3-642-45277-2, MR 3162068, S2CID 12738241 https://arxiv.org/abs/1305.6669 ↩

4. Barahona (1982). - Barahona, Francisco (1982), "On the computational complexity of Ising spin glass models", Journal of Physics A: Mathematical and General, 15 (10): 3241–3253, Bibcode:1982JPhA...15.3241B, doi:10.1088/0305-4470/15/10/028, MR 0684591 https://ui.adsabs.harvard.edu/abs/1982JPhA...15.3241B ↩