# Local dimer dynamics in higher dimensions

Ivailo Hartarsky  TU Wien, Faculty of Mathematics and Geoinformation, Wiedner
Hauptstraße 8-10, A-1040 Vienna, Austria,
<EMAIL_ADDRESS>Lyuben Lichev  Institut
Camille Jordan, Univ. Jean Monnet, Saint-Etienne, France, lyuben.lichev@univ-
st-etienne.fr Fabio Toninelli  TU Wien, Faculty of Mathematics and
Geoinformation, Wiedner Hauptstraße 8-10, A-1040 Vienna, Austria,
<EMAIL_ADDRESS>
###### Abstract

We consider local dynamics of the dimer model (perfect matchings) on
hypercubic boxes $[n]^{d}$. These consist of successively switching the dimers
along alternating cycles of prescribed (small) lengths. We study the
connectivity properties of the dimer configuration space equipped with these
transitions. Answering a question of Freire, Klivans, Milet and Saldanha, we
show that in three dimensions any configuration admits an alternating cycle of
length at most 6. We further establish that any configuration on $[n]^{d}$
features order $n^{d-2}$ alternating cycles of length at most $4d-2$. We also
prove that the dynamics of dimer configurations on the unit hypercube of
dimension $d$ is ergodic when switching alternating cycles of length at most
$4d-4$. Finally, in the planar but non-bipartite case, we show that
parallelogram-shaped boxes in the triangular lattice are ergodic for switching
alternating cycles of lengths 4 and 6 only, thus improving a result of Kenyon
and Rémila, which also uses 8-cycles. None of our proofs make reference to
height functions.

MSC2020: 05B50; 05C70; 82C20
Keywords: dimers, dominoes, local dynamics, ergodicity

##  1 Introduction

The dimer model on planar graphs has played a crucial role in statistical
mechanics and probability theory for several reasons: in particular, its
integrability properties related to Kasteleyn’s determinantal or Pfaffian
solution and, in the bipartite case, the emergence of macroscopic shapes,
arctic curves, conformal invariance and Gaussian Free Field height
fluctuations at large scales (see the monographs [Kenyon09, Gorin21] and
references therein). The behaviour of the dimer model in dimension higher than
2, or on planar but non-bipartite graphs, is much less understood, and the
same can be said about the model’s Glauber dynamics. The goal of the present
work is to present new results about (local) dimer Glauber dynamics, either on
$\mathbb{Z}^{d}$ for $d\geq 3$ or on the planar triangular lattice.

The study of Glauber dynamics of the dimer model has a long history and has
proved quite challenging. While it is easy to define local Markov dynamics
with update rule consisting in switching alternating cycles, which ensures
that the uniform measure is stationary and reversible, proving that such
processes are ergodic and quantifying their speed of convergence to
equilibrium is a much more subtle business. In the _planar bipartite case_ ,
the height function [Thurston90] turns out to be extremely helpful: it
provides a natural partial order preserved by the dynamics, an easy proof of
ergodicity and an intuitive “mean curvature motion” heuristic suggesting that,
in many interesting situations, the mixing time $T_{\rm{mix}}$ is of order
$L^{2}$ (in continuous time), with $L$ the diameter of the domain. Under some
conditions, the Glauber dynamics have in fact been proven to be fast mixing
[Luby01, Randall00, Wilson04] and even to satisfy $T_{\rm{mix}}=L^{2+o(1)}$
under suitable restrictions on the domain geometry [Laslier15, Caputo12,
Laslier22].

As soon as the model is either not planar or not bipartite, there is no
canonical definition of height function and the most basic question of proving
that local Glauber dynamics are ergodic, and even that they have no completely
blocked configurations, turn out to be non-trivial. The situation is
particularly unclear for the dimer model on (say, cubic subsets of)
$\mathbb{Z}^{d}$ for $d\geq 3$ where there are no local dynamics that are
known to be ergodic. In fact, the simplest chain whose updates consist in
flipping two parallel dimers fails to be ergodic because of subtle topological
obstructions. We refer to Section 1.2 (as well as to [Chandgotia23]*Sections
1, 3 and 9 and [Milet15]) for a more extensive discussion of conjectures, open
problems and previous partial results, and to Section 1.3 for a precise
statement of our own results. Let us only briefly anticipate here that our
main results include the proof that for local Glauber dynamics on cubic boxes
of $\mathbb{Z}^{d}$, allowing _switching_ (also called moves in [Milet15] and
loop shifts in [Chandgotia23]) along cycles of finite length (suitably
depending on the dimension $d$ only), all connected components of the state
space are at least of size $e^{c(d)n^{d-2}}$, with $n$ the side length of the
cube. For comaprison, it was previously an open question to prove that there
are no components of cardinality $1$. Let us add that the ergodicity question,
besides being crucial for the use of Markov chains as simulation algorithms,
has also attracted interest in the theoretical physics community due to its
connection to the quantum dimer model and to the possible occurrence of
“Hilbert space fragmentation” [Roising23].

Finally, we emphasize that substantial progress in the understanding of the
_equilibrium_ properties of (uniform) dimer configurations in dimension $d\geq
3$ has been made recently. This includes a large deviation principle for the
“flow function” of three-dimensional dimers [Chandgotia23] and the proof of
occurrence of macroscopic loops for the $d\geq 3$ double dimer model
[Quitmann22]. See also [Lammers21, Randall00a, Linde01] for different
generalisations of the dimer model to dimension $d\geq 3$.

###  1.1 Model

Given a graph $G$, a _dimer configuration_ on $G$ is a perfect matching. The
edges in a dimer configuration are called _dimers_. Fix a graph $G$ and a
dimer configuration on $G$. An _alternating cycle_ is a cycle in $G$ of even
length where every second edge is a dimer. A _switching_ of an alternating
cycle is the operation of exchanging the dimer and the non-dimer edges along
the cycle. Note that any switching in a dimer configuration produces another
dimer configuration, see e.g. Figure 1(b).

For a graph $G$, we denote by $\mathcal{D}(G)$ the graph with vertices, given
by the dimer configurations on $G$, where two vertices are connected if there
is an alternating cycle whose switching transforms one of the dimer
configurations into the other. Moreover, for an integer $\ell\geq 2$, we
denote by $\mathcal{D}_{\ell}(G)$ the spanning subgraph of $\mathcal{D}(G)$
where edges correspond to alternating cycles of length at most $2\ell$. We
also say that the space of dimer configurations is _$2\ell$ -ergodic_ (or
simply _ergodic_) if the graph $\mathcal{D}_{\ell}(G)$ is connected. Note that
the superposition of two dimer configurations forms a set of alternating
cycles and double edges, so for any finite graph $G$ and $\ell$ large enough,
$\mathcal{D}_{\ell}(G)$ is necessarily ergodic.

Given a positive integer $n$, we denote by $[n]$ the set $\\{1,\dots,n\\}$.
Given a positive integer $d\geq 1$, we refer to any vector
$\mathbf{n}=(n_{1},\dots,n_{d})$ such that $n_{1},\dots,n_{d}\geq 2$ and the
product $n_{1}\dots n_{d}$ is even as _shape_. For a shape $\mathbf{n}$, the
_$\mathbf{n}$ -box_ $\mathbb{Q}^{d}_{\mathbf{n}}$ is defined as follows. The
graph $\mathbb{Q}_{\mathbf{n}}^{d}$ has vertex set $\prod_{i=1}^{d}[n_{i}]$
and edges between $\mathbf{u}=(u_{1},\ldots,u_{d})$ and
$\mathbf{v}=(v_{1},\ldots,v_{d})$ if there exists $i\in[d]$ such that
$u_{j}=v_{j}$ for all $j\neq i$ and $|u_{i}-v_{i}|=1$. We write
$\mathbb{Q}_{n}^{d}$ for $\mathbb{Q}_{\mathbf{n}}^{d}$ with
$\mathbf{n}=(n,\dots,n)\in\mathbb{Z}^{d}$ and $\mathbb{Q}^{d}$ for the unit
hypercube $\mathbb{Q}_{2}^{d}$. For simplicity, we often identify boxes
$\mathbb{Q}_{\mathbf{n}}^{d}$ with their natural embedding in the
$d$-dimensional Euclidean space.

We further define the triangular lattice $\mathbb{T}$ as the graph with vertex
set $\mathbb{Z}^{2}$ where every vertex $\mathbf{v}$ is adjacent to
$\mathbf{v}+(1,0),\mathbf{v}+(-1,0),\mathbf{v}+(0,1),\mathbf{v}+(0,-1),\mathbf{v}+(1,-1),\mathbf{v}+(-1,1)$.
For positive integers $m,n$ with $mn$ even, we denote by $\mathbb{T}_{m,n}$
the graph induced from $\mathbb{T}$ by the vertex set $[m]\times[n]$. Note
that, while $\mathbb{T}_{m,n}$ is a (rectangular) box in the embedding of
$\mathbb{T}$ chosen above, in the more standard isoradial embedding, these
domains correspond to parallelograms.

We set out to study the ergodicity of
$\mathcal{D}_{\ell}(\mathbb{Q}_{\mathbf{n}}^{d})$ and
$\mathcal{D}_{\ell}(\mathbb{T}_{m,n})$.

###  1.2 Background

Given a planar graph drawn in the plane, a _domain_ is a union of faces (seen
as closed polygons in the plane) of the lattice. Of course, any domain may be
seen as a portion of the lattice with its proper dimer configurations and
cycle-switching dynamics. The ergodicity of simply connected domains in planar
bipartite lattices (with cycle length given by the length of the largest inner
face) is a classical fact and follows directly by considering the associated
height function (see [Saldanha95, Thurston90]). Recently, the ergodicity of
local dynamics on a number of planar lattices was studied by Røising and Zhang
[Roising23], extending an approach of Kenyon and Rémila [Kenyon96]. We note
that the techniques used there do not rely on height functions but use
planarity in a substantial way, and also involve a certain amount of manual
verification.

The main goal of our work is to go beyond the planar case. The most natural
setting in this respect corresponds to studying
$\mathcal{D}_{\ell}(\mathbb{Q}_{\mathbf{n}}^{3})$ for fixed $\ell$ and large
3-dimensional shapes $\mathbf{n}$. It is not hard to check that
$\mathcal{D}_{2}(\mathbb{Q}_{\mathbf{n}}^{3})$ is not connected and even has
isolated vertices e.g. for $\mathbf{n}=(3,3,2)$ (and similarly for
$\mathbf{n}=(n_{1},n_{2},n_{3})$ with $n_{1}$ and $n_{2}$ divisible by 3 and
$n_{3}$ even), see Figure 1(a). This suggests the existence of an invariant
preserved by switching $4$-cycles. One such invariant was noted in
[Freedman11] (also see [Bednik19]), and a much more informative one called the
_twist_ was introduced in [Milet15] and further studied in [Milet15a,
Milet14], thus establishing interesting algebraic, topological and geometric
connections alongside the combinatorial ones.

(a) A configuration in $\mathbb{Q}^{3}_{(3,3,2)}$ with no alternating 4-cycles

(b) Configurations in a domain of $\mathbb{T}$ with no alternating $4$ or
$6$-cycles.

(c) A dimer configuration on $\mathbb{T}_{4,3}$ without alternating 4-cycles.

Figure 1: Example configurations with no short alternating cycles.

This suggests considering $\mathcal{D}_{\ell}(\mathbb{Q}_{\mathbf{n}}^{3})$
for $\ell\geq 3$. Milet and Saldanha [Milet15a] asked whether
$\mathcal{D}_{3}(\mathbb{Q}_{\mathbf{n}}^{3})$ is connected for
$3$-dimensional shapes $\mathbf{n}$. This was reiterated by Freire, Klivans,
Milet and Saldanha in [Freire22, Saldanha21] and very recently by Chandgotia,
Sheffield and Wolfram [Chandgotia23]*Problem 9.1. We promote it to the
following conjecture, which is one of the main motivations behind our work.

######  Conjecture 1.

For all $3$-dimensional shapes $\mathbf{n}$, the graph
$\mathcal{D}_{3}(\mathbb{Q}_{\mathbf{n}}^{3})$ is connected.

Several weaker results in the direction of Conjecture 1 have been obtained.
Firstly, for $\mathbf{n}=(n_{1},n_{2},2)$, $6$-ergodicity was established in
[Milet15]. In [Freire22], Conjecture 1 was proved up to refinement, that is,
repeatedly replacing each dimer in the configuration by a copy of a dimer
configuration on $\mathbb{Q}_{(5,5,10)}$, $\mathbb{Q}_{(5,10,5)}$ or
$\mathbb{Q}_{(10,5,5)}$ with dimers parallel to the original one. In
[Saldanha22], Conjecture 1 was proved for $\mathbf{n}=(n,m,N)$ with $N$ large
enough (depending on $n$ and $m$) and restricting attention to dimer
configurations whose last sufficiently many layers (again, depending on $n$
and $m$) are filled with vertical dimers.

In view of the above, the following question weakening Conjecture 1 was asked
in [Freire22], where it was checked that no small counterexamples exist.

######  Question 2.

Do there exist even $n$ such that $\mathcal{D}_{3}(\mathbb{Q}_{n}^{3})$ has
isolated vertices?

Higher dimensions have been explored even less. Indeed, we are only aware of a
binary invariant for $4$-cycle switchings considered in [Klivans22], where
results similar to those from [Saldanha22] were proved.

###  1.3 Results

In the present work, we prove several results on the connectivity properties
of the graphs $\mathcal{D}_{\ell}(\mathbb{Q}^{d}_{\mathbf{n}})$ and
$\mathcal{D}_{\ell}(\mathbb{T}_{m,n})$. Contrary to previous approaches that
mainly used the algebraic, topological and geometric aspects of the
Milet–Saldanha twist invariant, our arguments are purely combinatorial and
elementary.

Our first result immediately entails a negative answer to Question 2.

######  Theorem 3 (Extraction of a dense $\mathbb{Q}^{d}$).

Let $d\geq 2$ and $\mathbf{n}$ be a $d$-dimensional shape. Then, for any dimer
configuration $D$ on $\mathbb{Q}_{\mathbf{n}}^{d}$, there exists
$\mathbf{x}\in\mathbb{Z}^{d}$ such that the unit cube
$\mathbf{x}+\mathbb{Q}^{d}\subseteq\mathbb{Q}_{\mathbf{n}}^{d}$ contains at
least $2^{d-2}+1$ dimers in $D$.

Indeed, when $d=3$, this yields a unit cube with $3$ dimers, which is readily
checked to contain an alternating cycle of length $4$ or $6$. One can
similarly check that in 4 dimensions, we obtain an alternating cycle of length
at most $8$. We believe that any set of $2^{d-2}+1$ disjoint dimers in
$\mathbb{Q}^{d}$ admits an alternating cycle of length at most $2d$ for any
$d\geq 2$ but have been unable to prove this. Let us emphasise that it is
crucial that $\mathbf{x}+\mathbb{Q}^{d}$ contains $2^{d-2}+1$ dimers and not
less: in fact, one can check that there exist various very different examples
of configurations with $2^{d-2}$ dimers containing no alternating cycle of any
length.

Theorem 3 proves the absence of isolated vertices in
$\mathcal{D}_{3}(\mathbb{Q}_{\mathbf{n}}^{3})$ for all $3$-dimensional shapes
$\mathbf{n}$. At the cost of increasing the value of $\ell$, we are able to
prove much more.

######  Theorem 4 (Degree and component size).

Fix $d\geq 3$ and an even positive integer $n$. The minimum degree of
$\mathcal{D}_{2d-1}(\mathbb{Q}_{n}^{d})$ is at least $n^{d-2}/(320d^{6})$ and
each connected component contains at least $2^{n^{d-2}/(320d^{6})}$ dimer
configurations.

Let us note that we have specialised the result for boxes of equal sides only
for the sake of readability. The bound on the minimum degree is optimal up to
a factor independent of $n$, as shown by the pyramid configuration defined in
Example 15 where alternating cycles of length $\ell$ should stay at distance
at most $\ell$ from the centers of the $(d-2)$-dimensional horizontal
sections, see Figure 2. We further remark that the total number of dimer
configurations on $\mathbb{Q}_{n}^{d}$ is of order $e^{C(d)n^{d}}$ for some
$C(d)>0$ as $n$ grows [Hammersley66].

(a) The dimer configuration on odd sections.

(b) The dimer configuration on even sections.

Figure 2: The pyramid dimer configuration on $\mathbb{Q}_{n}^{3}$ (see Example
15; the parity of a section is determined by the parity of the vertex
$(1,1,\mathbf{v}^{\prime})$). The horizontal sections alternate between the
two 2-dimensional dimer configurations shown above. These contain no vertical
dimers. The only short alternating cycles are around the middle column. Red
dimers are solid, blue ones are dashed.

Next, we focus our attention on unit hypercubes $\mathbb{Q}^{d}$ for which we
can prove stronger results. Firstly, the following improvement of Theorem 4
can be deduced in the same way.

######  Theorem 5 (Degree and component size in $\mathbb{Q}^{d}$).

Fix $d\geq 3$. The minimum degree of $\mathcal{D}_{d-1}(\mathbb{Q}^{d})$ is at
least $2^{d}/d^{4}$ and each connected component contains at least
$2^{2^{d}/d^{4}}$ dimer configurations.

While this result is only interesting for large $d$, at which point the size
of alternating cycles also grows, we emphasise that the size of cycles we
allow is very small compared to the total volume of the hypercube. At the cost
of allowing switching along cycles twice as long, we are able to prove
ergodicity in the following strong form.

######  Theorem 6 (Ergodicity on $\mathbb{Q}^{d}$).

For every $d\geq 2$, the graph $\mathcal{D}_{2d-2}(\mathbb{Q}^{d})$ is
connected and has diameter at most $(d-1)2^{d-1}$.

In view of this bound on the diameter of the dimer configuration space on the
unit hypercube that is almost linear (as a function of the volume of the
hypercube), it is natural to ask whether the diameter of
$\mathcal{D}_{\ell}(\mathbb{Q}_{n}^{d})$ can also be linear in the volume. In
two dimensions, this is not the case since a lower bound of order $n^{3}$
follows by considering the height functions of the two configurations in
Figure 2, while for non-bipartite graphs such as the triangular lattice, the
diameter can be linear in the volume [Kenyon96]. In higher dimensions, the
situation is only clarified by the following result, which also offers a proof
in two dimensions without height functions.

######  Theorem 7 (Diameter lower bound).

For all $d,\ell,n\geq 2$ with $n$ even, the graph
$\mathcal{D}_{\ell}(\mathbb{Q}_{n}^{d})$ has diameter at least

$\frac{n^{d-1}(n^{2}-1)}{6\ell^{2}}.$

Finally, while it is tempting to look for the minimal value of $\ell$ ensuring
ergodicity in each setting, this is a rather sensitive matter. In this
direction, we prove the following result.

######  Theorem 8 (Ergodicity on $\mathbb{T}_{m,n}$).

For all positive integers $m,n$ with $mn$ even, the graph
$\mathcal{D}_{3}(\mathbb{T}_{m,n})$ is connected and has diameter at most
$2mn$.

This should be compared to [Kenyon96] showing an analogous result for
$8$-ergodicity but for any simply connected domain of the triangular lattice.
While there do exist domains for which 8-cycles are necessary (see Figure
1(b)), we show that for boxes, cycles of length 4 and 6 suffice. While there
is a dimer configuration on $\mathbb{T}_{4,3}$ without alternating 4-cycles
(see Figure 1(c)), it remains unclear whether 6-cycles can be avoided for
sufficiently large values of $mn$.

With the exception of Theorems 4 and 5, the above results are shown by
completely different means, thus providing several approaches for further use.
The proofs provided in subsequent sections are therefore completely
independent.

##  2 Extraction of a dense $\mathbb{Q}^{d}$: proof of Theorem 3

In this section, we show that any dimer configuration on
$\mathbb{Q}_{\mathbf{n}}^{d}$ contains a unit hypercube containing at least
$2^{d-2}+1$ dimers. The proof is a simple double counting argument.

###### Proof of Theorem 3.

Fix a dimension $d\geq 2$, a $d$-dimensional shape $\mathbf{n}$ and a dimer
configuration $D$ on $\mathbb{Q}_{\mathbf{n}}^{d}$. We count the couples of a
vertex $\mathbf{u}\in\mathbb{Q}_{\mathbf{n}}^{d}$ and a unit hypercube
$\mathbf{x}+\mathbb{Q}^{d}\subseteq\mathbb{Q}^{d}_{\mathbf{n}}$ containing the
dimer of $\mathbf{u}$ in $D$. We say that a vertex
$\mathbf{x}\in\mathbb{Q}_{\mathbf{n}}^{d}$ is of _type_
$I(\mathbf{x})=\\{i\in[d]:x_{i}\in\\{1,n_{i}\\}\\}$, which indicates in which
coordinates $\mathbf{x}$ is on the boundary of $\mathbb{Q}^{d}_{\mathbf{n}}$.
The type of a dimer $\mathbf{u}\mathbf{v}$ is defined as
$I(\mathbf{u}\mathbf{v})=\\{i\in[d]:u_{i}=v_{i}\in\\{1,n_{i}\\}\\}$ so that
$I(\mathbf{u}\mathbf{v})\subseteq I(\mathbf{u})\cap I(\mathbf{v})$. Then, for
every $i\in I(\mathbf{u}\mathbf{v})$, all unit hypercubes that contain
$\mathbf{u}\mathbf{v}$ contain only vertices whose $i$-th component is either
in the set $\\{1,2\\}$ (if $u_{i}=v_{i}=1$) or in the set
$\\{n_{i}-1,n_{i}\\}$ (if $u_{i}=v_{i}=n_{i}$). One may easily check that
there are exactly $2^{d-|I(\mathbf{u}\mathbf{v})|-1}\geq
2^{d-|I(\mathbf{u})|-1}$ such unit hypercubes.

On the other hand, the number of vertices of type $I\subseteq[d]$ is
$2^{|I|}\prod_{i\in[d]\setminus I}(n_{j}-2)$. Treating separately the corners
of $\mathbb{Q}_{\mathbf{n}}^{d}$, each of which is contained in a single unit
hypercube, we obtain that the number of couples $(\mathbf{u},\mathbf{x})$ as
above is at least

$2^{d}+\sum_{I\subsetneq[d]}2^{d-|I|-1}\times 2^{|I|}\prod_{j\in[d]\setminus
I}(n_{j}-2)=2^{d-1}\left(1+\sum_{I\subseteq[d]}\prod_{i\in[d]\setminus
I}(n_{i}-2)\right)=2^{d-1}\left(1+\prod_{i\in[d]}(n_{i}-1)\right).$

Since there are exactly $\prod_{i\in[d]}(n_{i}-1)$ unit hypercubes and each
dimer is counted twice for every unit hypercube that contains it (once for
each of its endvertices), there has to be a unit hypercube containing at least
$2^{d-2}+1$ dimers, as desired. ∎

##  3 Degree and component size: proof of Theorem 4 and 5

Throughout this section, we fix $d\geq 3$, an even positive integer $n$ and a
dimer configuration $D$ on $\mathbb{Q}^{d}_{n}$. We say that a vertex
$\mathbf{w}\in\mathbb{Q}_{n}^{d}$ is _forbidden_ (by a dimer
$\mathbf{u}\mathbf{v}\in D$) if there exists $i\in[d]$ such that
$u_{j}=v_{j}=w_{j}$ for all $j\in[d]\setminus\\{i\\}$, $\mathbf{u}\mathbf{v}$
is a dimer and $\mathbf{u}\mathbf{w}$ or $\mathbf{v}\mathbf{w}$ is an edge in
$\mathbb{Q}^{d}_{n}$. In other words, the dimer $\mathbf{u}\mathbf{v}$ forbids
$\mathbf{w}$ if $\mathbf{w}$ is a neighbour of $\mathbf{u}$ or $\mathbf{v}$
aligned with $\mathbf{u}\mathbf{v}$. A vertex that is not forbidden is called
_authorised_. Observe that for $n\geq 3$, a dimer containing a vertex on the
boundary of $\mathbb{Q}^{d}_{n}$ (that is, one with less than $2d$ neighbours)
may forbid one or two vertices in $\mathbb{Q}^{d}_{n}$, while all other dimers
forbid two vertices.

We next show that there is a short alternating cycle close to each authorised
vertex.

######  Lemma 9.

Fix an authorised vertex $\mathbf{w}\in\mathbb{Q}_{n}^{d}$. Then, there is an
alternating cycle of length at most $4d-2$ contained in the second
neighbourhood of $\mathbf{w}$ in $\mathbb{Q}^{d}_{n}$. Moreover, if $n=2$,
every vertex in $\mathbb{Q}^{d}$ has an alternating cycle of length at most
$2d-2$ in its second neighbourhood.

###### Proof.

Let $(\mathbf{v}^{i})_{i=1}^{m}$ be the neighbours of the authorised vertex
$\mathbf{w}$ in $\mathbb{Q}^{d}_{n}$ for some $m\in[d,2d]$. Moreover, suppose
without loss of generality that the dimers in the second neighbourhood of
$\mathbf{w}$ are $\mathbf{w}\mathbf{v}^{1}$ and
$(\mathbf{u}^{i}\mathbf{v}^{i})_{i=2}^{m}$.

If $\mathbf{u}^{i}$ is a neighbour of $\mathbf{v}^{1}$ in $\mathbb{Q}^{d}_{n}$
for some $i\in[2,m]$, then
$\mathbf{v}^{1},\mathbf{w},\mathbf{v}^{i},\mathbf{u}^{i}$ is an alternating
cycle of length $4$, as desired. Suppose that none of
$(\mathbf{u}^{i})_{i=2}^{m}$ is a neighbour of $\mathbf{v}^{1}$. Note that
since $\mathbf{w}$ is an authorised vertex, the vectors
$\mathbf{w}-\mathbf{v}^{i}$ and $\mathbf{v}^{i}-\mathbf{u}^{i}$ are orthogonal
for every $i\in[2,m]$, which implies that $\mathbf{u}^{i}$ has exactly two
neighbours among $(\mathbf{v}^{j})_{j=2}^{m}$ in $\mathbb{Q}^{d}_{n}$ (or
otherwise said, vertex $(1,1,0,0,\dots,0)$ has exactly two neighbours in
common with the origin in $\mathbb{Z}^{d}$). Now, consider the graph induced
from $\mathbb{Q}^{d}_{n}$ by the vertices
$\bigcup_{i=2}^{m}\\{\mathbf{u}^{i},\mathbf{v}^{i}\\}$, and orient the dimer
edges from $(\mathbf{v}^{i})_{i=2}^{m}$ to $(\mathbf{u}^{i})_{i=2}^{m}$ and
the other edges from $(\mathbf{u}^{i})_{i=2}^{m}$ to
$(\mathbf{v}^{i})_{i=2}^{m}$. We obtain a digraph on $2m-2$ vertices where
every vertex has out-degree at least 1, and for every (directed) path in this
digraph, exactly one of every two consecutive edges is a dimer. Thus, one may
find an alternating cycle of length at most $2m-2\leq 4d-2$ by starting from
any vertex and making steps in the digraph until the first time a vertex is
visited twice.

It remains to notice that when $n=2$, every vertex is authorised and has
degree $d$ in $\mathbb{Q}^{d}$. ∎

Lemma 9 implies that if there are many authorised vertices in a dimer
configuration on $\mathbb{Q}^{d}_{n}$, then there must be many alternating
cycles in that configuration. The next lemma shows that there must be many
authorised vertices.

######  Lemma 10.

Fix $n\geq 4$. Then, there are at least $n^{d-2}/(20d^{2})$ authorised
vertices.

###### Proof.

By the pigeonhole principle there exists $j\in[d]$ such that at least
$n^{d}/(2d)$ of all dimers differ in their $j$-th coordinate. We assume that
$j=d$ without loss of generality. For $\mathbf{v}\in\mathbb{Q}_{n}^{d}$, the
_level_ of $\mathbf{v}$ is $v_{d}\in[n]$. For every $i\in[2,n]$, denote by
$k_{i}$ the number of dimers $\mathbf{u}\mathbf{v}$ with $u_{d}=i-1$ and
$v_{d}=i$. In particular,

$\sum_{i=2}^{n}k_{i}\geq\frac{n^{d}}{2d}.$ (1)

For convenience of notation, we extend the sequence by setting
$k_{0}=k_{1}=k_{n+1}=k_{n+2}=0$.

For every $i\in[n]$, denote by $N_{i}$ the number of vertices on level $i$
that are either forbidden by at least two dimers or authorised. To begin with,
we show that the sum of $(N_{i})_{i=1}^{n}$ is at most twice the number of all
authorised vertices. For every $j\in\\{0,\ldots,2d\\}$, denote by $F_{j}$ the
number of vertices forbidden by exactly $j$ dimers. Since each of the
$n^{d}/2$ dimers in the configuration forbids at most two vertices, we have

$F_{1}-2F_{0}+2\sum_{i=1}^{n}N_{i}=F_{1}+\sum_{j=2}^{2d}2F_{j}\leq\sum_{j=1}^{2d}jF_{j}\leq
n^{d}=\sum_{j=0}^{2d}F_{j}=F_{1}+\sum_{i=1}^{n}N_{i},$

which implies that $\sum_{i=1}^{n}N_{i}\leq 2F_{0}$. In particular, if
$\sum_{i=1}^{n}N_{i}\geq n^{d-2}/(10d^{2})$, then the proof is completed.

We focus on the analysis of the sequence $(N_{i})_{i=1}^{n}$. Suppose that
$\sum_{i=1}^{n}N_{i}<n^{d-2}/(10d^{2})$. Observe that for every $i\in[n]$,
every dimer $\mathbf{u}\mathbf{v}$ satisfying $u_{d}+1=v_{d}\in\\{i-1,i+2\\}$
forbids one vertex on level $i$ but has no vertex on level $i$ itself.
Conversely, every dimer $\mathbf{u}\mathbf{v}$ satisfying
$u_{d}+1=v_{d}\in\\{i,i+1\\}$ contains one vertex on level $i$ while
forbidding none. Moreover, the dimers with two vertices on level $i$ forbid
one or two vertices on that level. Let $s_{i}$ be the number of such dimers
forbidding one vertex on level $i$, and $t_{i}$ be the number of such dimers
forbidding two vertices on level $i$. Then, the total number of forbidden
vertices on level $i$ counted with multiplicities (that is, a vertex forbidden
by $j$ dimers is counted $j$ times) is $s_{i}+2t_{i}+k_{i-1}+k_{i+2}$. Note
that this expression may be rewritten as

$\displaystyle 2(s_{i}+t_{i})+k_{i-1}+k_{i+2}-s_{i}={}$
$\displaystyle(n^{d-1}-k_{i}-k_{i+1})+k_{i-1}+k_{i+2}-s_{i}$
$\displaystyle={}$ $\displaystyle
n^{d-1}-(s_{i}-k_{i-1}+k_{i}+k_{i+1}-k_{i+2}).$ (2)

As a consequence, the total number of authorised vertices is bounded from
below by

$n^{d}-\sum_{i=1}^{n}(n^{d-1}-(s_{i}-k_{i-1}+k_{i}+k_{i+1}-k_{i+2}))=k_{2}+k_{n}+\sum_{i=1}^{n}s_{i}.$

Hence, if $\sum_{i=1}^{n}s_{i}\geq n^{d-2}/(20d^{2})$, then the proof is
completed.

Suppose that $\sum_{i=1}^{n}s_{i}<n^{d-2}/(20d^{2})$. Since the minimum of (2)
and $n^{d-1}$ is an upper bound on the number of vertices on level $i$
forbidden by exactly one dimer and no vertex is forbidden more than $2d$
times, we have that for every $i\in[n]$,

$2dN_{i}\geq|s_{i}-k_{i-1}+k_{i}+k_{i+1}-k_{i+2}|.$

In particular, combining this with the triangle inequality implies that for
every $i\in[n]$,

$||k_{i+2}-k_{i+1}|-|k_{i}-k_{i-1}||\leq|k_{i-1}-k_{i}-k_{i+1}+k_{i+2}|\leq
s_{i}+2dN_{i}.$ (3)

Now, for every positive integer $m\leq n/2$, summing (3) for
$i\in\\{2,4,\ldots,2m-2\\}$ and applying the triangle inequality yields

$||k_{2m}-k_{2m-1}|-k_{2}|=||k_{2m}-k_{2m-1}|-|k_{2}-k_{1}||\leq\sum_{i=1}^{m-1}(s_{2i}+2dN_{2i})<\frac{3n^{d-2}}{10d},$
(4)

while summing over $i\in\\{2m-1,2m+1,\ldots,n-1\\}$ instead yields

$|k_{n}-|k_{2m-1}-k_{2m-2}||=||k_{n+1}-k_{n}|-|k_{2m-1}-k_{2m-2}||\leq\sum_{i=m}^{n/2}(s_{2i-1}+2dN_{2i-1})<\frac{3n^{d-2}}{10d}.$
(5)

To finish the proof, we show that $k_{2}\geq n^{d-2}/(10d)$ or $k_{n}\geq
n^{d-2}/(10d)$. Indeed, in this case, there are at least $n^{d-2}/(10d)$
dimers that forbid only one vertex, which is a lower bound on the number of
authorised vertices. Suppose for a contradiction that both
$k_{2}<n^{d-2}/(10d)$ and $k_{n}<n^{d-2}/(10d)$. Then, by (4) and (5) we have
that for every $i\in[n]$, $|k_{i}-k_{i-1}|\leq 4n^{d-2}/(10d)$. At the same
time, by (1) there is $i\in[2,n]$ such that $k_{i}\geq n^{d-1}/(2d)$. Thus,
both $k_{2}$ and $k_{n}$ must be at least $n^{d-1}/(2d)-n\times
4n^{d-2}/(10d)=n^{d-2}/(10d)$, which leads to a contradiction and finishes the
proof. ∎

###### Proof of Theorem 4.

By Lemma 10 there are at least $n^{d-2}/(20d^{2})$ authorised vertices in $D$.
Moreover, since for any vertex $\mathbf{v}\in\mathbb{Q}^{d}_{n}$, the number
of vertices at (graph) distance at most 4 from $\mathbf{v}$ is at most
$1+2d+2d(2d-1)+2d(2d-1)^{2}+2d(2d-1)^{3}<(2d)^{4}$, we may find
$n^{d-2}/(320d^{6})$ authorised vertices at distance at least 5 from each
other in $\mathbb{Q}^{d}_{n}$. Then, the alternating cycles in the second
neighbourhoods of these vertices ensured by Lemma 9 are disjoint, and
therefore may be switched independently of each other, thus proving the
desired result. ∎

###### Proof of Theorem 5.

Since for any vertex $\mathbf{v}\in\mathbb{Q}^{d}$, the number of vertices at
(graph) distance at most 4 from $\mathbf{v}$ is at most
$1+d+d(d-1)+d(d-1)^{2}+d(d-1)^{3}<d^{4}$, we may find $2^{d}/d^{4}$ vertices
at distance at least 5 from each other in $\mathbb{Q}^{d}$. Then, the
alternating cycles in the second neighbourhoods of these vertices ensured by
Lemma 9 are disjoint, and therefore may be switched independently of each
other, thus proving the desired result. ∎

##  4 Ergodicity of the high-dimensional hypercube: proof of Theorem 6

First, let us briefly outline the proof strategy. Let $Q_{1}$ (resp. $Q_{2}$)
be the hypercube containing all vertices whose last coordinate is 1 (resp. 2),
and call an edge (or a dimer) in $\mathbb{Q}^{d}$ _crossing_ if it contains
one vertex in $Q_{1}$ and one vertex in $Q_{2}$. For any given $d\geq 2$, we
fix a dimer configuration on $\mathbb{Q}^{d}$ and iteratively decrease the
number of crossing edges until none are left so that we can apply induction on
$d$. At each step, the idea is to find an alternating cycle of length at most
$4d-4$ in which all edges between $Q_{1}$ and $Q_{2}$ are dimers. To do this,
we combine several technical lemmas related to the expansion properties of the
hypercube with the analysis of a suitable exploration procedure of $Q_{1}$ and
$Q_{2}$ along the alternating cycles in $\mathbb{Q}^{d}$ that do not use
crossing edges which are not dimers.

We now turn to the details. For a set $A\subseteq\mathbb{Q}^{d}$, we denote by
$\partial A$ the set of vertices at (graph) distance 1 from $A$ in
$\mathbb{Q}^{d}$. The next result is a version of a classical theorem of
Harper [Harper66] (see also [Frankl81, Katona75, Keevash20]).

######  Theorem 11 ([Harper66], or also Lemma 5 and Theorem 2 in [Katona75]).

Fix positive integers $d$ and $a<2^{d}$. Then, there exists a unique choice of
integers $1\leq t\leq k+1\leq d$ and $t\leq a_{t}<\dots<a_{k}<d$ such that

$a=\sum_{j=k+1}^{d}\binom{d}{j}+\sum_{i=t}^{k}\binom{a_{i}}{i}.$

Moreover,

$\min\left\\{|A\cup\partial
A|:A\subseteq[2]^{d},|A|=a\right\\}=\phi_{d}(a):=\sum_{j=k}^{d}\binom{d}{j}+\sum_{i=t}^{k}\binom{a_{i}}{i-1}.$

The same holds trivially with $\phi_{d}(0):=0$ and $\phi_{d}(2^{d}):=2^{d}$.

While a direct application of Theorem 11 would be inappropriate in our
setting, it becomes a useful tool in combination with the following lemma.
Call a vertex in $\mathbb{Q}^{d}$ _even_ if the sum of its coordinates is
even, and _odd_ otherwise. We also say that a subset of vertices of
$\mathbb{Q}^{d}$ is even (resp. odd) if it contains only even (resp. odd)
vertices.

######  Lemma 12.

Fix an integer $d\geq 2$ and an even set $A\subseteq\mathbb{Q}^{d}$. Then,

$|\partial A|\geq\min\left\\{|B\cup\partial
B|:B\subseteq\mathbb{Q}^{d-1},\,|B|=|A|\right\\}.$

###### Proof.

Define the map
$\pi:\mathbb{Q}^{d}\to\mathbb{Q}^{d-1}:(v_{1},\ldots,v_{d})\mapsto(v_{1},\ldots,v_{d-1})$
and consider a vertex $\mathbf{u}$ in the first neighbourhood of $\pi(A)$ in
$\mathbb{Q}^{d-1}$. If $\mathbf{u}\in\pi(A)$, then there are two distinct
vertices $\mathbf{u}^{1},\mathbf{u}^{2}\in\mathbb{Q}^{d}$ with
$\pi(\mathbf{u}^{1})=\pi(\mathbf{u}^{2})=\mathbf{u}$ and $\mathbf{u}^{2}\in
A$. Thus, $\mathbf{u}$ is the image of the odd vertex
$\mathbf{u}^{1}\in\partial A$. Moreover, if $\mathbf{u}\in\partial\,\pi(A)$,
then there is a vertex $\mathbf{v}\in A$ such that $\pi(\mathbf{v})$ is a
neighbour of $\mathbf{u}$. Thus, $\mathbf{u}$ is the image of a neighbour of
$\mathbf{v}$ under $\pi$, which is an odd vertex in $\partial A$. Combining
the two observations above shows that $|\partial
A|\geq|\pi(A)\cup\partial\,\pi(A)|$, which finishes the proof. ∎

Fix a dimer configuration $D$ in $\mathbb{Q}^{d}$, and suppose that
$\mathbf{v}$ is an even vertex in $Q_{1}$ contained in a crossing dimer. We
define the graph $\Gamma$ with vertex set $[2]^{d}$ and edge set $E(Q_{1})\cup
E(Q_{2})\cup D$ where $E(G)$ denotes the edge set of a graph $G$. In
particular, $D$ may naturally be seen as a dimer configuration on $\Gamma$.

For every integer $k\geq 0$, denote by $E_{k}$ (resp. $O_{k}$) the set of even
(resp. odd) vertices that may be reached from $\mathbf{v}$ by following an
alternating path in $\Gamma$ of length at most $2k$ (resp. $2k+1$) starting
with a non-dimer edge. In particular, $E_{0}=\\{\mathbf{v}\\}$ and
$O_{0}=Q_{1}\cap\partial\\{\mathbf{v}\\}$. Also, we define $E_{k,i}=E_{k}\cap
Q_{i}$ for $i\in[2]$. Note that for every integer $k\geq 0$,

$|E_{k+1}|\geq|O_{k}|\geq|\partial E_{k,1}\cap Q_{1}|+|\partial E_{k,2}\cap
Q_{2}|.$ (6)

The following lemma is a preliminary technical result.

######  Lemma 13.

Fix $d\geq 1$ and $k\in[0,d]$, and let $\phi=\phi_{d}$ from Theorem 11. Let
$l_{1},l_{2}\in[2^{d}]$ and $l=l_{1}+l_{2}$.

  1. 1.

If $l\leq 2^{d}$, then $\phi(l_{1})+\phi(l_{2})\geq\phi(l)$.

  2. 2.

If $l>2^{d}$, then $\phi(l_{1})+\phi(l_{2})\geq 2^{d}+\phi(l-2^{d})$.

###### Proof.

We prove both statements simultaneously. If some of $l_{1}$ and $l_{2}$ is
$2^{d}$, there is nothing to prove. Without loss of generality, suppose that
$1\leq l_{1}\leq l_{2}\leq 2^{d}-1$. Let $X_{1}$ and $X_{2}$ be two subsets of
$\mathbb{Q}^{d}$ with $|X_{1}|=l_{1}$, $|X_{2}|=l_{2}$, $|X_{1}\cup\partial
X_{1}|=\phi(l_{1})$, $|X_{2}\cup\partial X_{2}|=\phi(l_{2})$ and
$X_{1}\not\subseteq X_{2}$. Define $Y_{1}=X_{1}\cup X_{2}$ and
$Y_{2}=X_{1}\cap X_{2}$. We claim that

$|Y_{1}\cup\partial Y_{1}|+|Y_{2}\cup\partial Y_{2}|\leq|X_{1}\cup\partial
X_{1}|+|X_{2}\cup\partial X_{2}|.$ (7)

Indeed, let $\mathbf{w}\in Y_{1}\cup\partial Y_{1}$. Then, $\mathbf{w}$
belongs to at least one of $X_{1}\cup\partial X_{1}$ and $X_{2}\cup\partial
X_{2}$. Moreover, if $\mathbf{w}$ also belongs to $Y_{2}\cup\partial Y_{2}$,
then $\mathbf{w}$ belongs to both $X_{1}\cup\partial X_{1}$ and
$X_{2}\cup\partial X_{2}$, thus showing (7) after summation over all vertices
in $\mathbb{Q}^{d}$.

In particular, this shows that for every pair of integers $1\leq l_{1}\leq
l_{2}\leq 2^{d}-1$ there are integers $m_{1},m_{2}$ such that $0\leq
m_{1}<l_{1}$, $l_{2}<m_{2}\leq 2^{d}$ and $m_{1}+m_{2}=l_{1}+l_{2}$ such that
$\phi(m_{1})+\phi(m_{2})\leq\phi(l_{1})+\phi(l_{2})$. Iterating this
observation finishes the proof of both points. ∎

Now, we define the sequences $(a_{k})_{k\geq 0}$ and $(b_{k})_{k\geq 0}$ by
setting $b_{0}=2^{d-2}+a_{0}=2^{d-2}+1$, and for every integer $k\geq 0$,
$a_{k+1}$ (resp. $b_{k+1}$) is the minimum of $|\partial X_{1}\cap
Q_{1}|+|\partial X_{2}\cap Q_{2}|$ over all even sets $X_{1}\subseteq Q_{1}$
and $X_{2}\subseteq Q_{2}$ such that $|X_{1}|+|X_{2}|=a_{k}$ (resp.
$|X_{1}|+|X_{2}|=b_{k}$). Note that by (6), for every integer $k\geq 0$,
$|E_{k}|\geq a_{k}$, and if $|E_{m}|\geq b_{0}$ for some $m$, then for every
integer $k\geq 0$, $|E_{k+m}|\geq b_{k}$.

######  Corollary 14.

We have $a_{d-2}=2^{d-2}$ and $b_{d-2}=2^{d-1}$.

###### Proof.

If $d=2$, the statement is trivial. Suppose that $d\geq 3$. We show by
induction that for every integer $k\in[0,d-2]$,
$\min(a_{k},b_{k}-2^{d-2})\geq\sum_{j=d-2-k}^{d-2}\tbinom{d-2}{j}$. The proof
for $b_{k}-2^{d-2}$ being identical, we only prove the inequality for $a_{k}$.
The statement is trivially satisfied for $k=0$. Suppose that for some
$k\in[d-2]$, the statement holds for $k-1$. Fix even sets $X_{1}\subseteq
Q_{1}$ and $X_{2}\subseteq Q_{2}$ of size resp. $l_{1}$ and $l_{2}$ such that
$l=l_{1}+l_{2}=\sum_{j=d-1-k}^{d-2}\tbinom{d-2}{j}\leq a_{k-1}$. Denoting
$\phi=\phi_{d-2}$ from Theorem 11, and applying Theorem 11 with $d-2$ instead
of $d$ and Lemma 12 with $d-1$ instead of $d$, we obtain that

$|\partial X_{1}\cap Q_{1}|\geq\phi(l_{1})\quad\text{and}\quad|\partial
X_{2}\cap Q_{2}|\geq\phi(l_{2}).$ (8)

Thus, Lemma 13 shows that

$|\partial X_{1}\cap Q_{1}|+|\partial X_{2}\cap
Q_{2}|\geq\phi(l_{1})+\phi(l_{2})\geq\phi(l)=\sum_{j=d-2-k}^{d-2}\binom{d-2}{j},$

which completes the induction. ∎

###### Proof of Theorem 6.

Fix an integer $d\geq 2$ and any dimer configuration $D$ on $\mathbb{Q}^{d}$.
We show that by switching along alternating cycles of length at most $4d-4$,
we can reach the configuration where every dimer $\mathbf{u}\mathbf{v}$
satisfies that $u_{1}\neq v_{1}$, that is, all dimers are parallel to the
first dimension.

We show this by induction on the dimension. The base case is clear. Fix an
integer $d\geq 3$ and suppose that the statement holds for $d-1$. If $D$
contains no crossing dimers, then it consists of a dimer configuration on
$Q_{1}$ and a dimer configuration on $Q_{2}$. Then, the conclusion follows
from the induction hypothesis for $d-1$.

Now, suppose that $D$ contains a crossing dimer. Fix an even vertex
$\mathbf{v}\in Q_{1}$ contained in a crossing dimer. We show that
$|E_{2d-3}|=2^{d-1}$. On the one hand, by Corollary 14, $E_{d-2}$ has size at
least $2^{d-2}$. If the inequality is strict, then $|E_{d-2}|\geq b_{0}$ and
consequently $|E_{2(d-2)}|\geq b_{d-2}=2^{d-1}$.

Suppose that $|E_{d-2}|=2^{d-2}$. We show that $|O_{d-2}|\geq 2^{d-2}+1$. If
$E_{d-2,1}$ and $E_{d-2,2}$ are both non-empty, we show that the sizes of the
vertex boundaries of both $E_{d-2,1}$ in $Q_{1}$ and of $E_{d-2,2}$ in $Q_{2}$
must be resp. (strictly) larger than $E_{d-2,1}$ and $E_{d-2,2}$. Indeed, for
$i\in[2]$, the number of edges between $E_{d-2,i}$ and its vertex boundary (in
$Q_{i}$) is $(d-1)|E_{d-2,i}|$, and at the same time this number is at most
$(d-1)|\partial E_{d-2,i}\cap Q_{i}|$. Moreover, equality holds only if
$\partial E_{d-2,i}\cap Q_{i}$ is not adjacent to any vertex outside
$E_{d-2,i}$ in $Q_{i}$, which may only happen when $E_{d-2,i}$ contains all
even vertices in $Q_{i}$, which in our case shows that $|\partial
E_{d-2,i}\cap Q_{i}|>|E_{d-2,i}|$. Now, if $E_{d-2,2}=\varnothing$, say, then
$E_{d-2}$ must contain all even vertices in $Q_{1}$. However, as there is a
crossing dimer with an even vertex in $Q_{1}$, there is also one with an odd
vertex in $Q_{1}$ and therefore in $O_{d-2}$. Hence,
$|E_{d-1,1}|\geq|E_{d-2,1}|=2^{d-2}$ and $E_{d-1,2}\neq\varnothing$, so
$|E_{d-1}|\geq 2^{d-2}+1$ and an application of Corollary 14 shows that
$|E_{2d-3}|\geq b_{d-2}=2^{d-1}$.

Let $\mathbf{v}^{\prime}$ be the odd vertex of the crossing dimer containing
$\mathbf{v}$. Since $E_{2d-3}$ contains all even vertices in $\mathbb{Q}^{d}$,
it contains a neighbour of $\mathbf{v}^{\prime}$ in $Q_{2}$, so
$\mathbf{v}^{\prime}\in O_{2d-3}$. Hence, there is an alternating cycle in
$\Gamma$ of length at most $4d-4$ containing the dimer
$\mathbf{v}\mathbf{v}^{\prime}$, whose switching decreases the number of
crossing dimers. Iterating the above approach leaves no crossing dimers
eventually, and thus finishes the proof of the first point.

For the second step, note that every switching decreases the number of
crossing dimers by at least two, so $2^{d-2}$ steps are sufficient to make all
crossing dimers (in a fixed dimension) disappear. Since the induction above
consists of $d-1$ steps, the distance (in
$\mathcal{D}_{2d-2}(\mathbb{Q}^{d})$) from any dimer configuration $D$ to the
configuration where all dimers are parallel to the first dimension is at most
$(d-1)2^{d-2}$, and therefore the diameter of
$\mathcal{D}_{2d-2}(\mathbb{Q}^{d})$ is at most twice as large. ∎

##  5 Diameter lower bound: proof of Theorem 7

For this section we fix $n$ even and $\ell,d\geq 2$. As above, we call a site
$\mathbf{v}\in\mathbb{Q}_{n}^{d}$ _even_ if $\sum_{i\in[d]}v_{i}$ is even and
_odd_ otherwise. Given a dimer configuration $D$, we define a colouring of the
vertices of $\mathbb{Q}_{n}^{d}$ in two colours (red and blue) as follows. Let
$\mathbf{u}\mathbf{v}\in D$ be a dimer with $\mathbf{u}$ odd and $\mathbf{v}$
even. Let $i\in[d]$ be such that $|u_{i}-v_{i}|=1$. We colour both
$\mathbf{u}$ and $\mathbf{v}$ _red_ if $u_{i}-v_{i}=1$, and _blue_ if
$u_{i}-v_{i}=-1$.

######  Example 15 (Pyramid configuration).

As an example, let us consider the _pyramid configuration_ of Figure 2 defined
formally as follows. For each $\mathbf{v}^{\prime}\in\mathbb{Q}_{n}^{d-2}$ and
even $\mathbf{v}\in\mathbb{Q}_{n}^{d}$ such that
$\mathbf{v}=(v_{1},v_{2},\mathbf{v}^{\prime})$, the second vertex in the dimer
of $\mathbf{v}$ is:

$\begin{cases}(v_{1}+1,v_{2},\mathbf{v}^{\prime})&\text{if }v_{1}<v_{2}\text{
and }v_{1}\geq n+1-v_{2},\\\ (v_{1},v_{2}+1,\mathbf{v}^{\prime})&\text{if
}v_{1}\leq v_{2}\text{ and }v_{1}<n+1-v_{2},\\\
(v_{1}-1,v_{2},\mathbf{v}^{\prime})&\text{if }v_{1}>v_{2}\text{ and }v_{1}\leq
n+1-v_{2},\\\ (v_{1},v_{2}-1,\mathbf{v}^{\prime})&\text{if }v_{1}\geq
v_{2}\text{ and }v_{1}>n+1-v_{2}.\end{cases}$

In terms of colouring, the dimers corresponding to the former two cases are
red, while the remaining ones are blue. In particular, all sites
$\mathbf{u}\in\mathbb{Q}_{n}^{d}$ with $u_{1}<u_{2}$ are red, while those with
$u_{1}>u_{2}$ are blue.

Theorem 7 will follow easily from Example 15 and the following observation.

######  Lemma 16.

For any dimer configuration on $\mathbb{Q}_{n}^{d}$ there are exactly
$n^{d}/2$ red vertices.

###### Proof.

Fix $i\in[d]$ and $j\in[n]$. Consider the dimers $\mathbf{u}\mathbf{v}$ such
that $u_{i}=j$ and $v_{i}=j+1$. Since the numbers of even and odd sites
$\mathbf{w}$ with $w_{i}\leq j$ are equal, the number of such dimers with
$\mathbf{u}$ even is equal to the number of such dimers with $\mathbf{u}$ odd.
Since these two types of dimers have different colours (red and blue,
respectively) and each dimer is considered for exactly one choice of $(i,j)$,
the result follows. ∎

###### Proof of Theorem 7.

It is clear that switching a cycle cannot modify the colours of vertices
outside the cycle. Therefore, by Lemma 16, switching any cycle can only alter
the colours of the sites within the cycle without changing the amount of sites
of either colour. Consider the pyramid dimer configuration $D$ from Example 15
and its inverse $\bar{D}$ obtained by using the configuration in Figure 2(a)
on even sections and Figure 2(b) on odd ones instead, which also leads to
exchanging the two colours. Thus, all sites $\mathbf{u}\in\mathbb{Q}_{n}^{d}$
with $u_{1}<u_{2}$ are red in $D$ and blue in $\bar{D}$. Among these sites,
for each $i\in[n-1]$, there are $(n-i)n^{d-2}$ at distance $i$ from the
complement of this set. Since each switching moves at most $\ell$ red sites at
graph distance at most $\ell$, in order to reach $\bar{D}$ from $D$, we need
to switch at least

$\frac{n^{d-2}}{\ell^{2}}\sum_{i=1}^{n-1}(n-i)i=\frac{n^{d-1}(n^{2}-1)}{6\ell^{2}}$

alternating cycles. ∎

##  6 Ergodicity on $\mathbb{T}_{m,n}$: proof of Theorem 8

In this section, we fix positive integers $m,n$ with $m$ even. The proof of
Theorem 8 proceeds by induction by showing that, starting with any dimer
configuration on $\mathbb{T}_{m,n}$, we can make all dimers on the lower
boundary horizontal. Thereby, one can directly apply the induction hypothesis
to the remaining box $(0,1)+\mathbb{T}_{m,n-1}$. The base of the induction are
the cases $n\in\\{1,2\\}$. The first one is trivial (there is one dimer
configuration), and the second one boils down to switching 4-cycles on
$\mathbb{Q}_{(m,2)}^{2}$ (which is easily seen to be ergodic with diameter
$m-1$) due to absence of diagonal dimers. We may therefore assume that $n\geq
3$.

$\mathbf{x}$$\mathbf{y}$

$\mathbf{x}$$\mathbf{y}$

$\mathbf{x}$$\mathbf{y}$

$\mathbf{x}$$\mathbf{y}$$\mathbf{z}$

$\mathbf{x}$$\mathbf{y}$$\mathbf{z}$

$\mathbf{x}$$\mathbf{y}$$\mathbf{z}$

Figure 3: Illustration of Case 1 of the proof of Theorem 8.

We proceed by a further induction. Let $x\in[m/2]$ be maximal such that
$(2y-1,1),(2y,1)$ is a dimer in the present configuration for all $y\in[x]$.
If $x=m/2$, we are done. Otherwise, we consider two cases for the other end
$\mathbf{x}$ of the dimer containing $(2x+1,1)$.

#### Case 1

Assume $\mathbf{x}=(2x+1,2)$ (see Figure 3 for an illustration). Let
$\mathbf{y}$ be the other end of the dimer of $(2x+2,2)$. If
$\mathbf{y}=(2x+2,1)$, we are done after switching the 4-cycle
$(2x+1,1),(2x+1,2),(2x+2,2),(2x+2,1)$. We assume this is not the case, so
necessarily $(2x+2,1),(2x+3,1)$ is a dimer. If $\mathbf{y}=(2x+3,2)$, then
switching the 4-cycle $(2x+2,1),(2x+3,1),(2x+3,2),(2x+2,2)$ brings us to the
previous case, so we are done. If $\mathbf{y}=(2x+1,3)$, then we are done by
switching the 6-cycle $(2x+1,1),(2x+2,1),(2x+3,1),(2x+2,2),(2x+1,3),(2x+1,2)$.

We may therefore assume that $\mathbf{y}=(2x+2,3)$, and note that it suffices
to move this dimer to $(2x+2,2),(2x+2,3)$ since all other cases were already
dealt with. Let $\mathbf{z}$ be the other end of the dimer of $(2x+3,2)$. If
$\mathbf{z}=(2x+3,3)$, it suffices to switch the 4-cycle
$(2x+2,2),(2x+3,2),(2x+3,3),(2x+2,3)$. If $\mathbf{z}=(2x+4,1)$, it suffices
to switch the 6-cycle $(2x+2,1),(2x+3,1),(2x+4,1),(2x+3,2),(2x+2,3),(2x+2,2)$.
Finally, it remains to consider the case $\mathbf{z}=(2x+4,2)$, which entails
that $(2x+4,1),(2x+5,1)$ is a dimer. Then, we can switch the 4-cycle
$(2x+4,1),(2x+5,1),(2x+4,2),(2x+3,2)$, returning to the previous case.

$\mathbf{x}$$\mathbf{y}$

$\mathbf{x}$$\mathbf{y}$

$\mathbf{x}$$\mathbf{y}$

$\mathbf{x}$$\mathbf{y}$$\mathbf{z}$

$\mathbf{x}$$\mathbf{y}$$\mathbf{z}$

$\mathbf{x}$$\mathbf{y}$$\mathbf{z}$

Figure 4: Illustration of Case 2 of the proof of Theorem 8.

#### Case 2

Assume $\mathbf{x}=(2x,2)$ (see Figure 4 for an illustration). Let
$\mathbf{y}$ be the other end of the dimer of $(2x+1,2)$. If
$\mathbf{y}=(2x,3)$, then switching the 4-cycle
$(2x+1,2),(2x,3),(2x,2),(2x+1,1)$ brings us back to Case 1. If
$\mathbf{y}=(2x+2,1)$, then we are done by switching the 4-cycle
$(2x+1,1),(2x+2,1),(2x+1,2),(2x,2)$. If $\mathbf{y}=(2x+2,2)$, then
$(2x+2,1),(2x+3,1)$ has to be a dimer and switching the 4-cycle
$(2x+2,1),(2x+3,1),(2x+2,2),(2x+1,2)$ returns us to the previous case.

We may therefore assume that $\mathbf{y}=(2x+1,3)$ and it suffices to move
this dimer to $(2x+1,2),(2x+2,2)$. Let $\mathbf{z}$ be the other end of the
dimer of $(2x+2,2)$. If $\mathbf{z}\in\\{(2x+2,1),(2x+2,3)\\}$, this forms a
4-cycle with $(2x+1,2),(2x+1,3)$ and we are done. It therefore remains that
$\mathbf{z}=(2x+3,2)$, which forces $(2x+2,1),(2x+3,1)$ to be a dimer, and
switching the 4-cycle formed by these two dimers returns us to the previous
case.

This completes the induction as well as the proof of the first statement in
Theorem 8. For the second statement, note that we switch at most 4 alternating
cycles in the process of making the dimer at $(2x+1,1)$ horizontal.

######  Remark 17.

Let us note that the proof entails that the minimum degree of
$\mathcal{D}_{6}(\mathbb{T}_{m,n})$ is at least linear in the semi-perimeter
$m+n$. In contrast, the minimum degree of $\mathcal{D}_{8}(\mathbb{T}_{m,n})$
can be shown to be of order $mn$ since there is an alternating cycle of length
at most 8 within the third neighbourhood of each vertex. We also observe that
“sufficiently regular” domains such as triangles or hexagons with even number
of vertices can be treated along the lines of Theorem 8.

## Acknowledgements

This work was supported by the Austrian Science Fund (FWF): P35428-N. We thank
Scott Sheffield and Catherine Wolfram for suggesting the topic to us, and
Marcin Lis for several interesting discussions.

## References


* [LS94] Pierre Lochak and Leila Schneps, _The Grothendieck-Teichmüller group and automorphisms of braid groups_ , The Grothendieck theory of dessins d’enfants (Luminy, 1993), London Math. Soc. Lecture Note Ser., vol. 200, Cambridge Univ. Press, Cambridge, 1994, pp. 323–358. MR 1305403
  * [Mar08] Martin Markl, _Operads and PROPs_ , Handbook of algebra. Vol. 5, Handb. Algebr., vol. 5, Elsevier/North-Holland, Amsterdam, 2008, pp. 87–140. MR 2523450
  * [Moe10] Ieke Moerdijk, _Lectures on dendroidal sets_ , Simplicial methods for operads and algebraic geometry, Adv. Courses Math. CRM Barcelona, Birkhäuser/Springer Basel AG, Basel, 2010, Notes written by Javier J. Gutiérrez, pp. 1–118. MR 2778589
  * [MW07] Ieke Moerdijk and Ittay Weiss, _Dendroidal sets_ , Algebr. Geom. Topol. 7 (2007), 1441–1470. MR 2366165
  * [MW09] I. Moerdijk and I. Weiss, _On inner Kan complexes in the category of dendroidal sets_ , Adv. Math. 221 (2009), no. 2, 343–389. MR 2508925
  * [Nak97] Hiroaki Nakamura, _Galois rigidity of profinite fundamental groups [translation of Sūgaku 47 (1995), no. 1, 1–17; MR1362515 (98d:14027)]_, vol. 10, 1997, Sugaku Expositions, pp. 195–215. MR 1600655
  * [NS00] Hiroaki Nakamura and Leila Schneps, _On a subgroup of the Grothendieck-Teichmüller group acting on the tower of profinite Teichmüller modular groups_ , Invent. Math. 141 (2000), no. 3, 503–560. MR 1779619
  * [Oda97] Takayuki Oda, _Etale homotopy type of the moduli spaces of algebraic curves_ , Geometric Galois actions, 1, London Math. Soc. Lecture Note Ser., vol. 242, Cambridge Univ. Press, Cambridge, 1997, pp. 85–95. MR 1483111
  * [Pet13] Dan Petersen, _The operad structure of admissible $G$-covers_, Algebra Number Theory 7 (2013), no. 8, 1953–1975. MR 3134040
  * [Pop21] Florian Pop, _Little survey on i/om and its variants and their relation to (variants of) gt — old & new_, Topology and its Applications (2021), 107993\.
  * [Qui08] Gereon Quick, _Profinite homotopy theory_ , Doc. Math. 13 (2008), 585–612. MR 2466189
  * [Ray18] Sophie Raynor, _Compact symmetric multicategories and the problem of loops._ , Ph.D. thesis, 2018.
  * [Ray21] Sophie Raynor, _Graphical combinatorics and a distributive law for modular operads_ , Adv. Math. 392 (2021), Paper No. 108011, 87. MR 4316667
  * [Ser08] Jean-Pierre Serre, _Topics in Galois theory_ , second ed., Research Notes in Mathematics, vol. 1, A K Peters, Ltd., Wellesley, MA, 2008, With notes by Henri Darmon. MR 2363329
  * [SL97] Leila Schneps and Pierre Lochak (eds.), _Geometric Galois actions. 1_ , London Mathematical Society Lecture Note Series, vol. 242, Cambridge University Press, Cambridge, 1997, Around Grothendieck’s “Esquisse d’un programme”. MR 1483106
  * [Til00] Ulrike Tillmann, _Higher genus surface operad detects infinite loop spaces_ , Math. Ann. 317 (2000), no. 3, 613–628. MR 1776120
  * [Wah04] Nathalie Wahl, _Infinite loop space structure(s) on the stable mapping class group_ , Topology 43 (2004), no. 2, 343–368. MR 2052967
  * [Wal21] Tashi Walde, _2-Segal spaces as invertible infinity-operads_ , Algebr. Geom. Topol. 21 (2021), no. 1, 211–246. MR 4224740
  * [War20] Ben C. Ward, _Toward a minimal model for $h_{\ast}(\overline{M})$_, 2020.