3
$\begingroup$

Fix a $n \times m$ rectangle and consider the set $S_{n,m}$ of all its dominos tilings. Here are examples with $n=m=8$.

enter image description here

The set $S_{n,m}$ is empty if and only if $nm$ is odd, and for small $nm$, its cardinal is available at A099390 or A004003. For example, $|S_{8,8}| = 2444888770250892795802079170816 = 2^8 101^2 5849^2 9929^2 16661^2 \simeq 2.4 \times 10^{30}$.

Two domino tilings in $S_{n,m}$ will be called equivalent if one can obtain one from the other by applying a transformation consisting on doing successive $90°$ rotation of some $2 \times 2$ squares tiled by two dominos. Such a transformation is illustrated in above animation, and observe that the first domino tiling turns out to be equivalent to a trivial one (i.e. when all the dominos have the same state, where state means vertical or horizontal).

Question: Is every domino tiling (of rectangle) equivalent to a trivial one?

The set of above transformations forms a groupoid, say $\mathcal{G}_{n,m}$. The question can be reformulated by asking whether the action of $\mathcal{G}_{n,m}$ on $S_{n,m}$ is transitive.

Note that if $1 \in \{n,m\}$ then the answer is trivially yes. Now, if $1 \not \in \{n,m\}$, a counter-example could be given by a domino tiling without $2 \times 2$ square (tiled by two dominos), but such counter-example does not exist, because otherwise consider the domino in its top left corner, its state (vertical or horizontal) fixes the state of all the dominos in the diagonal, and this diagonal turns out to be infinite, contradiction.

$\endgroup$
5
  • 1
    $\begingroup$ Yes, I think this is true and should follow from the distributive lattice structure on these tilings (see e.g. Thurston's "Conway's Tiling Groups"). See for example the discussion at: math.stackexchange.com/questions/2626175/…. $\endgroup$ Commented Nov 4, 2022 at 16:56
  • 1
    $\begingroup$ Quoting arxiv.org/abs/1608.07072, referenced in that MSE answer, "A remarkable theorem, which can be deduced from ideas of Thurston [8, 1, 5], says that if $S$ is simply connected, then $F_S$ is connected." Here $S$ is the region being tiled (e.g. the rectangle in your example) and $F_S$ is the flip graph: the graph on tilings where an edge corresponds to your $2 \times 2$ square rotation (usually called a flip). $\endgroup$ Commented Nov 4, 2022 at 17:01
  • 1
    $\begingroup$ The statement il also claimed here without proof. The answer looks like closely related to a proof, if not equivalent. $\endgroup$
    – Wolfgang
    Commented Nov 5, 2022 at 6:30
  • $\begingroup$ @SamHopkins: this is exactly what we need. Now, it is stated in this paper without proof and without reference to an explicit proof. $\endgroup$ Commented Nov 5, 2022 at 6:43
  • 2
    $\begingroup$ Here it seems there is more than one proof. $\endgroup$ Commented Nov 5, 2022 at 10:49

0

You must log in to answer this question.