ALGEBRAIC COMBINATORICS

no. 1
Domino tilings and flips in dimensions 4 and higher
Klivans, Caroline J.1; Saldanha, Nicolau C.2
1 Division of Applied Mathematics, Box F 182 George Street Brown University Providence, RI 02912 USA
2 Departamento de Matemática, PUC-Rio Rua Marquês de São Vicente 225, Rio de Janeiro, RJ 22451-900 Brazil
Algebraic Combinatorics, Volume 5 (2022) no. 1, pp. 163-185.

In this paper we consider domino tilings of bounded regions in dimension n≥4. We define the twist of such a tiling, an elements of ℤ/(2), and prove that it is invariant under flips, a simple local move in the space of tilings.

We investigate which regions 𝒟 are regular, i.e. whenever two tilings t 0 and t 1 of 𝒟×[0,N] have the same twist then t 0 and t 1 can be joined by a sequence of flips provided some extra vertical space is allowed. We prove that all boxes are regular except 𝒟=[0,2] 3 .

Furthermore, given a regular region 𝒟, we show that there exists a value M (depending only on 𝒟) such that if t 0 and t 1 are tilings of equal twist of 𝒟×[0,N] then the corresponding tilings can be joined by a finite sequence of flips in 𝒟×[0,N+M]. As a corollary we deduce that, for regular 𝒟 and large N, the set of tilings of 𝒟×[0,N] has two twin giant components under flips, one for each value of the twist.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.205
Classification: 05B45, 52C20, 52C22, 05C70
Keywords: Higher dimensional tilings, dominoes, dimers
Klivans, Caroline J. 1; Saldanha, Nicolau C. 2

1 Division of Applied Mathematics, Box F 182 George Street Brown University Providence, RI 02912 USA
2 Departamento de Matemática, PUC-Rio Rua Marquês de São Vicente 225, Rio de Janeiro, RJ 22451-900 Brazil
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2022__5_1_163_0,
     author = {Klivans, Caroline J. and Saldanha, Nicolau C.},
     title = {Domino tilings and flips in dimensions 4 and higher},
     journal = {Algebraic Combinatorics},
     pages = {163--185},
     publisher = {MathOA foundation},
     volume = {5},
     number = {1},
     year = {2022},
     doi = {10.5802/alco.205},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.205/}
}
TY  - JOUR
AU  - Klivans, Caroline J.
AU  - Saldanha, Nicolau C.
TI  - Domino tilings and flips in dimensions 4 and higher
JO  - Algebraic Combinatorics
PY  - 2022
SP  - 163
EP  - 185
VL  - 5
IS  - 1
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.205/
DO  - 10.5802/alco.205
LA  - en
ID  - ALCO_2022__5_1_163_0
ER  - 
%0 Journal Article
%A Klivans, Caroline J.
%A Saldanha, Nicolau C.
%T Domino tilings and flips in dimensions 4 and higher
%J Algebraic Combinatorics
%D 2022
%P 163-185
%V 5
%N 1
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.205/
%R 10.5802/alco.205
%G en
%F ALCO_2022__5_1_163_0
Klivans, Caroline J.; Saldanha, Nicolau C. Domino tilings and flips in dimensions 4 and higher. Algebraic Combinatorics, Volume 5 (2022) no. 1, pp. 163-185. doi : 10.5802/alco.205. https://alco.centre-mersenne.org/articles/10.5802/alco.205/

[1] Ardila, Federico; Stanley, Richard P. Tilings, Math. Intelligencer, Volume 32 (2010) no. 4, pp. 32-43 | DOI | MR | Zbl

[2] Elkies, Noam; Kuperberg, Greg; Larsen, Michael; Propp, James Alternating-sign matrices and domino tilings. I, J. Algebraic Combin., Volume 1 (1992) no. 2, pp. 111-132 | DOI | MR | Zbl

[3] Elkies, Noam; Kuperberg, Greg; Larsen, Michael; Propp, James Alternating-sign matrices and domino tilings. II, J. Algebraic Combin., Volume 1 (1992) no. 3, pp. 219-234 | DOI | MR | Zbl

[4] Freire, Juliana; Klivans, Caroline J.; Milet, Pedro H.; Saldanha, Nicolau C. On the connectivity of spaces of three-dimensional tilings (2022) (to appear in Transactions of the AMS)

[5] Kasteleyn, P. W. The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice, Physica, Volume 27 (1961), pp. 1209-1225 | DOI | Zbl

[6] Kenyon, Richard Lectures on dimers (2009) (57 pages, https://arxiv.org/abs/0910.3129) | MR

[7] Klivans, Caroline J.; Saldanha, Nicolau C. Domino tilings and flips in dimensions 4 and higher: Examples and Additional Material (2021) (https://www.dam.brown.edu/people/cklivans/tiling_code.html, http://www.mat.puc-rio.br/~nicolau/4domino/index.html)

[8] Milet, Pedro H.; Saldanha, Nicolau C. Domino tilings of three-dimensional regions: flips and twists (2014) (38 pages, https://arxiv.org/abs/1410.7693)

[9] Milet, Pedro H.; Saldanha, Nicolau C. Flip invariance for domino tilings of three-dimensional regions with two floors, Discrete Comput. Geom., Volume 53 (2015) no. 4, pp. 914-940 | DOI | MR | Zbl

[10] Pak, Igor; Yang, Jed The complexity of generalized domino tilings, Electron. J. Combin., Volume 20 (2013) no. 4, Paper no. 12, 23 pages | DOI | MR | Zbl

[11] Saldanha, Nicolau C. Singular polynomials of generalized Kasteleyn matrices, J. Algebraic Combin., Volume 16 (2002) no. 2, pp. 195-207 | DOI | MR | Zbl

[12] Saldanha, Nicolau C. Domino tilings of cylinders: the domino group and connected components under flips (2019) (37 pages, https://arxiv.org/abs/1912.12102)

[13] Saldanha, Nicolau C. Domino tilings of cylinders: connected components under flips and normal distribution of the twist, Electron. J. Combin., Volume 28 (2021) no. 1, Paper no. 1.28, 23 pages | DOI | MR | Zbl

[14] Saldanha, Nicolau C.; Tomei, Carlos; Casarin, M. A. Jun.; Romualdo, D. Spaces of domino tilings, Discrete Comput. Geom., Volume 14 (1995) no. 2, pp. 207-233 | DOI | MR | Zbl

[15] Temperley, H. N. V.; Fisher, Michael E. Dimer problem in statistical mechanics—an exact result, Philos. Mag. (8), Volume 6 (1961), pp. 1061-1063 | DOI | MR | Zbl

[16] Thurston, William P. Conway’s tiling groups, Amer. Math. Monthly, Volume 97 (1990) no. 8, pp. 757-773 | DOI | MR | Zbl

Cited by Sources: