††thanks: These authors contributed equally.††thanks: These authors
contributed equally.

# Statistical mechanics of dimers on quasiperiodic Ammann-Beenker tilings

Jerome Lloyd  Rudolf Peierls Centre for Theoretical Physics, Parks Road,
Oxford OX1 3PU, United Kingdom  School of Physics and Astronomy, University of
Birmingham, Edgbaston Park Road, Birmingham, B15 2TT, United Kingdom
Department of Theoretical Physics, University of Geneva, 24 quai Ernest-
Ansermet, 1211 Genève 4, Switzerland  Sounak Biswas  Rudolf Peierls Centre for
Theoretical Physics, Parks Road, Oxford OX1 3PU, United Kingdom  Steven H.
Simon  Rudolf Peierls Centre for Theoretical Physics, Parks Road, Oxford OX1
3PU, United Kingdom  S. A. Parameswaran  Rudolf Peierls Centre for Theoretical
Physics, Parks Road, Oxford OX1 3PU, United Kingdom  Felix Flicker  Rudolf
Peierls Centre for Theoretical Physics, Parks Road, Oxford OX1 3PU, United
Kingdom  School of Physics and Astronomy, Cardiff University, The Parade,
Cardiff CF24 3AA, United Kingdom

###### Abstract

We study classical dimers on two-dimensional quasiperiodic Ammann-Beenker (AB)
tilings. Using the discrete scale-symmetry of quasiperiodic tilings, we prove
that each infinite tiling admits ‘perfect matchings’, where every vertex is
touched by one dimer. We show the appearance of so-called _monomer
pseudomembranes_. These are sets of edges which collectively host exactly one
dimer, which bound certain eightfold-symmetric regions of the tiling. Regions
bounded by pseudomembranes are matched together in a way that resembles
perfect matchings of the tiling itself. These structures emerge at all scales,
suggesting the preservation of collective dimer fluctuations over long
distances. We provide numerical evidence, via Monte Carlo simulations, of
dimer correlations consistent with power laws over a hierarchy of different
lengthscales. We also find evidence of rich monomer correlations, with
monomers displaying a pattern of attraction and repulsion to different regions
within pseudomembranes, along with signatures of deconfinement within certain
annular regions of the tiling.

##  I Introduction

Dimer models have long attracted interest as elegant routes to capture the
interplay of local constraints and lattice geometry. The classical dimer
problem is a combinatorial one, counting the number of configurations of hard
rods on a lattice. It was solved in the early sixties for planar graphs by
Pfaffian techniques [1, 2, 3], a solution which exposed a link to the free
fermion models. Much of the early interest was indeed spurred by connections
to the planar Ising model [4, 5], which famously falls into this class.
Classical dimers have continued to play an important role within physics,
mathematics, and computer science communities over the last century owing to
their ubiquity in problems of constraint satisfaction, optimization, and
combinatorics [6, 7, 8, 9]. Many interesting questions remain concerning the
role of dimensionality, geometry and topology of the underlying graph on the
emergent physics.

Perhaps the principal reason to study classical dimer systems, however, is to
better understand their quantum counterparts. Quantum dimer models were
introduced by Rokhsar and Kivelson [10, 11, 12, 7] as effective descriptions
of short-range resonating valence bond physics in high-temperature
superconductors [13, 14]. They have since outgrown this original motivation
and now rank among the paradigmatic models of quantum statistical mechanics.
They are known to host a rich variety of phases and phase transitions [15, 16,
17, 18, 19, 20, 21], including both gapped and gapless quantum spin liquids
[12, 22, 23, 24, 25, 26, 27] and deconfined quantum critical points [28, 29,
*SenthilEA2, 31], whose emergent gauge structure and fractionalized
excitations have particularly intuitive descriptions in terms of dimers [7].
More recently, their local constraints have been proposed as a route to glassy
quantum dynamics and slow thermalization [32, 33, 34, 35]. The classical dimer
model provides basic intuition toward the quantum problem. Furthermore, at
exactly one point of the zero-temperature phase diagram — the critical
Rokhsar-Kivelson point — the wavefunction is given by the equal amplitude
superposition of all classical dimer states111This statement is strictly only
true if the ground state is non-degenerate, but is simply generalised to the
case with degeneracies.. The ground state dimer correlations at the Rokhsar-
Kivelson point match the infinite temperature correlations of the classical
model. The classical dimer model thus serves as an important starting point to
the quantum model.

Here we consider classical dimer models on bipartite graphs [1, 36, 2, 3, 37,
38, 39, 40, 26, 41, 42, 43, 41, 44, 45, 46, 47, 48, 49, 50]. A graph is a set
of vertices connected by edges. It is bipartite if its vertices can be
partitioned into two mutually exclusive sets such that there are no edges
between vertices belonging to the same set (same bipartite ‘charge’). Dimers
are placed on the edges such that each vertex connects to zero or one dimers
(a hard-core constraint). This defines a dimer covering, or _matching_. An
unmatched vertex not connected to a dimer is termed a monomer. A monomer-free
configuration, if one exists, is called a perfect matching.

The perfect matchings of graphs admitting planar embeddings can be counted
exactly using the previously mentioned Pfaffian techniques. In practice such
methods amount to diagonalisation of the so-called Kasteleyn matrix, which in
many cases can be done analytically via Fourier analysis: if the graph lacks
translational invariance, however, no simple analytical form is guaranteed to
exist. Numerical solution becomes computationally demanding for large systems
(generally we are interested in the thermodynamic limit), and does not offer
the same insight. A more intuitive perspective is afforded by the height
representation [51, 52, 53, 54], particularly when it is applied to periodic
bipartite lattices that admit perfect matchings. On such lattices, the
statistical mechanics of dimer configurations can be understood by mapping
dimer coverings to configurations of an integer-valued ‘height’ field on edges
of the dual lattice. The hard-core constraint becomes a zero-divergence
condition on this field — i.e. a Gauss law — allowing it to be re-expressed as
the lattice curl of a scalar (vector) height variable in 2D (3D). The height
mapping is most useful when entropically favoured dimer coverings correspond
to locally flat height configurations. Dimer correlations can then be deduced
using a coarse-grained free energy density for the height field, taking a
local Gaussian form at long wavelengths. Monomers appear as vortex defects of
the height field. In 2D, if the microscopic parameters correspond to the
vorticity being irrelevant (as on the square and honeycomb lattices), the
height model is in a _rough_ phase, implying critical (power law) dimer
correlations and logarithmic confinement of monomers (i.e. the free energy
cost of a pair of test monomers in an otherwise-perfect matching diverges
logarithmically with their separation). When the vorticity is relevant (as on
the square lattice with additional aligning interactions [41]), the height
model is in its _flat_ phase, with exponentially decaying connected
correlations of dimers and linearly confined monomers. Since vortex defects
are never relevant in 3D, dimer correlations are always algebraic, and
monomers are deconfined. That is, a test pair can be separated to arbitrary
distance with finite free energy cost. However, these arguments rely on both
the existence of perfect matchings and the identification of locally flat
height configurations with high-probability configurations. Neither is
guaranteed for a generic bipartite graph.

Classical dimers have also been studied in settings with disorder, such as
random regular graphs and Erdős-Renyi random graphs [55, 56, 57, 58], using
approaches that are asymptotically exact in the thermodynamic limit [59, 60].
However, the absence of conventional spatial locality in these ensembles rules
out any simple generalization of the notions of dimer correlations and monomer
confinement.

Figure 1: _Clockwise:_ _(a)_ A finite patch of the Ammann-Beenker (AB) tiling.
Composed of copies of square and rhombus tiles, the (infinite) tiling covers
the plane in an ordered fashion, yet never repeats periodically. _(b)_ A
maximum matching (dimer covering) of a patch of the AB tiling. The tiling can
be perfectly matched in the thermodynamic limit; on finite patches, an $O(1)$
_number_ of unmatched vertices (monomers) generally appear, which can be moved
to the boundary. Thick black lines indicate links which comprise overlapping
pseudomembranes, each of which collectively host one dimer. Yellow edges
indicate a dimer on a pseudomembrane. _(c)_ A patch of the AB∗ tiling,
obtained from AB by removing all 8-connected vertices. _(d)_ A maximum
matching of a patch of the AB∗ tiling. Pseudomembranes become membranes,
hosting zero dimers and leading to a decoupling of dimers residing on
different _ladders_.

Figure 2: _Left:_ The $e_{j}$-dependence of the connected dimer correlations,
$|C(e_{0},e_{j})|$ (Eq. (6)). The source edge $e_{0}$, indicated by the solid
red triangle, connects an $8_{2}$-vertex to a nearby ladder. The resulting
correlations are typical of slowly decaying examples, and resemble a power
law. (See Sec. V). _Right:_ Density plot of the monomer correlation function
$Z(x,y)$, for the $8_{4}$-vertex. $Z(x,y)$ is displayed as a function of $y$,
with $x$ fixed at a vertex marked by a solid red dot.

Recent work has explored the problem of classical dimer models on Penrose
tilings [61]. These are infinite tilings of the plane constructed from two
types of tiles. The tiles fit together without gaps or defects, in such a way
that no patch can be tessellated periodically to reproduce the pattern [62,
63, 64]. Despite lacking the discrete translational symmetries of crystal
lattices, they nevertheless display long-range order. For example, their
Fourier transforms, which are tenfold rotationally symmetric, feature sharp
Bragg peaks which can be labelled by a finite number of wave vectors. This
latter condition defines the Penrose tiling to be _quasiperiodic_ [64].
Penrose tilings came to prominence in the physics community with the discovery
of _quasicrystals_ , real materials whose atoms are arranged quasiperiodically
[65]. Considering the edges and vertices of the tiles as those of a bipartite
graph, Penrose tilings do not admit perfect matchings despite having no net
imbalance in their bipartite charge [61]. Instead, they have a finite density
of monomers in the thermodynamic limit. The _maximum matchings_ on Penrose
tilings, which contain the maximum number of dimers, have an unusually rich
underlying structure, quite distinct from either periodic or random systems.
In general maximum matchings, monomers can be thought of as moving via dimer
re-arrangements. On Penrose tilings, monomers are always confined within
regions bound by nested loops, or _monomer membranes_. These membranes are
composed of edges which do not host a dimer in any maximum matching. Each such
region has an excess of vertices belonging to one or the other bipartite
charge, and hosts a corresponding number of monomers. Adjacent regions have
monomers of the opposite bipartite charge. The properties of these membranes
and the regions that they enclose follow directly from the dimer constraint
and the underlying symmetry of the tiling, and can hence be precisely
determined. Ref. 66 identified similar monomer-confining regions, separated
either by membranes or perfectly matched regions, as components of the
Dulmage-Mendelsohn decomposition of generic bipartite graphs [67, 68, 69, 70].
This was used to investigate phase transitions of such monomer-confining
regions in ensembles of periodic lattices with random vertex dilution, such as
those used to model vacancy disorder in quantum magnets.

While both Refs. 61 and 66 consider bipartite dimer models, the usual mapping
to height models does not apply to quasiperiodic graphs, or graphs where
vertices can have different co-ordination numbers. While a more general height
mapping is possible in principle [71], the resulting height functions
typically do not lead to analytically tractable coarse-grained continuum free
energy functionals. This is because there is no longer a simple relationship
between the local configuration of the height field and the statistical weight
of the global dimer covering. In any case, due to a sizeable density of
monomers in the cases studied in Refs. 61 and 66, connected correlation
functions of dimers are short-ranged and more or less unremarkable. In
addition, monomer correlation functions are non-monotonic and strongly site-
dependent, making it challenging to define a crisp notion of monomer
confinement. These facts challenge the goal of a precise characterization of
long-wavelength properties of dimer models in quasiperiodic environments.

###  I.1 Results

In this work, we meet this challenge in the setting of a distinct
quasiperiodic dimer problem for which we can make a series of exact, and
asymptotic, statements. Specifically, we study classical dimers on the Ammann-
Beenker (AB) tiling, shown in Figures 1a and 1b. This tiling has been the
topic of much recent attention, with investigations in the context of
magnetism [72, 73, 74], superconductivity [75], critical eigenstates [76],
protected Majorana modes [77] and topological insulators [78]. Like the
Penrose tilings, AB tilings exhibit discrete scale invariance: _deflations_
(vertex decimations followed by rescaling lengths by the irrational silver
ratio) map an AB tiling to another AB tiling. We prove that these tilings host
perfect matchings in the thermodynamic limit, in contrast to the Penrose
tilings investigated in Ref. [61]. Our proof makes use of the discrete scale
invariance characteristic of quasicrystals: we find that at any given coarse-
graining scale, special vertices that are left invariant by double deflations
lead to the preservation of strong dimer-dimer correlations at the next scale.
This suggests that certain regions associated with these vertices retain
mutual dimer correlations. The preserved vertices have edge-co-ordination
eight and we refer to them as ‘8-vertices’.

The success of this iterative construction of dimer coverings motivates us to
consider an auxiliary problem on a related graph that we dub the AB∗ tiling,
Fig. 1c. This is obtained from the AB tiling by removing all the 8-vertices.
The AB∗ tiling is also perfectly matched and does not host monomers, and we
show that it decouples into perfectly matched one-dimensional regions that we
call _ladders_ , separated by membranes. These membranes, like those in Refs.
61 and 66, are composed of edges between different ladders that do not host a
dimer in any maximum matching. However, unlike the monomer-confining regions
of Refs. 61 and 66, they separate perfectly matched regions. This structure
allows us to systematically treat the matching problem on the AB tiling once
the 8-vertices are reintroduced. We show that membranes in the AB∗ tiling
become _pseudomembranes_ in the full AB tiling, concentric with the
8-vertices: the edges belonging to every pseudomembrane now collectively host
exactly one dimer, as the monomer reinstated on the central 8-vertex of the
region ‘crosses’ the membranes in order to be matched with monomers from other
8-vertices.

Each 8-vertex is surrounded by at least one pseudomembrane. Loosely speaking,
a double deflation maps this 8-vertex and its surrounding pseudomembrane-
bounded region into a single vertex at the next scale. Since each
pseudomembrane is crossed by exactly one dimer, this procedure preserves an
“effective dimer-constraint” at each successive scale— thereby leading to
effective matching problems at each scale. This remarkable property provides a
heuristic picture of the emergence of correlated dimer fluctuations over large
distances. It also suggests that the AB tiling is an intriguing example of a
lattice-level (rather than continuum) coarse-graining of a constrained system
that faithfully imposes the constraint at each successive decimation scale
222We emphasize the deterministic nature, since real-space decimations can
have an especially simple structure in random systems..

We show that the discrete scale invariance exhibited by perfect matchings
leaves its imprint in both dimer and monomer correlations, as exhibited in
Fig. 2. Investigating connected dimer correlations numerically, we show that,
while they are strongly anisotropic and site-dependent, the connected
correlation functions of certain dimers have slow decays, consistent with
power laws, cutoff by a set of lengthscales going up to the system size. This
is particularly striking given the absence of the continuum height description
which mandates power law correlations in periodic bipartite lattices [54, 9].
We then turn to monomer correlations, where we observe a pattern of ‘charged’
correlations set by the pseudomembranes, whereby a monomer is strongly
(weakly) correlated to monomers within pseudomembranes centred on 8-vertices
of opposite (equal) bipartite charge to the monomer. We further show, that in
the angular direction around an 8-vertex, monomer-monomer correlations
asymptote to finite constant values at large separation — that is, a pair of
monomers are _deconfined_ with respect to annular separation. We argue that
these behaviours arise as a consequence of effective matching problems at each
scale. Finally, we investigate the phase diagram of dimer models on both the
AB tiling and AB∗ tiling in the presence of a classical aligning interaction
resembling the Rokhsar-Kivelson potential term, as a step on the road towards
a study of quasiperiodic quantum dimer models.

The remainder of this paper is organized as follows. We introduce the
necessary background on dimer covers and AB tilings in Sec. II. In Sec. III we
prove that perfect matchings exist for AB tilings in the thermodynamic limit.
This construction leads to the introduction of the auxiliary AB∗ tiling, which
is also perfectly matched. In Sec. IV.1 we prove the existence of membranes in
the AB∗ tiling; in Sec. IV.2 we demonstrate how these become pseudomembranes
in the AB tiling, and in Sec. IV.3, we explain how the pseudomembranes lead to
the structure of effective matchings at different scales across the tiling.
Turning to numerical results on the AB tiling, after outlining our choice of
samples and boundary conditions in Sec. V.1, we identify connected dimer
correlations consistent with power laws (Sec. V.2), and long range monomer
correlations with regions of annular deconfinement (Sec. V.3). In Sec. V.4 we
investigate the effects of including a classical aligning interaction in both
the AB and AB∗ tilings. We provide concluding remarks in Sec. VI.

##  II Background

###  II.1 Dimer models and graph theory

In this section we introduce the necessary terminology to discuss dimer
coverings on graphs. The graphs of interest in this paper have two important
properties. First, they are bipartite, meaning the vertices can be partitioned
into two mutually exclusive subsets, $\mathcal{U}$ and $\mathcal{V}$, so that
every vertex in $\mathcal{U}$ ($\mathcal{V}$) only has edges to vertices in
$\mathcal{V}$ ($\mathcal{U}$). If two vertices belong to the same subset, we
will say they have equal (bipartite) _charge_ ; otherwise, they are oppositely
charged. Second, the graphs admit planar embeddings. We keep the geometry of
the tiling, although strictly speaking only the graph topology is relevant to
the matching problem.

A matching of a graph is a subset of edges such that no vertex is incident
with more than one edge in the subset [79]. A matching is equivalent to a
dimer configuration, as edges in the matching can be covered by dimers, with
no vertex touching more than one dimer. A vertex connected to an edge in the
matching is said to be matched; an unmatched vertex is called a monomer. A
perfect matching is a matching with every vertex matched or, equivalently, a
monomer-free dimer covering. Not every graph admits a perfect matching — a
simple counterexample is any graph with an odd number of vertices. A maximum
matching is a matching with the maximum number of dimers (minimum number of
monomers): Fig. 3a-b shows examples of maximum and perfect matchings. If a
graph admits a perfect matching, then any maximum matching is necessarily
perfect. When considering the limit of infinite system size, as we will do
here, a sensible definition of perfect matchings requires that the density of
monomers vanishes, in this limit. This avoids the unnecessary complication of
dealing with a small, $O(1)$ number of unpaired boundary vertices— the exact
number of such monomers depends on how exactly one chooses to terminate the
system, and does not scale with the size of the graph.

Figure 3: (a) A maximum matching which is not perfect. Unmatched vertices are
marked with a blue circle. (b) A perfect matching. (c) An alternating cycle;
augmenting this cycle — swapping covered and uncovered edges — yields a new
matching with the same number of dimers. (d) An even-length alternating path
terminating at a monomer; upon augmenting this path, the monomer is
transported to the other end of the path. (e) Augmenting an odd-length
alternating path between monomers, or _augmenting path_ , annihilates the two
monomers in favour of a dimer.

Usually a graph will have multiple maximum or perfect matchings and, from a
statistical mechanics perspective, our interest is in this full configuration
space, possibly up to certain constraints (e.g. we may only consider perfectly
matched configurations, or penalise matchings with certain alignments of
dimers). An _alternating path_ is a connected subset of edges along which
edges are alternately covered and uncovered by dimers. Starting from any
matching, switching which edges are covered/uncovered in a closed alternating
path (_alternating cycle_) results in another matching with the same number of
dimers (see Fig. 3c). Switching those edges in an open odd-length alternating
path changes the number of monomers in the matching — for example, two
monomers can be created by removing one dimer. This process of switching
covered and uncovered edges is known as augmenting the path. All alternating
cycles are of even length (on a bipartite graph this statement is trivial
since all cycles are of even length).

On a bipartite graph, monomers are assigned a charge depending on which
bipartite subgraph they reside on, and are able to ‘move’ through the dimer
vacuum along alternating paths: taking an even-length alternating path with
one end terminating on one of the monomers, augmenting the path results in the
monomer being translated to the opposite end of the path, while conserving the
monomer’s charge (see Fig. 3d). The creation of a monomer pair on a bipartite
graph has a physical analogy in the excitation of a particle-antiparticle or
defect pair above the vacuum state (viewed as one where all monomers are
paired into neutral dimers). Given a maximum matching, all other maximum
matchings in the configuration space can be reached by combinations of two
basic ‘moves’: (i) augmenting alternating cycles; and (ii) transporting
monomers along alternating paths of even length. Detailed discussions on
classical dimer coverings and their application to physics can be found in
e.g. Refs. [80, 81, 71].

Monomers can be added to the matching by augmenting odd-length paths of
dimers. The reverse process is also possible. Starting from an imperfect
matching, if an odd-length alternating path can be found with end points
terminating on two monomers (an augmenting path), then this path can be
augmented to annihilate the two monomers in favour of a dimer (see Fig. 3e).
If augmenting paths can be found sequentially between all remaining monomers
of a matching, so that no monomer appears in more than one path, then the
augmentation of these paths results in a perfect matching. We will use these
facts to prove the Ammann-Beenker tilings can be perfectly matched.

###  II.2 Ammann-Beenker tilings

Although we will use the language of graph theory in our discussion of AB, the
mathematical theory of quasicrystals has traditionally been developed in the
language of _tilings_. A tiling is a filling of space with congruent shapes
without overlaps or gaps [64]. For clarity we will use _tiling_ to refer to an
infinite tiling of the plane; finite sections of a tiling we refer to as
_patches_. Periodic tilings can be formed by repetition of a single tile, such
as a square or hexagon. Conventional crystals can be seen as regular tilings
of 3D space by an atomic unit cell; the underlying symmetries can be deduced
from diffraction experiments, and yield the 230 crystallographic space groups
[82]. However, the only rotational symmetries compatible with such periodic
long-range order (in 2D or 3D) are 2-, 3-, 4-, and 6-fold. When diffraction
experiments on AlMn-alloys revealed structures compatible with 5-fold
rotational symmetry [83], crystallographic theory had to be extended to
include _quasi_ crystals — alloys with long-range atomic order but no
translation symmetry. Quasicrystals can feature finite patches of 5-, 8-, 10-
or 12-fold rotational symmetry [84, 85, 86].

Figure 4: The inflation rule $\sigma$, in which a tile is decomposed into
smaller tiles, followed by a rescaling of all lengths by a factor of the
silver ratio $\delta_{S}=1+\sqrt{2}$ (which we do not show here). The inverse
$\sigma^{-1}$, deflation, is uniquely specified. An arbitrarily large AB
tiling can be generated from a small patch by repeated inflations. (Note the
inflation of the square tile breaks the rotation symmetry so we must keep
track of orientation, as captured by the triangular motif shown. We will
usually leave the markings absent in future figures for clarity.) Figure 5:
The seven vertex configurations, and their action under inflation (Fig. 4).
All vertices map to $8$-vertices under at most two inflations.

Quasiperiodic tilings are a class of planar tilings without translation
symmetry, capable of accounting for the symmetries observed in quasicrystals
which are forbidden in periodic tilings [64, 87, 63]. They are distinguished
from the more general set of aperiodic tilings by the fact that their
diffraction patterns can be indexed by a finite number of wavevectors [64].
The most famous family of quasiperiodic tilings is due to Penrose [62].
Penrose tilings have local patches of 5-fold symmetry (and can have at most
one true 5-fold rotational centre). The Ammann-Beenker tilings [88, 63] have
8-fold symmetry, and together with the decagonal (10-fold) and dodecagonal
(12-fold) tilings, they make up the ‘Penrose-like’ tilings [89]. The
remarkable fact that the four symmetries displayed by these tilings account
for the symmetries of all physical quasicrystals (i.e. those observable in
experiment) was explained by Levitov based on arguments of energetic stability
[90]. The Penrose-like tilings have therefore seen extensive study in
connection to physics.

Classical dimers on Penrose tilings were studied in previous work [61]; here
we focus on the Ammann-Beenker (AB) tiling, a patch of which is shown in Fig.
1a. The AB tiling is constructed from copies of two inequivalent tiles: a
square, and a rhombus with angles $\pi/4$ and $3\pi/4$. Both tiles have edges
of unit length. No shifted copy of this tiling can be exactly overlaid with
the original. Many mathematical properties of AB tilings are well understood
and can be found in e.g. [64]. Here we briefly mention those relevant to the
following discussion.

The Ammann-Beenker tilings (plural) constitute an uncountable set of LI
(_locally indistinguishable_ or _locally isomorphic_) tilings. Two tilings are
LI if any finite patch of one can be found in the other. In this way, all AB
tilings ‘look the same’ from a local perspective, distinguished only in their
global structure. In fact, every finite patch recurs with positive frequency
in all tilings. This property accounts for the long-range order of the
quasiperiodic tilings. This structure can be compared to that of the periodic
tilings, where the long-range order arises from the repeated unit cell.
Results that we discuss in the following sections apply in generality to the
entire set of AB tilings.

Any AB tiling $\mathcal{T}$ can be generated by several methods [91, 64, 63].
Square and rhombus tiles can have their edges decorated by _matching rules_
which force the tiles to fit together quasiperiodically; an AB tiling can be
created as a slice through a higher dimensional periodic lattice (the _cut-
and-project_ technique); or the tilings can be generated via an inflation
procedure. This inflation method allows us to discuss the scale symmetry of
the tilings, and is our primary workhorse in this paper.

Starting from a finite seed patch $\mathcal{T}_{0}$ (e.g. a single square
tile) an inflation rule $\sigma$ is repeatedly applied to grow the patch as
$\mathcal{T}_{n}=\sigma^{n}(\mathcal{T}_{0})$, with the number of tiles
growing exponentially under inflation. $\sigma$ consists of two steps:
decomposition, where every tile is divided into smaller tiles as shown in Fig.
4, followed by rescaling, where the decomposed tiling is scaled so that the
new tiling is formed from exact copies of the original tiles. The scaling
factor is the silver ratio $\delta_{S}$, defined by

$\delta_{S}^{2}=2\delta_{S}+1$ (1)

and equal to

$\delta_{S}=1+\sqrt{2}.$ (2)

The Penrose tiling instead has as its scale factor the golden ratio
$\varphi=\frac{1+\sqrt{5}}{2}$. Note that it is the _length_ (rather than
area) of the tile edges that scales by $\delta_{S}$ under decomposition: this
can be seen geometrically in Fig. 4, with each edge divided into a rhombus
edge and the square diagonal. The area of each tile scales by $\delta_{S}^{2}$
under decomposition. In the following, if we say one tiling is larger than
another by some power of the silver ratio, we are always referring to the
respective lengths of their tile edges.

Patches of arbitrarily large size can be generated by the inflation process.
The tiling $\mathcal{T}$ is recovered after an infinite number of inflations.
The inverse of the inflation rule, $\sigma^{-1}$, deflation, is also uniquely
specified on a tiling, consisting of composition — reconstruction of the
larger tiles from smaller tiles — and rescaling by the inverse of the silver
ratio. Acting with $\sigma$ or $\sigma^{-1}$ on $\mathcal{T}$ returns another
tiling in the same LI class.

Every possible configuration of tiles around a vertex in AB is identical to
one of the seven vertex configurations shown in Fig. 5 (up to rotations). The
5-vertices ($5_{A}$ and $5_{B}$) yield two distinct results upon inflation
depending on the orientation of the adjacent square plaquettes. All other
vertices can be uniquely identified by their co-ordination number (valence, in
graph theory nomenclature). Under $\sigma$, each vertex configuration is
mapped to a different configuration, e.g. $4\rightarrow 6$, with the exception
of the 8-vertex, which inflates to another 8-vertex. These inflations are also
shown in Fig. 5.

Figure 6: The scale symmetry of the AB tiling: the $8$-vertices of an AB
tiling are positioned to sit at the vertices of another locally
indistinguishable AB tiling, with lengths increased by a factor of
$\delta_{S}^{2}$, where $\delta_{S}=1+\sqrt{2}$ is the silver ratio.
8-vertices are coloured by their bipartite charge.

The scale symmetry of the Ammann-Beenker tilings arises from this inflation
structure, and specifically from the invertibility of $\sigma$. One expression
of this symmetry is that all 8-vertices of $\mathcal{T}$ are positioned at the
vertices of the tiling obtained by twice-composing $\mathcal{T}$, i.e. the
twice-deflated tiling $\mathcal{T}_{-2}\equiv\sigma^{-2}(\mathcal{T})$ with
lengths rescaled by $\delta_{S}^{2}$. This follows from noticing that every
vertex is mapped to an 8-vertex under two inflations, as can be checked from
the vertex inflations in Fig. 5. By the inverse, deflating twice maps the
8-vertices of $\mathcal{T}$ to the vertices of $\mathcal{T}_{-2}$. This scale
symmetry is more clearly shown in Fig. 6, which shows a patch of $\mathcal{T}$
overlaid with the scaled $\mathcal{T}_{-2}$. The 8-vertices of $\mathcal{T}$
are coloured by their bipartite charge, and are seen to coincide with the
vertices of the scaled $\mathcal{T}_{-2}$. We will rely on this symmetry in
the rest of the paper. Anticipating this 8-vertex $\leftrightarrow$ vertex
mapping, we introduce $\sigma^{2}$ inflation tiles, shown in Fig. 7. Compared
to the basic inflation tiles (Fig. 4), the $\sigma^{2}$ tiles have the
property that their vertices become $8$-vertices in the inflated tiling.

Figure 7: The $\sigma^{2}$ (in/de)flation rules, which map vertices directly
to 8-vertices in the completed tiling. Here we leave off triangular motifs in
the inflation for clarity.

This scale hierarchy continues: under $\sigma^{2}$, the 8-vertices of
$\mathcal{T}$ inflate to 8-vertices, and these twice-inflated 8-vertices are
positioned to sit at the vertices of a tiling with lengths scaled by
$\delta_{S}^{4}$. With this in mind, it is convenient to define an ordering to
the $8$-vertices. An $8$-vertex is order-zero if it maps to a 7-, $5_{A}$-, or
6-vertex under a single deflation; order-one if it deflates to an order-zero
8-vertex; and so on. This flow of vertices is represented in Fig. 8. We denote
an order-$n$ $8$-vertex an $8_{n}$-vertex. An $8_{n}$-vertex is therefore the
$n^{\textrm{th}}$ inflation of an order-0 8-vertex, $8_{0}$. We find that
$8_{n}$-vertices of $\mathcal{T}$ sit at the vertices of an AB tiling, LI to
$\mathcal{T}$, with lengths scaled by a factor of $\delta_{S}^{(n+2)}$. Since
_all_ vertices of $\mathcal{T}$ are mapped to order-$n$ or higher 8-vertices
under $\sigma^{(n+2)}$, 8-vertices of order-$n$ and higher can also be viewed
as those vertices of $\mathcal{T}$ that are preserved under $n+2$ deflations.
We will denote the $n$-times deflated tiling of $\mathcal{T}$ as
$\mathcal{T}_{-n}$ (generally we will not distinguish between deflations and
decompositions, unless the distinction is important).

Figure 8: The flow of vertices under successive inflations. The ordering of
$8$-vertices is defined so that an order-zero 8-vertex, $8_{0}$, deflates once
to a $5_{A}$-, 6-, or 7-vertex, and an order-$n$ 8-vertex, $8_{n}$, deflates
to $8_{n-1}$.

To conclude this section, we discuss the 8-fold symmetry that defines the
Ammann-Beenker tilings. First, as mentioned previously, the Bragg spectrum
(Fourier transform of the lattice) has a discrete 8-fold rotational symmetry
($D_{8}$ in Schönflies notation) [92]. Second, and most importantly to us, the
symmetry shows up in the structure of tiles surrounding an 8-vertex. Every
vertex configuration has a set of tiles which always appears around the vertex
wherever it is placed in the tiling. Such a motif is known as the vertex
_empire_ [63, 93]. Vertex empires are generally not simply connected; the set
of empire tiles simply connected to a vertex is called the _local empire_ of
the vertex. The local empire of the $8_{0}$-vertex is shown in Fig. 9, and has
$D_{8}$ symmetry. The inflation $\sigma$ preserves this symmetry, and so the
radius of symmetry of an $8_{n}$-vertex is a factor of $\delta_{S}$ larger
than for an $8_{n-1}$-vertex. The local empire of an $8_{n}$-vertex (which we
will refer to as an $8_{n}$-empire) in fact includes that of an
$8_{n-1}$-vertex within it. According to the definition of the LI-class of
tilings, every finite region can be found with positive frequency across the
tiling. It follows that $D_{8}$-symmetric 8-empires of arbitrarily large size
can be found across the tiling, with a frequency corresponding to the
frequency of the respective 8-vertices.

Figure 9: The local empire of an $8_{0}$-vertex, the simply connected set of
tiles that always appear around an $8_{0}$-vertex in the tiling. The local
empire has $\mathcal{D}_{8}$ symmetry.

##  III Perfect matchings on the Ammann-Beenker tilings

We now show that Ammann-Beenker tilings can be perfectly matched. We work in
the thermodynamic limit, where the tiling covers the infinite plane and
boundary effects can be ignored. Taking the thermodynamic limit is a delicate
procedure in quasiperiodic systems since one must necessarily work with open
boundary conditions and bound their contribution as the system size increases.
By ‘perfect matchings’ in the thermodynamic limit, we mean those with zero
monomer density. While efficient algorithms exist to determine the maximum
matching of finite graphs [94, 95], showing that an infinite graph (the
relevant case in the thermodynamic limit) admits a perfect matching is in
general non-trivial. Quasiperiodic Penrose tilings cannot be perfectly
matched: though the infinite tiling is charge neutral, monomers are confined
within regions with an excess of one or the other type of bipartite charge.
Such confinement emerges as a direct consequence of the quasiperiodic
geometry: monomers cannot annihilate those of the opposite charge as they
cannot cross so-called monomer membranes. Membranes are sets of edges which
cannot be covered by dimers in any maximum matching. Equivalently, no
augmenting paths exist between monomers on opposite sides of a membrane.
Deleting these edges disconnects the graph.

The perfect matching problem on AB is of a similarly non-trivial nature. We
note that the matching problem on finite patches of the AB tiling depends
sensitively on the patch considered. Clearly a patch with a net imbalance of
bipartite charge never admits a perfect matching. However, the AB tilings have
vanishing net charge density in the thermodynamic limit, because the average
vertex connectivity is the same for the two bipartite subsets. Less trivially,
it is also possible to find charge-neutral patches with unpaired monomers. An
example is the patch generated by inflating the basis square four times:
exactly two monomers remain in the maximum matching, with opposite charges.
This is akin to the Penrose problem where membranes stop the monomers from
matching. In contrast to that case, where the _density_ of monomers approaches
$\sim 10\%$, the observed number of unpaired monomers on AB remains of order
unity as the tiling is grown. We have verified these statements using the
above graph-theoretic methods to compute maximum matchings on a large sample
of patches generated via inflation. While similar membrane structures to those
in Penrose tilings exist on AB (as we will show in Sec. IV), in the latter
case they do not frustrate the perfect matching, as we will show below. On
finite patches, the presence of monomers arises from defects at the boundary
which migrate into the bulk, and no finite density persists in the
thermodynamic limit.

The strategy of our proof that the AB tilings can be perfectly matched is as
follows. Consider the perfect matching problem on an AB tiling $\mathcal{T}$.
We first match up all vertices of $\mathcal{T}$ except for the 8-vertices
(recall that these are the vertices which remain under two deflations). We
then show that the problem of matching the remaining 8-vertices maps to a
perfect matching problem on the twice-deflated tiling $\mathcal{T}_{-2}$. On
this tiling, we match all but the 8-vertices again (this matches all $8_{0}$\-
and $8_{1}$-vertices on the original $\mathcal{T}$). We then use the scale
symmetry of $\mathcal{T}$ to iterate this procedure and obtain an upper bound
on the monomer density of the AB tiling after $n$ deflations. This density
vanishes exponentially as $n\to\infty$, corresponding to taking the
thermodynamic limit.

Our motivation for separating out the 8-vertices comes from the requirement
for a bipartite graph to be charge-neutral in order to admit a perfect
matching. This is true of the AB tiling in the thermodynamic limit. Note,
however, that any $D_{8}$ local empire has an excess charge of at least one.
This follows since every $D_{8}$ local empire has an 8-vertex at its centre
(by definition), and its eight-fold rotational symmetry mandates that the
total number of vertices within the region must be $8m+1$, for some integer
$m$. Since this number is odd, there must be an excess of bipartite charge.
The same argument shows that any symmetric region centred on 8-vertices cannot
be perfectly matched without placing at least one dimer outside of the region.
Since such regions exist at all scales across the tiling, we can always find
arbitrarily large regions that cannot be perfectly matched internally. This
structure of coupled $D_{8}$ regions complicates the problem. By first
removing the 8-vertices at the centres of these regions, we can match the rest
of the tiling systematically before progressively reintroducing and matching
the remaining monomers.

###  III.1 Proof of Perfect Matching

  1. 1.

Let $\mathcal{T}$ be an AB tiling not covered by dimers. Let
$\mathcal{T}_{-2}$ be the tiling obtained by deflating twice on $\mathcal{T}$.
Replacing the tiles of $\mathcal{T}_{-2}$ by the _dimer inflation tiles_
(DITs) in Fig. 10, we obtain a matching of $\mathcal{T}$, such that only the
8-vertices remain unmatched.

The last statement follows from noting that (a) no dimers touch the corner
vertices of the DITs, which map to the 8-vertices of $\mathcal{T}$ (see Sec.
II.2); (b) all vertices in the interior of the DITs are matched; and (c) all
remaining unmatched vertices on the boundary of the DITs (large, black)
overlap consistently with matched vertices on adjacent tile boundaries (large,
white). No double covering occurs.

The density of unpaired monomers on $\mathcal{T}$ after application of the
DITs gives an upper bound on the true monomer density $\rho$ (i.e. the density
remaining in any maximum matching of $\mathcal{T}$ ). Therefore,

$\rho\leq\nu_{8v},$ (3)

where $\nu_{8v}=\delta_{S}^{-4}\sim 0.03$ is the density of 8-vertices on the
Ammann-Beenker tiling [64].

  2. 2.

Next, we allow the monomers to move around the tiling via augmenting paths. We
define 8-vertices (monomers) to be deflate neighbours on $\mathcal{T}$ if they
become true nearest-neighbours on $\mathcal{T}_{-2}$. An augmenting path
always exists between two deflate-neighbouring monomers. This is clear from
the right of Fig. 10, since deflate-neighbouring monomers sit on adjacent
corner vertices of either one of the DITs.

The bound on $\rho$ will be reduced by augmentation of these paths,
annihilating two deflate-neighbouring monomers to give a dimer. Each
augmentation removes the monomers from future possible pairings, but otherwise
does not affect the possibility of annihilations between other monomers, since
augmenting paths between disjoint pairs of deflate-neighbouring monomers can
be chosen so as not to intersect. The paths in Fig. 10 are non-intersecting.

Augmentation of a complete (non-intersecting) set of paths between deflate-
neighbouring monomers results in a perfect matching of $\mathcal{T}$.
According to our definition of deflate-neighbours, a complete set of
augmenting paths is given by a perfect matching of $\mathcal{T}_{-2}$, via the
identification of dimers on $\mathcal{T}_{-2}$ with augmenting paths on
$\mathcal{T}$. Fig. 6 shows that augmenting paths between deflate-neighbouring
8-vertices indeed has the structure of a matching problem at the next scale.

  3. 3.

A perfect matching of $\mathcal{T}_{-2}$ is evidently no easier to obtain than
for $\mathcal{T}$. However, by application of the DITs to the tiling
$\mathcal{T}_{-4}$, we match all vertices of $\mathcal{T}_{-2}$ except the
8-vertices. Augmenting the corresponding paths on $\mathcal{T}$ annihilates
all monomers on $8_{0}$\- and $8_{1}$-vertices of $\mathcal{T}$. The remaining
unmatched vertices correspond to the $8_{n>1}$-vertices, and the bound on
$\rho$ is reduced by another factor of $\nu_{8v}$:

$\rho\leq\nu_{8v}^{2}.$ (4)

  4. 4.

We now apply this procedure to all scales of the AB tiling. We call a monomer
on an $8_{n}$-vertex an order-$n$ monomer. Finding augmenting paths between
all order-$n$ and order-$(n+1)$ monomers of $\mathcal{T}$ corresponds to
finding augmenting paths between all order-$(n-2)$ and order-$(n-1)$ monomers
of the $\mathcal{T}_{-2}$ tiling, and by induction, to a matching of the
non-8-vertices of the $\mathcal{T}_{-(n+2)}$ tiling (here we identify
order-$n$ for $n<0$ with the non-8-vertices according to Fig. 8). Each
matching of the non-$8$-vertices of $\mathcal{T}_{-(n+2)}$ is performed via
the DITs, reducing the bound on $\rho$ by a factor of $\nu_{8v}$. Since the
infinite tiling $\mathcal{T}$ can be deflated an arbitrary number of times
(and $\nu_{8v}<1$), the density of monomers must tend to zero in the
thermodynamic limit:

$\rho\leq\nu_{8v}^{2n},\hskip
28.45274pt\lim_{n\rightarrow\infty}\rho\rightarrow 0,$ (5)

and the tiling admits a perfect matching $\square$.

We point out finally that the above proof does not guarantee a vanishing
_number_ of monomers on the tiling. In fact, it is easy to construct
counterexamples: the infinite tiling obtained by repeated inflation of the
8-fold symmetric patch in Fig. 9 is one. This tiling must have an excess
charge of at least one monomer, which can be seen as the charge residing on
the ‘order infinity’ 8-vertex at the centre of the tiling. It will never be
matched under a finite number of the above inflation matching rules. These
monomers are artefacts of how the boundary of the graph is terminated (for the
above example, we can imagine adding a small number of vertices to the graph
boundary which break the symmetry and allow the monomer to be matched).
Crucially, the number of such monomers is $O(1)$, i.e. it does not scale with
the size of the graph. Consequently, the density of monomers vanishes on all
vertices in the thermodynamic limit, and all observables of interest remain
unchanged by the specific choice of boundary. We emphasize that an $O(1)$
number of monomers on the infinite graph is not a peculiarity of our problem;
a similar number of monomers appears for periodic graphs with certain choices
of boundary conditions (e.g., an $L_{x}\times L_{y}$ square lattice with with
both $L_{x}$ and $L_{y}$ odd always hosts one monomer).

Figure 10: (_Left_) The dimer inflation tiles: deflating with the squared
tiles in Fig. 7, $\mathcal{T}\rightarrow\mathcal{T}_{-2}$, and then re-
inflating with these dimer-decorated tiles places dimers on $\mathcal{T}$.
This matches all vertices of $\mathcal{T}$ except the $8$-vertices (marked
with red and blue circles denoting bipartite charge). Unmatched vertices on
tile boundaries (black) overlap with matched vertices (white) in the completed
tiling. (_Right_) Augmenting paths always exist between neighbouring
8-vertices (the other choice of charge-neutral pairing follows from the
symmetry of the dimers).

##  IV Membranes, Ladders and Effective Matching Problems

In proving the existence of perfect matchings on the Ammann-Beenker tilings,
8-vertices of $\mathcal{T}$ were matched (by augmenting paths) if the
corresponding sites shared a dimer on the deflated tiling $\mathcal{T}_{-2n}$.
Since the 8-vertices sit at the vertices of tilings with lengths rescaled by
powers of the silver ratio, $\delta_{S}^{2n}$, a natural question is whether
an effective description emerges in terms of matchings at larger lengthscales.
In this section, we will show how the 8-vertices of the AB tiling are
surrounded by concentric structures of sets of edges collectively hosting
exactly one dimer. We call these monomer ‘pseudomembranes’. Each
pseudomembrane, therefore, imposes an effective dimer constraint at a larger
scale, with the pseudomembrane bounding a region acting as an effective vertex
(‘effective unit’), connected to the rest of the graph by exactly one dimer.
This effective matching description, in turn, has far-reaching consequences
for the system’s correlations, which we explore in Sec. V.

Monomer _membranes_ were introduced in Refs. 61 and 66, as sets of edges
hosting zero dimers. In Penrose tilings membranes separate unmatched regions
with an excess bipartite charge. The complete AB tiling does not host
membranes. However, we identify similar structures of sets of edges — the
pseudomembranes — which host exactly _one_ dimer in any perfect matching. Like
membranes, pseudomembranes capture how certain aspects of the quasiperiodic
graph structure are encoded in the set of perfect matchings. The properties of
membranes and pseudomembranes can be understood in terms of the Dulmage-
Mendelsohn decomposition of the graph and its ‘fine’ generalization as
discussed in Appendix A. Here, we provide their construction and establish
their properties. We do this by first introducing an auxiliary tiling, ‘AB∗’,
obtained from AB by deleting all 8-vertices. AB∗ admits exact membranes, which
separate perfectly matched quasi-1D regions (‘ladders’). This is in contrast
to Refs. 61 and 66 where membranes confine monomers. We next demonstrate how
the exact membranes become pseudomembranes on AB with the reintroduction of
the 8-vertices. The pseudomembranes lead to the natural identification of
perfectly matched regions of $D_{8}$ symmetry (‘$\mathcal{H}$ regions’) within
the local empires of 8-vertices, which play an important role in the monomer
correlations discussed in Sec. V. To conclude the section, we comment on the
effective matching problem.

Figure 11: The AB∗ ladder tiles: dimer inflation tiles of Fig. 10 with edges
incident to $8$-vertices removed. The removed $8$-vertices are marked with
solid blue and red circles, the colours denoting the two bipartite charges.
The yellow and blue shaded segments join up to form _ladders_ which host
dimers in a maximum matching of AB∗. The edges in the unshaded regions
comprise _membranes_ , which never host a dimer in any maximum matching of
AB∗. The edges enclosing the green shaded region form _stars_ of $16$ edges
around the absent $8$-vertices, and can be perfectly matched in the bulk of
AB∗.

###  IV.1 Membranes and ladders on the AB∗ tiling

Figure 12: All vertex configurations of the ladder-decorated tiles of Fig. 11.
This shows all possible ways in which ladder segments can join up to form
ladders in the AB∗ tiling. The segments shaded with yellow and light blue in
Fig. 11 match up to form ladders, whereas the green segments match up to form
stars in the bulk of the AB∗ tiling.

The important point to take from Sec. III is that at each (double) deflation
step, only the augmenting paths between two 8-vertices survive as a dimer at
the next scale. Crucially, all information that correlates different inflation
scales involves the $8$-vertices. By removing these vertices from AB
(equivalently localizing monomers on all 8-vertices), we obtain the AB∗
tiling. AB∗ has particularly simple correlations and provides insight into the
more complicated statistics of AB.

The AB∗ tiling can be perfectly matched. This follows trivially from Step 1 of
the Perfect Matching proof, since the DITs (Fig. 10) match all vertices except
for the 8-vertices. We will use a decorated version of the DITs, Fig. 11, to
emphasise structures that emerge when the tiles are placed in the full AB∗
tiling. In Fig. 11 the edges connecting the $8$-vertices (solid blue and red
circles) to the rest of the graph are removed. The blue- and yellow-shaded
plaquettes join to form the regions we call _ladders_. The colour codes relate
to the inflation properties of the ladders (see Appendix B). The edges
enclosing the green-shaded regions close to form loops of 16 edges, centred on
the missing 8-vertices, which we call _stars_ (or _order_ -0 ladders). To see
how individual ladder segments match up to form ladders in the graph, it is
useful to refer back to the vertex configurations. They are shown for the AB∗
tiles in Fig. 12 (compare Fig. 5 for the undecorated tiles). The continuation
of blue and yellow regions into ladders, as well as the formation of closed
stars around the green regions, is apparent.

We denote the closed all-blue ladder appearing in the $5_{A}$-, $6$-, $7$\-
and $8$-vertex configurations of Fig. 12 the $L_{1}$ ladder. Higher order
ladders, $L_{n}$, are constructed by $n-1$ inflations $\sigma$ ( Sec. II.2) of
$L_{1}$. The star is obtained by a single deflation of $L_{1}$, and so we
denote the star a zero-order ladder, $L_{0}$. A detailed discussion of this
inflation structure is provided in Appendix B. From the $D_{8}$ symmetry of
the $L_{0}$ and $L_{1}$ ladders, the fact that _all_ ladders that close333The
reader may note that unclosed system-spanning ladders are not ruled out by the
ladder continuations of Fig. 12. Such ladders in fact exist, but are
necessarily of ‘order infinity’ in the inflation scheme: they therefore occur
with zero frequency on the infinite tiling and will not play a part in the
remaining discussion. do so with $D_{8}$ symmetry can also be proven. In
general, an order-$n$ 8-vertex is surrounded by concentric $D_{8}$ symmetric
ladders of orders 0-through-$n$, which justifies the terminology. This
structure can be seen in Fig. 13, where we display a finite patch of the AB∗
tiling, with ladders of orders up to $L_{3}$ surrounding the correspondingly
ordered 8-vertices.

In every perfect matching, stars and ladders form perfectly matched regions,
separated by exact membranes which do not host any dimers. Fig. 11 has dimers
residing only on edges that belong to the stars and ladders. We will show that
all vertices in each star (ladder) must be matched to vertices in the same
star (ladder) in all perfect matchings. Therefore, any edges external to the
stars and ladders (thick white edges in Fig. 11 and Fig. 12) are never covered
by dimers in any perfect matching and hence form exact membranes.

The proof follows from two observations. First, stars are closed loops of $16$
vertices, with eight vertices in each bipartite subset (we denote the two
subsets $\mathcal{U}$ and $\mathcal{V}$) and no vertices in the interior (due
to the removal of the $8$-vertices in constructing AB∗). For each star, all
‘exterior’ vertices with edges to the rest of the graph (i.e. the ‘points’ of
the star) are of the same charge. The ‘interior’ vertices alternate with these
and therefore are all of the opposite charge. Since they cannot match with any
other vertex, we must match each interior vertex with an adjacent exterior
vertex. Therefore each star hosts eight dimers forming one of two possible
alternating paths around the star, leaving no exterior vertices unmatched.

Ladder segments in the tiles of Fig. 11 always contain the same number of
vertices of each charge. This property is inherited by any section of a ladder
built up from these segments. Fig. 12 shows the vertex configurations for the
ladder-decorated tiles, allowing us to read off all the ways in which
different ladder segments can match up to form ladders. For each ladder
section in Fig. 12, all vertices with edges to other ladder segments are of
the same charge, say $\mathcal{U}$. While $\mathcal{V}$-vertices do have edges
connecting them to stars, those edges can never host dimers in a perfect
matching, as we have already shown that the vertices in a star are always
matched to vertices within the star. Since there are an equal number of
vertices of each charge in any ladder, this immediately implies that all
$\mathcal{U}$-vertices in a ladder must match to $\mathcal{V}$-vertices in the
same ladder in a perfect matching to avoid a contradiction. Thus, edges
outside ladders and stars constitute membranes which never host a dimer in any
perfect matching of the AB∗ tiling.

This splitting of the AB∗ tiling into ladder regions separated by membranes
means that no statistical correlation can occur between distinct ladders. The
no-dimer constraint implies membranes act as impermeable boundaries for each
ladder subsystem, and the dimer partition function of the entire 2D tiling
factorises into a product of partition functions for lower-dimensional
quasiperiodic ladders. Thus, the notoriously difficult problem of enumerating
dimer configurations on a graph is simplified on AB∗. We use this fact in
Appendix C to calculate an asymptotically exact result for the free energy of
dimers on AB∗, via transfer matrices. These properties also provide insight
into the more complex correlations of AB, as we will return to in Sec. V.3.
The ladder regions and membranes in any perfectly matched patch of AB∗can be
determined algorithmically by using the Dulmage-Mendelsohn decomposition
described in Appendix A.

Figure 13: A finite patch of the AB∗ tiling, in terms of stars and ladders. An
$8_{n}$-vertex is the centre of concentric ladders of orders $0\leq m\leq n$,
which close with $D_{8}$ symmetry. White space represents impermeable
membranes separating ladders.

###  IV.2 Pseudomembranes on the AB tiling

Armed with our results on AB∗, we now return to the full AB tiling, and show
that the restoration of the deleted 8-vertices transforms the membranes of AB∗
to pseudomembranes on AB. As we defined earlier, a pseudomembrane is a
connected set of edges which collectively host exactly one dimer between them
in any maximum matching. Pseudomembranes satisfy two additional properties:
(i) deleting all the edges in a pseudomembrane disconnects the graph into two
components; (ii) pseudomembranes close with $D_{8}$ symmetry, and are centred
on $8$-vertices.

Figure 14: Membranes in perfectly matched _punctured $8_{2n}$-empires_, which
separate perfectly matched $\mathcal{H}_{i}$ regions demarcated with different
colours. An $8_{n}$-empire is the local empire of an $8_{n}$-vertex. A
punctured $8_{n}$-empire is an $8_{n}$-empire without the central $8$-vertex.
On adding the $8$-vertex back, each membrane becomes a _pseudomembrane_ which
can host a single dimer on its edges. _Top_ : membranes in a punctured
$8_{2}$-empire, separating regions $\mathcal{H}_{0}$ (gold star),
$\mathcal{H}_{1}$ (purple) and $\mathcal{H}_{2}$ (red). _Bottom_ : membranes
in a punctured $8_{4}$-empire, separating regions $\mathcal{H}_{0-4}$. The
$8_{4}$-empire contains a copy of the $8_{2}$-empire. Small components of the
empires outside the largest $\mathcal{H}_{i}$ regions are not shown.

Anticipating the second point, we consider local empires of $8_{n}$-vertices,
which we refer to as $8_{n}$-empires. An $8_{n}$-empire is generated by
inflating the local empire of an $8_{0}$-vertex (Fig. 9) $n$ times. Since the
$8_{n}$-empire cannot be perfectly matched (due to the charge imbalance), we
first remove the central $8$-vertex from the $8_{n}$-empire, yielding what we
term a _punctured $8_{n}$-empire_. Generally, in any matching of the punctured
empire, small components of the tiling lying outside the outermost
$\mathcal{H}_{i}$ will remain unmatched, on account of the finite patch
boundary. Choosing boundary conditions to exclude these outer vertices, the
remaining region can be perfectly matched, and this is what we will take an
$8_{n}$-empire to mean in the rest of section. With this caveat, the punctured
$8_{n}$-empire is perfectly matched, and splits into certain perfectly matched
$D_{8}$-symmetric annular subregions, which we label as $\mathcal{H}_{i}$. In
all perfect matchings of a punctured $8_{n}$-empire , vertices in each
subregion $\mathcal{H}_{i}$ can only match to other vertices within
$\mathcal{H}_{i}$. The $\mathcal{H}_{i}$ are separated from each other by
exact membranes concentric with the central 8-vertex444These $\mathcal{H}$
regions are the perfectly matched components of the Dulmage-Mendelsohn
decomposition reviewed in Appendix A. The zeroth subregion is the star,
$\mathcal{H}_{0}\equiv L_{0}$, and the first subregion is the first-order
ladder, $\mathcal{H}_{1}\equiv L_{1}$. Higher order subregions correspond to
connected components of AB formed from lower order 8-empires, closed ladders,
and the membrane links in between. As explained in Appendix D, _even_
subregions are essentially inflations of the star $L_{0}$, while _odd_
subregions are inflations of $L_{1}$. We therefore refer to $\mathcal{H}_{i}$
as ‘star-like’ for $i$ even, and ‘ladder-like’ for $i$ odd. These statements
generalise the result that the stars and ladders of AB∗ separated by
membranes, can be perfectly matched.

The proof of these statements, along with a more detailed discussion of the
inflation structure of the $\mathcal{H}$ regions, can be found in Appendix D.
Essentially, we first adapt the methods of Sec. III to use the inflation
structure of $\mathcal{H}$ regions and prove that each $\mathcal{H}_{i}$
subregion can be perfectly matched. We then follow it up with a proof that in
all perfect matchings vertices in a region $\mathcal{H}_{i}$ match only to
other vertices within the same region $\mathcal{H}_{i}$. We display the
membranes and $\mathcal{H}_{i}$ subregions for punctured $8_{2}$ and
$8_{4}$-empires in Fig. 14.

If the central $8$-vertex is reinstated to this perfect matching it will host
a monomer. Moving this monomer out of any region enclosed by a membrane of the
punctured empire converts the membranes to pseudomembranes. This follows since
moving the monomer requires the augmentation of alternating paths of even
length which terminate on the monomer. Since such paths traverse a membrane
that originally enclosed the monomer, they will place a single dimer across
the former membrane. Since only a single monomer was added to the perfect
matching, it follows that there can be no more than one such dimer in any
pseudomembrane.

One might wonder if a monomer can recross the membrane in the opposite
direction and thereby place another dimer across the membrane; this is ruled
out by some simple observations about the perfectly matched regions. Any two
perfectly matched regions separated by a membrane have the property that all
edges in the membrane connect vertices of the same bipartite charge in one
region to vertices of the opposite bipartite charge in the other region
(Appendix D). If the central $8$-vertex is a $\mathcal{U}$-vertex, this
implies that each perfectly matched component of a punctured $8_{n}$-empire
has only $\mathcal{V}$-vertices on its inner boundary and
$\mathcal{U}$-vertices on its outer boundary. When a monomer is introduced by
reinstating the central $8$-vertex, the monomer recrossing a membrane would
imply the existence of a perfectly matched region such that its inner boundary
is crossed twice by the monomer and its outer boundary is not crossed by the
monomer. This matches two $\mathcal{V}$-vertices of that region with vertices
outside the region, leaving an excess of two $\mathcal{U}$-vertices in the
rest of the region. It is therefore not possible in a maximum matching.

Note that the results of the previous paragraph also hold for $8_{n}$-empires
with generic boundary conditions. Punctured $8_{n}$-empires admit a perfect
matching only when the unmatched components outside the outermost
$\mathcal{H}$ region are excluded, otherwise they typically host a few
monomers at their boundaries. While such monomers have a vanishing density in
the thermodynamic limit, our construction of pseudomembranes outlined above
does not carry over. However, when such an $8_{n}$-empire is embedded in a
larger system, the monomers at the boundaries are annihilated with other
monomers in a maximum matching (recall that AB tilings host perfect matchings
in the thermodynamic limit), and pseudomembranes appear.

In general, an $8_{n}$-empire hosts $n+2$ pseudomembranes concentric with the
$8$-vertex at the empire’s centre (including the membrane enclosing the
outermost $\mathcal{H}$ subregion and the eight edges incident to the
$8$-vertex). The $8_{n}$-empire also hosts smaller $8_{m}$-empires, and all
these empires host their own pseudomembranes, concentric with each empire’s
central 8-vertex. These $8$-vertices are necessarily of order $m<n$. Taken
together, the edges that make up the pseudomembranes of AB are those that form
the membranes of the AB∗ tiling, as described in Sec. IV.1.

###  IV.3 The effective matching problem

The full AB tiling exhibits a rich hierarchical structure of nested
pseudomembranes. Each pseudomembrane bounds a region (set of edges and
vertices) which acts as an _effective unit_ in the matching problem, such that
only one dimer connects the region to the rest of the graph. Motivated by
this, we define an $8_{n}$-unit to be the region bounded by the $n+2$-th
pseudomembrane from the centre of the local empire of any ($m>n$)
$8_{m}$-vertex. Note the $8_{n}$-unit coincides with the definition of the
$8_{n}$-empire, minus the components outside and including the outermost
pseudomembrane.

In the sense of Sec. III, the perfect matching problem can be seen as the
problem of matching up $8_{1}$-units, _mediated_ by the background of
perfectly matched ladder regions. This means that each $8_{1}$-unit matches to
a ladder (made up of non-8-vertices) with a single dimer (placed on the
pseudomembrane). The edges of this ladder in turn match to other
$8_{1}$-units. Similarly, based on the scale symmetry of the AB tilings, the
perfect matchings can be described by the matching up of $8_{n}$-units
mediated by _effective ladders_. Here we define an $n$-th order effective
ladder as a ladder built from $8_{n-1}$\- and $8_{n-2}$-units (so that the
effective ladder deflates to one of the ladders of Sec. IV.1 on the
$\mathcal{T}_{-2n}$ tiling). We dub these ‘effective matching problems’.

In Fig. 15, we display dimer occupation densities for the $8_{4}$-, $8_{2}$\-
and $8_{0}$-units to highlight the structures discussed in this section. The
data were obtained using Monte Carlo methods, as discussed in the next
section. The pseudomembranes appear as rings of edges with near-zero dimer
density, concentric with the centres of local $D_{8}$ symmetry. For the
$8_{4}$-unit we have highlighted the structures of the $2$nd order effective
ladders. The matching of the $8_{4}$-unit can therefore be seen from multiple
scales: as the matching of vertices on the basic $\mathcal{T}$ graph; as the
effective matching of $8_{0}$-vertices, mediated by the ladders of the AB∗
tiling; or of the effective matching of $8_{2}$-units, mediated by the $2$nd-
order effective ladders. The scale symmetry in the matching problem — where
effective units are matched at each scale of the tiling — hints at the
possibility for non-trivial signatures of the scale invariance in the dimer
and monomer correlations. We now proceed to explore this question numerically.

Figure 15: Left: Dimer occupation densities on an $8_{4}$-unit, a finite
$D_{8}$-symmetric patch of AB tiling. The region is bounded by the $6$-th
pseudomembrane. The lighter colours indicate a rich nested structure of
pseudomembranes associated with different $8$-vertices and their local
empires. The black lines emphasize the scale symmetry of the lattice (and
consequently maximum matchings): they denote sections of the larger AB-tilings
($\mathcal{T}_{-2}$ and $\mathcal{T}_{-4}$) composed of the $8_{2}$ and
$8_{0}$-units. Each $8_{n}$-vertex is surrounded by a pseudomembrane, and
hence connected to the rest of the graph by at most one dimer. They sit at the
vertices of a larger AB-tiling ($\mathcal{T}_{-n}$), and act as effective
units. Right: An $8_{0}$-unit (top) and an $8_{2}$-unit (bottom), with edges
coloured to indicate dimer-occupation densities.

##  V Numerical results on the AB tiling

In this section, we explore the correlations of the AB tiling via a numerical
study of the classical dimer model on finite patches of the AB tiling using
the directed-loop algorithm. Originally introduced to efficiently sample
space-time configurations using quantum Monte Carlo algorithms [96, 97, 17],
this method has been adapted to sample the configuration space of classical
dimer models and to access their monomer correlations [98, 41]. The algorithm
involves introducing two monomer defects into a maximum matching and
transporting one of the monomers around an alternating cycle until
annihilating it with its partner monomer (or with any other monomer, in graphs
not admitting perfect matchings). Since detailed balance is satisfied for
these intermediate configurations with two monomers, the corresponding
partition function can be sampled. This gives us access to monomer
correlations without additional computational effort. For completeness, we
review the algorithm in Appendix E.

###  V.1 Choice of samples and boundary conditions

Since quasiperiodic systems are not translationally invariant and do not admit
periodic boundary conditions, some care must be taken in choosing appropriate
finite patches for our numerical studies of the AB tiling. We consider finite
patches with exact $D_{8}$ symmetry. We anticipate that understanding matching
problems on such patches can yield results representative of an arbitrary
finite patch of AB tilings, since those are characterized by an effective
matching problem of $D_{8}$ empires. Additionally, every finite patch of
tiling is a part of a larger $D_{8}$ empire of the infinite tiling.

For our largest simulations we consider an $8_{4}$-unit. We use the
$8_{4}$-unit rather than the $8_{4}$-empire as the components of the empire
outside the largest pseudomembrane generate significant boundary effects. The
central $8$-unit has $6$ concentric pseudomembranes around it. As explained in
Sec. IV.2, in any perfect matching of the AB tiling, precisely one dimer
straddles the pseudomembrane to correlate the dimer configurations inside and
outside the region it encircles. Hence, it is reasonable to expect that
calculations of observables defined entirely inside a region enclosed by a
pseudomembrane will not be severely affected by the rest of the tiling even in
finite patches. With these modifications, the largest AB patch we consider
contains $15473$ vertices and $30136$ edges. In some cases, we consider a
smaller patch consisting of the $8_{2}$-unit. This sample contains $481$
vertices and $872$ edges. Below we present dimer and monomer correlations for
these finite patches. Note that all maximum matchings of these patches host a
single monomer with the charge of the central $8$-vertex. If the finite patch
were extended to the infinite tiling, this monomer would annihilate with an
oppositely charged monomer in another region, creating the single dimer
crossing the pseudomembrane. With this in mind, we also consider monomer
correlations on the charge-neutral punctured tilings, obtained from the above
patches by removing the central vertex. We will show that the two cases
(entire and punctured tilings) demonstrate qualitatively different behaviours
for the monomer correlations.

###  V.2 Dimer correlations

The dimer occupation densities are displayed in Fig. 15. Motivated by the
structure of effective matchings and the possibility of non-trivial long range
correlations, we investigate the connected correlations $C(e_{i},e_{j})$ of
dimers on edges $e_{1}$ and $e_{2}$, defined to be

$C(e_{i},e_{j})=\langle n(e_{i})n(e_{j})\rangle-\langle n(e_{i})\rangle\langle
n(e_{j})\rangle,$ (6)

where $n(e_{i})=1$ if the edge $e_{i}$ hosts a dimer, and $n(e_{i})=0$
otherwise. For the system sizes under consideration we find that connected
dimer correlations do not decay exponentially, as they would for either long-
range ordered or disordered dimer covers. Characterizing $C(e_{i},e_{j})$ is
complicated owing to its lack of translational invariance, and its high degree
of inhomogeneity. Fig. 2 shows the dimer-correlation function $C(e_{0},e_{j})$
for an edge $e_{0}$ which connects a $4$-vertex to a ladder (formed of
$2$-vertices).

To characterize the decay of correlations, we calculate $C_{\max}(e_{0},x)$:
the maximum value of $|C(e_{0},e_{j})|$ such that the edge $e_{j}$ has a graph
distance of $x$ edges from $e_{0}$. We display this quantity, computed for
seven different choices of $e_{0}$, in Fig. 16. We see a slow decay across the
system, consistent with power law asymptotic behaviour, cut-off only by the
boundaries of the sample. We conjecture that this slow power law is a
manifestation of the description in terms of the effective matching problems,
at all scales, in terms of $8_{n}$-vertices, mediated by the effective ladders
formed of $8_{n-2}$\- and $8_{n-1}-$units as described in Sec. IV.3. We
emphasize that these power-law-like correlations are neither homogeneous nor
translationally invariant, and are unrelated to the familiar power laws
appearing in bipartite lattices with a continuum Gaussian action. Not all
edges have dimer correlations which decay slowly across the whole system. In
general, different dimer correlation functions decay slowly until a cutoff
lengthscale, after which they rapidly fall off. The cutoff lengthscales are
set by the pseudomembranes. To gain an understanding of this, we look at the
dimer correlations within the basic star surrounding the 8-vertices. For a
dimer on one of the eight central membrane links, connected correlations
outside the star are identically zero.555This can be seen by checking that for
each choice of dimer connecting the central 8-vertex to the star, and the
dimer connecting the star to the rest of the tiling, there is exactly one
possible dimer configuration on the star itself. Combined with the discussion
of effective matching problems, this suggests that links on and inside the
$n$-th pseudomembrane have dimer correlations which are effectively cut off by
the $(n+1)$-th pseudomembrane. In a system of linear size $L$, we therefore
expect slowly decaying correlations over all scales, cut off by lengthscales
in the set $L,L/\delta_{S}^{2},L/\delta_{S}^{4}\ldots$ We confirmed this
numerically. For example, inside an $8_{2}$-unit, the edges connecting
$8_{0}$-units to $L_{1}$ ladders (i.e., inside the $3$-rd pseudomembrane) do
not have significant connected correlations outside the $8_{2}$-unit (bounded
by the $4$th pseudomembrane). Such correlations are displayed in Fig. 17. We
remark that the correlations outside the $8_{2}$-unit are significantly
reduced, but unlike an elementary star, they are not exactly zero; the analyis
of the elementary star presented above merely provides us with a guiding
principle to understand the cut-off lengthscales in the decay of dimer
correlations for larger regions.

Figure 16: Power law connected correlations of dimers for a $D_{8}$-symmetric
sample (an $8_{4}$-unit). For several edges $e_{0}$,
$C_{\mathrm{m}ax}(e_{0},x)$, the maximum absolute value of dimer correlations
at a graph distance of $x$ edges from $e_{0}$ has a slow decay consistent with
a power law. The apparent dip at $\log_{10}(x)\sim 2$ corresponds to effects
of the sample boundary. We have displayed several choices of $e_{0}$ in this
figure: $a$, $b$ and $c$ are edges between $8_{0}$-units and $L_{2}$ ladders;
$d$ is a edge between an $8_{0}$-unit and an $L_{3}$ ladder; $e$ is a edge on
an $L_{1}$ ladder; $f$ connects an $8_{2}$-unit to $L_{4}$; $g$ is a edge
between an $8_{2}$-unit and an $L_{1}$ ladder. A large-scale plot of the
tiling showing all the different source edges for this plot is provided in
Appendix F. Figure 17: Connected correlations of dimers for a
$D_{8}$-symmetric sample (an $8_{4}$-unit). In contrast to Fig. 16, for
several edges $e_{0}$, $C_{\mathrm{m}ax}(e_{0},x)$, the maximum absolute value
of dimer-correlations at a graph distance of $x$-edges from $e_{0}$, is
sizeable only inside the $8_{2}$-unit in which $e_{0}$ lies. In this figure,
we have chosen $e_{0}$ to be edges $a-h$, all connecting an $8_{0}$-unit to an
$L_{1}$ ladder, inside a larger $8_{2}$-unit. A large-scale plot of the tiling
showing all the different source edges for this plot is provided in Appendix
F.

###  V.3 Monomer correlations

Next we turn to monomer correlations. For bipartite graphs with perfect
matchings, the monomer correlation function is just the partition function
$Z(x,y)$ over dimer configurations, up to normalisation, with two oppositely
charged monomers situated on vertices $x$ and $y$. As noted in the section
introduction, the symmetric patches have an extra vertex in the bipartite
subset of the central 8-vertex. Without loss of generality we denote this
subset $\mathcal{U}$. To probe the physics associated with a single monomer
defect pair in maximum matchings, we first introduce an auxiliary partition
function $Z^{\prime}(x_{1},x_{2},y)$, having two $\mathcal{U}$-monomers on the
vertices $x_{1}$ and $x_{2}$ and a single $\mathcal{V}$-monomer at $y$. We
then define the two-particle correlation function as

$Z(x,y)=\sum_{x_{1},x_{2}}Z^{\prime}(x_{1},x_{2},y)(\delta_{x_{1},x}+\delta_{x_{2},x}),$
(7)

which calculates the pair correlation of oppositely charged monomers in a gas
of three monomers.

To understand the monomer correlations, it is useful to consider dynamical
processes like those in Fig. 3d applied to the three-monomer gas, where the
monomers ‘random-walk’ across even-length alternating paths by augmenting
them. As explained in Appendix. E, such processes can be designed to respect
detailed balance in the configuration space with three monomers (thereby
leading to a Monte Carlo scheme to computationally study such monomer
correlations). Consequently, they provide valuable insight into ensemble
averages in the three-monomer gas like the pair correlation functions. In the
rest of this section, we will use the term ‘random-walk’ to mean such
processes.

Without loss of generality, we consider the movement of $\mathcal{V}$-monomers
while the $\mathcal{U}$-monomers are held fixed. Fig. 2 shows a typical
profile for $Z(x,y)$, with $x$ fixed and $y$ allowed to vary. While the
structure of correlations $Z(x,y)$ varies considerably with the
$\mathcal{U}$-monomer position $x$, we observe two distinct features which
hold across all values of $x$:

  * •

$Z(x,y)$ is strongly peaked for $y$ within the first few pseudomembranes near
the central $8$-vertex, taking its maximum value on the eight $\mathcal{V}$
vertices neighbouring the central $8$-vertex. Minima reside on the eight
highest order $\mathcal{V}$-charged 8-vertices. Additional _local_ maxima
(minima) occur for $y$ around (on) the locations of $\mathcal{U}$-charged
($\mathcal{V}$-charged) 8-vertices. Sites around (on) higher order
$\mathcal{U}$-charged ($\mathcal{V}$-charged) 8-vertices are associated with
stronger maxima (minima) of $Z(x,y)$.

  * •

$Z(x,y)$ has comparable support around the entire angular range of the region,
and is not confined in the vicinity of the $\mathcal{U}$-monomer.

The first point describes a ‘charged’ attraction between the free
$\mathcal{V}$-monomer and the tiling’s 8-vertices, with the strength of the
interaction set by the order of the 8-vertex. By charged, we mean that the
$\mathcal{V}$-monomer has large correlations around the $\mathcal{U}$-charged
8-vertices (the central vertex being the highest order $\mathcal{U}$-charge in
the region), but small correlations on and around $\mathcal{V}$-charged
8-vertices. This can be understood from the properties of the (pseudo)
membranes. It is simplest to first understand the effect for exact membranes
around the central vertex (i.e. on the punctured tiling with the central
vertex removed). The $\mathcal{V}$-monomer acts as a random walker, and begins
its walk in some $\mathcal{H}_{i}$ region bounded by the two membranes
$\mathcal{M}_{i}$ and $\mathcal{M}_{i+1}$. No alternating path exists that
crosses $\mathcal{M}_{i+1}$ and also has an end point terminating on the
monomer. This follows from the arguments in Appendix D. Hence, the monomer’s
walk cannot cross the $\mathcal{M}_{i+1}$ membrane. Heading inward, however,
the monomer may cross $\mathcal{M}_{i}$ at any point $x_{i}$ on the membrane,
but may then only return to $\mathcal{H}_{i}$ by re-crosssing
$\mathcal{M}_{i}$ at the _same_ point. It may further cross the next membrane,
$\mathcal{M}_{i-1}$ at any $x_{i-1}$, but cannot come back unless it can
return to the same $x_{i-1}$. For large membranes, the monomer is effectively
‘trapped’ on the inward side (like a lobster in a pot). The net effect for
high-order 8-vertices is thus a large probability for the monomer to be found
near the centre.

Figure 18: A random walking $\mathcal{V}$-monomer feels a global attraction to
the central $\mathcal{U}$-charged 8-vertex on account of the membranes. The
monomer, moving inward, can cross a membrane $\mathcal{M}_{i}$ at any point
$x_{i}$, but then may only re-cross the membrane at the same point.

The reinstatement of the central vertex places a single dimer on each
pseudomembrane $\mathcal{M}_{i}$ at a position $x^{\prime}_{i}$. For large
patches, with the averaging described in Eq. 7, a $\mathcal{U}$ monomer is
likely to be found far from the centre, and so almost all pseudomembranes will
host a dimer. This dimer provides an additional path for the
$\mathcal{V}$-charged monomer to escape the trapping by pseudomembranes. That
is, once a $\mathcal{V}$ monomer crosses inward from $\mathcal{H}_{i}$ to
$\mathcal{H}_{i-1}$ through the pseudomembrane $\mathcal{M}_{i}$ at $x_{i}$,
it can re-cross either at $x_{i}$ or $x^{\prime}_{i}$. However, for large
membranes, this does not significantly affect the arguments for trapping of
monomers presented earlier. The existence of local maxima and minima of
monomer correlations across the tiling’s 8-vertices follows from the same
reasoning applied to the pseudomembranes of all 8-vertices. This directly
implies a high probability for the monomer to be found near the
$\mathcal{U}$-charged 8-vertices. For the $\mathcal{V}$-charged 8-vertices,
the effect is reversed. Now the monomer may only cross inward at the single
point where a dimer exists on the pseudomembrane, but it may cross outward at
any point along the pseudomembrane. Thus, a $\mathcal{V}$ monomer is trapped
by the $\mathcal{U}$-charged pseudomembranes, and blocked by the
$\mathcal{V}$-charged pseudomembranes. From the same argument, it is easy to
see that for a fixed position of the $V$-charged monomer $y$, a random-walking
$\mathcal{U}$ monomer is trapped by $\mathcal{V}$-charged pseudomembrane and
blocked by $\mathcal{U}$-charged pseudomembranes. This implies that $Z(x,y)$,
for fixed $y$, has local maxima (minima) for $x$ around (on)
$\mathcal{V}$-charged ($\mathcal{U}$-charged) $8$-vertices.

Higher order $8$-vertices, having more concentric pseudomembranes, result in
stronger maxima/minima on sites on or around them. The configuration with
largest pair correlation (consequently smallest free energy) corresponds to
the $\mathcal{V}$-monomer around the central $8$-vertex and the
$\mathcal{U}$-monomer around the highest order $\mathcal{V}$-charged 8-vertex.
The separation between the central $\mathcal{U}$-charged 8-vertex and the
highest order $\mathcal{V}$-vertex scales with the size of the sample, and
this implies that monomers have the lowest free energy when separated over
very large distances. Thus, monomers are radially ‘anti-confined’, in striking
contrast to familiar cases in periodic lattices where monomers are typically
either confined or deconfined.

The above mechanism effectively describes the behaviour of correlations in the
radial direction (towards the central vertex, and other 8-vertices as a sub-
leading effect). With this in mind, we ask how the correlation behaves at
large angular distances (around the central vertex) within a given
$\mathcal{H}_{i}$ region. $\mathcal{H}_{i}$ can be partitioned into eight
identical sectors (‘wedges’), each spanning an interior angle $2\pi/8$, which
we label by $\mathcal{S}_{n}$ for $n=0\ldots 7$. We fix $x$ in
$\mathcal{S}_{0}$ and ask how $Z(x,y)$ behaves for $y$ in $\mathcal{S}_{n}$
and large $n$ (by ‘large’, we mean the distance in sectors from
$\mathcal{S}_{0}$). On the Ammann-Beenker tiling the largest $n$ we have
access is $n=4$. However, we can artificially increase $n$ by inserting
additional symmetric wedges into the basic AB tiling. This allows us to probe
the large-$n$ limit without changing the basic physics. In Fig. 19 we display
the results for an effective $8_{4}$-unit extended to 13 sectors; this patch
is large enough to see clear asymptotic behaviour while remaining
computationally accessible. For each of the five $\mathcal{H}_{i}$ regions in
the effective $8_{4}$-unit, we plot $Z(x,y)$ averaged over all $x$ in
$\mathcal{S}_{0}$ and all $y$ in $\mathcal{S}_{n}$, for $n\leq 6$. In each
region we observe a distinct plateau to a _non-zero_ constant at large $n$.
This implies that, within a given $\mathcal{H}_{i}$ region, the free energy
cost to separate a monomer along the annular direction does not increase with
distance . We dub this effect ‘annular deconfinement’. Along with the charged
attraction to 8-vertices explained above, this completes our characterisation
of the structure of monomer correlations in the AB tiling.

Figure 19: Averaged correlation function for a $\mathcal{U}$-monomer at
position $x$ and a $\mathcal{V}$-monomer at $y$, both within a given
$\mathcal{H}_{i}$ region. $\langle Z(x,y)\rangle$ is averaged over $x$ in the
sector $\mathcal{S}_{0}$ and over $y$ in $\mathcal{S}_{n}$. On the extended
graph with 13 sectors (see main text), the furthest sector from
$\mathcal{S}_{0}$ corresponds to $n=6$. For every $\mathcal{H}_{i}$ region,
$\langle Z(x,y)\rangle$ decays to a _finite_ constant at large $n$, signifying
annular deconfinement of the monomers. _Inset:_ on the punctured tiling with
the central vertex removed, star-like ($i$ even) $\mathcal{H}_{i}$ regions
remain deconfined, while ladder-like ($i$ odd) are _confined_ , decaying
exponentially to zero at large $n$. The log scale on the inset $y$-axis is set
by $\alpha=\frac{1}{2+\sqrt{3}}$

.

It is interesting to contrast this behaviour to the monomer-monomer
correlations for the punctured tiling, the inset to Fig. 19. Here we see that
the correlations for the _ladder_ -like regions ($i$ odd) $\mathcal{H}_{1}$
and $\mathcal{H}_{3}$ now decay exponentially with the sector distance $n$,
whereas those of the star-like ($i$ even) regions again plateau to a finite
constant. In fact, a transfer matrix calculation for the $\mathcal{H}_{1}$
region requires that at large $n$, the leading behaviour of the correlation
function goes as

$Z_{1}(x,y)\propto\bigg{(}\frac{1}{2+\sqrt{3}}\bigg{)}^{n}.$ (8)

The effective matching problems (recall all odd-$i$ $\mathcal{H}_{i}$ form
ladders of effective $8_{i-2}$-units) suggest that analogous behaviour should
emerge for the $\mathcal{H}_{3}$ region, and all other ladder-like region.
This statement is supported by the near-identical exponential fit of
$\mathcal{H}_{3}$ in the inset of Fig. 19. However, once the central 8-vertex
is reinstated, this large-$n$ ‘confinement’ of the ladder-like regions on the
punctured tilings is fragile to the deconfinement of the star-like regions. On
the punctured tilings the $\mathcal{H}_{i}$ regions are bounded by two exact
membranes $\mathcal{M}_{i}$ and $\mathcal{M}_{i+1}$, and monomer correlations
within the region $\mathcal{H}_{i}$ can be described by considering the
$\mathcal{V}$-monomer to be confined within the $\mathcal{H}_{i}$ region. Note
that the $\mathcal{V}$-monomer can indeed cross $\mathcal{M}_{i}$ to escape to
the region $\mathcal{H}_{i-1}$, but since it can only cross back through the
same point, its excursion outside $\mathcal{H}_{i}$ does not contribute to
monomer correlations within $\mathcal{H}_{i}$. The reinstatement of the
central vertex places a dimer on each of the membranes, meaning the monomer
can now take paths that cross one of the pseudomembranes at one point $x$, and
re-cross at another point $x^{\prime}$. For a monomer starting and ending its
path in a ladder-like region, these paths provide a mechanism to
deconfinement: the monomer takes a path which crosses over to a neighbouring
star-like region, where it is annularly deconfined, only crossing back over
near the end of the path. On the entire tiling, the monomer can therefore find
deconfining paths between all points starting and ending in the same
$\mathcal{H}_{i}$ region.

###  V.4 Aligning Interactions

Figure 20: The intensive specific heat, $C^{m}_{v}/N_{m}$, of an
$m^{\textrm{th}}$-order ladder with aligning interactions, as a function of
the temperature $T$. Lines denote transfer matrix calculations, whereas the
points represent data obtained from Monte Carlo simulations. _Left_ : When
$V<0$, the intensive specific heat has a broad feature independent of the
ladder size, associated with a crossover to columnar states. _Right_ : When
$V>0$, the ladders exhibit a sharp feature in the intensive specific heat,
which scales with the number of edges in a ladder (shown in inset).  Figure
21: The intensive specific heat, $C_{v}/N$ of finite AB patches with aligning
interactions, as a function of the temperature $T$. _Left_ : When $V<0$, the
crossover to columnar states on the ladders is associated with a broad feature
which does not scale with the size of the tiling. _Right_ : For $V>0$, the
sharp peak seen in the case of the ladders in Fig. 20 is significantly
broadened here. _Inset_ : $\sigma_{N_{f}}/N$ (Eq. (11)), indicating
fluctuations in the number of flippable plaquettes, has a broad feature which
indicates a crossover to staggered states on the ladders.

Finally, we briefly discuss the role of aligning interactions. To explore the
possibility of ordered dimer phases and their associated transitions in the
absence of periodic lattice symmetries, we consider a classical model defined
by the energy function

(9)

where the sum is taken over all plaquettes $\square$ (the four edges
comprising a square or rhombus tile of AB). The potential $V$ either favours
(negative sign) or disfavours (positive sign) the presence of ‘flippable’
plaquettes which host a pair of parallel dimers. Our energy function can be
understood as the classical limit of the quantum Rokhsar-Kivelson Hamiltonian
[10], with the kinetic term set to zero. Working entirely within the manifold
of maximum matchings, the partition function is weighted according to

$\displaystyle Z=\sum_{\mathcal{C}}e^{-VN_{F}(\mathcal{C})/T},$ (10)

where $N_{F}(\mathcal{C})$ counts the number of flippable plaquettes in a
dimer configuration $\mathcal{C}$. $T$ is a temperature that we introduce for
convenience. Only the combination $V/T$ has physical significance. Regardless
of sign, a non-zero value stabilizes ordered phases which break lattice
symmetries.

To orient the discussion, first consider the effect of aligning interactions
on the ladders which make up the AB∗ tiling. Negative $V$ favours the
maximally flippable columnar states on the ladders, while positive $V$ favours
the two staggered states, which are in topologically distinct sectors. That
is, each staggered state cannot be reached from any other state by a sequence
of local plaquette flips. These ladders can be treated exactly using the
transfer matrix approach, as described in App. C.

We calculate the intensive specific heat for an $m^{\textrm{th}}$-order ladder
with $N_{m}$ edges (this is obtained by taking derivatives of the free energy
in the usual way). We show the result in Fig. 20. For $V<0$, the intensive
specific heat exhibits a broad peak which does not scale with the size of the
ladder. This feature corresponds to the loss of entropy incurred in the
crossover to the columnar state. Each ladder has a macroscopically degenerate
number of columnar ground states — in the language of App. B, each $A$ segment
contributes two states while each $B$ segment contributes three. When $V>0$,
the intensive specific heat has a sharp feature at $T/V\approx 1.0$,
signalling the onset of staggered states in the ladders. As shown in the inset
of Fig. 20, $C^{m}_{V}/N_{m}\sim N_{m}$. This conventionally signals a first-
order phase transition, though the latter term should be used cautiously since
one can only take a particular sequence of $N_{m}$. Note, however, that this
does not drive a first-order transition in the AB∗ tiling, since any
thermodynamic singularity is suppressed by the exponential decay in the
density of ladders with their order $m$.

We now compute the intensive specific heat $c_{v}=C_{v}/N$ of AB patches with
$N$ edges (Fig. 21) using Monte Carlo simulations. As in the case of the AB∗
ladders, for $V<0$, $c_{v}$ has a broad feature at $T/V\approx 0.5$ which
corresponds to the onset of columnar-like configurations on the ladders. On
AB, dimer correlations are no longer restricted to ladders, but since the
ladders host most of the flippable plaquettes, tuning $V$ enhances the role of
the ladders even in this case. However, when $V>0$, the sharp feature
associated with the transition to the staggered states at $T/V\approx 1$ in
the AB∗ ladders (Fig. 20) is no longer present in the AB patches.

We calculate the standard deviation $\sigma_{N_{F}}$ of the number of
flippable plaquettes $N_{F}$ as

$\displaystyle\sigma_{N_{F}}=(\langle N_{F}^{2}\rangle-\langle
N_{F}\rangle^{2}).$ (11)

The results are displayed in the inset of Fig. 21. We see that
$\sigma_{N_{F}}/N$ exhibits a broad feature at $T\approx 1$, which suggests
that the dimers settle into configurations resembling staggered states on the
ladders without undergoing a phase transition.

Figure 22: Dimer densities on an AB patch ($8_{2}$-vertex) with aligning
interactions. _Top_ : at $T/V=-1/3$, the dimer densities reveal a strong
tendency to align along the legs of the ladders, indicating that staggered
configurations on the ladders are favoured. _Bottom_ : at $T/V=1/3$, the
dimers tend to align along the rungs of the ladders, indicating that columnar
states on the ladders are favoured.

Fig. 22 shows the dimer densities of an AB patch in the presence of aligning
interactions of both signs. We see that at large negative values of $V$ the
dimers align along the rungs of the ladders, while at large positive values of
$V$ the dimers align along the legs of the ladders. This suggests that typical
dimer configurations of the full AB tiling in these limits can be described in
terms of the cartoons of columnar and staggered states on the ladders.

##  VI Conclusions

We have demonstrated that classical dimers on the AB tiling admit perfect
matchings in the thermodynamic limit, with a rich structure linked to the
interplay of constraints with quasiperiodicity. A crucial feature of our
analysis is the identification of collections of edges whose dimer content can
be strictly bounded from above in any maximum matching. Previous work on the
Penrose tiling identified exact membranes, sets of edges that host zero dimers
in maximum matchings, separating regions hosting monomers with distinct
bipartite charge [61]. The present work extends this analysis in two ways.
First, we identified exact membranes on the auxiliary quasiperiodic AB∗ tiling
obtained by deleting $8$-vertices from the AB tiling. These membranes can be
understood in terms of the fine Dulmage-Mendelsohn decomposition of a
bipartite graph, reviewed in Appendix A. Second, returning to the full AB
tiling by replacing the $8$-vertices, we found that membranes become
_pseudomembranes_ , sets of edges that collectively host precisely one dimer
in any perfect matching.

The pseudomembrane structure of AB implies the existence of ‘effective
matching problems’ at every scale of the quasiperiodic tiling. Effective units
bounded by pseudomembranes are matched together in the same way as the basic
graph vertices, with a hard-core dimer constraint imposed by the
pseudomembranes. This scale invariance leads to long-ranged, anisotropic, and
site-dependent connected dimer correlations with a series of cut-off scales,
which we found evidence for using classical Monte Carlo simulations. Monomer
statistics are likewise dominated by the tiling’s pseudomembranes. In contrast
to familiar cases, e.g. monomer correlations on the periodic square tiling,
where a pair of oppositely charged monomers are confined by the pair
separation, on the AB tiling a neighbouring pair of test-monomers reach their
lowest free energy for very large separations (of the order of the system
size). Along with this radial anti-confinement, we also observe annular
deconfinement around the 8-vertices. Our results on dimer and monomer
correlations place the behaviour of the dimer model on AB tilings in sharp
contrast to familiar examples of dimer models of bipartite periodic graphs,
where both dimer correlations (either algebraic or short-range) and test-
monomer correlations (confining) are translationally invariant and isotropic,
like the coarse-grained continuum height action which describes these systems.
From the correlations discussed above, it is unlikely that the dimer model on
AB tilings have such a description. Putting the connection between the
effective matching problems and the underlying statistics on a firm
quantitative basis is an important future direction.

The existence of perfect dimer matchings on the AB tiling in the thermodynamic
limit is also distinguished from the situation in other two-dimensional
quasicrystals [61]. There are six minimal quasicrystals in two dimensions as
identified in the classification scheme of Ref. 89. All vertices of the
Penrose tiling belong to regions of one or other excess bipartite charge. The
oppositely charged regions are separated by exact membranes. These are the
prototypes for the AB pseudomembranes in the present study. In some sense,
however, it is the lack of perfectly matched regions which makes the Penrose
tiling unique, just as it is the absence of unmatched regions which makes AB
unique. The remaining four 2D quasicrystals contain regions with an excess of
one or the other bipartite charge alongside perfectly matched regions. The
division between different regions is always formed by sets of edges which
cannot host dimers in maximum matchings. Other graph decorations of the tiles
can change these results. In the tiling literature such decorations are said
to give ‘mutually locally derivable’ (MLD) tilings [64]. For example, it is
possible to define a tiling MLD to the rhombic Penrose tiling which can be
perfectly matched [61]. Such special cases aside, however, the remaining
minimal quasicrystals, while still quasiperiodic and long-range ordered, begin
to approach the generic results found in random or disordered bipartite graphs
with two-dimensional embeddings [66, 67, 68]. It is in this context that the
results in the present study truly stand out.

Turning to the more thorny issue of quantum fluctuations, the existence of
columnar and staggered states for opposing signs of the alignment potential
suggests that upon including dimer resonance moves, the phase diagram of
quantum dimers on quasicrystals will resemble the Rokshar-Kivelson picture for
periodic lattices [10, 7]. Therefore we anticipate the existence of at least a
point in the quantum dimer phase diagram, between the columnar and staggered
limits, where equal-time dimer correlations resemble those of the classical
models studied in this work. However, whether this point requires fine tuning,
or instead represents the properties of a robust phase of matter, is a more
delicate question. Historically, studies of dimer models on periodic bipartite
lattices have made use of the height representation [99, 28]; in the quantum
case, the height action must be supplemented by instanton contributions linked
to the integer-valued nature of the height field. Instantons destroy the long-
range quantum dimer correlations in two spatial dimensions, rendering them
exponentially short-ranged. In essence, this is Polyakov’s argument for the
absence of a deconfined phase of $U(1)$ quantum lattice gauge theories in
three spacetime dimensions [100]. This means that the power law correlations
of the RK model require the fine-tuning characteristic of a multicritical
point rather than the stability of a robust phase. The situation is less clear
in the present case since, as we have noted above, there does not seem to be
an obvious local height action that characterizes maximally probable dimer
configurations on quasicrystals. In fact, the anisotropic and site-dependent
nature of dimer and monomer correlations strongly suggest the absence of any
local, isotropic and translationally invariant action of coarse-grained fields
which describe our system. Therefore, Polyakov’s arguments do not apply
directly, and as we have seen, the notions of confinement and deconfinement
become richer and subtler. Consequently there is a possibility that long-
wavelength dimer correlations persist in the quantum problem. Verifying this
is challenging, since in order to make precise statements one must approach
the thermodynamic limit via a discrete sequence of inflations, and we are
forced by quasiperiodicity to work with open boundary conditions. This means
that the relevant computational cost likely becomes prohibitive before finite-
size effects have been suppressed. In light of this, further study of the
classical problem to determine if there is a convenient, possibly non-local,
characterization of maximally probable dimer configurations seems warranted,
as this might open a route to an analytical treatment.

A more numerically tractable direction is to explore dimer models on the
$D_{8}$-symmetric ladders introduced in the context of the AB∗ tiling in App.
C. Recall that each of the eight symmetry-related segments of the ladder forms
a system which tends to quasiperiodicity in the thermodynamic limit in its own
right. This presents an interesting avenue for investigating quasiperiodic
quantum dimer ladders. Periodic ladders, and closely associated frustrated
spin ladders, have long been studied to shed light on the phases and
transitions of quantum dimers [101, 102, 103, 104, 105, 106]. We expect
studies of quasiperiodic ladders to be similarly fruitful.

On a given bipartite graph there is a well-established mapping between
monomers in dimer matchings, and localised electronic zero-energy modes in
tight-binding models [107, 108, 66]. Here, the number of monomers hosted in a
maximum matching is associated with the number of zero modes, while the
monomer-confining regions are associated with wave functions whose support is
confined within a compact subgraph. The computed monomer densities and
geometry of monomer-confining regions on the Penrose tiling [61] are
consistent with the density of zero modes and the nature of confined states
obtained from investigations of hopping problems on the Penrose tiling [109,
110, 111]. Ref. 74 recently computed a finite density of confined zero modes
on the AB tiling; naively, this appears to be in conflict with our results
that demonstrate that the AB tiling can be perfectly matched with vanishing
monomer density in the thermodynamic limit. This apparent contradiction may be
resolved by noting that the zero modes obtained in Ref. [74] are ‘fragile’, in
the sense that they move away from zero energy upon the introduction of
arbitrarily weak disorder in the hopping matrix elements. In contrast, the
Penrose tiling hosts ‘strong’ zero modes that survive to any disorder
strength. Formally, the monomer density computed in the dimer cover problem
exactly equals the density of strong zero modes, but is not linked to the
density of fragile zero modes. The fragility of the AB zero modes may be
explicitly verified by computing the spectrum of the random-hopping problem:
for any nonzero randomness, exactly one zero mode from Ref. [74] survives (the
strong mode associated with the unavoidable central monomer on 8-fold
symmetric patches), with all the remaining modes moving to finite energy.

Finally, we comment on a relationship between the ideas explored in this paper
and fracton phases of matter [112, 113, 114, 115, 116, 117, 118]. The latter
are usually defined on translationally invariant lattices, and blend
topological features with sensitivity to geometry. Type-I fracton phases host
quasiparticle excitations which cannot move individually, but which can
combine into pairs or quadruplets to move along lines or planes. There is a
passing resemblance to the membranes in AB∗, in which the minimum excitation
out of a perfect matching would be the deletion of a single dimer, creating a
monomer-antimonomer pair. Membranes restrict each individual monomer to move
on a subset of vertices of the same bipartite charge. But the pair together is
free to move anywhere, with one or other monomer ‘opening a door’ through a
membrane which the other closes. However, a key feature of mobile fracton
pairs is that their separation is fixed, while the monomer pair has no such
constraint. Very recent work [119] has extended the duality between fractons
and elasticity theory [120] to quasicrystalline systems, but as yet it is
unclear whether this has direct implications for the results presented here.
In type-II fracton phases the excitations can only move along fractal subsets
of the full system. Loosely speaking, they are an instance where a complicated
set of gauge constraints on a simple lattice leads to emergent low-energy
behaviour in which the natural gauge-charged objects are fractals. Contrast
this with the present example, where a conventional Gauss-law-like structure
(imposed by the dimer constraint) leads to a setting where ‘gauge lines’ are
themselves subject to fractal — and fractally distributed — barriers. It seems
therefore that the study of dimer models on quasicrystals presents an
intriguing counterpoint to fractons. In future, it will be interesting to
explore whether properties such as unusual topological robustness at finite
temperature and glassy dynamics characteristic of fractonic phases also emerge
in the quasiperiodic dimer setting.

###### Acknowledgements.

We thank Kedar Damle, Paul Fendley, and Shivaji Sondhi for insightful
discussions. J.L. and F.F. acknowledge the advice, support, and encouragement
of Uwe Grimm throughout this work, which we dedicate to his memory. We
acknowledge support from the European Research Council under the European
Union Horizon 2020 Research and Innovation Programme via Grant Agreement No.
804213-TMCS (S.A.P., S.B.), and EPSRC Grant EP/S020527/1 (S.A.P., S.H.S.). F.
F. acknowledges support from the Astor Junior Research Fellowship of New
College, Oxford. J. L. acknowledges support from the Ogden Trust. Statement of
compliance with EPSRC policy framework on research data: This publication is
theoretical work that does not require supporting research data.

##  Appendix A Membranes in perfectly matched bipartite graphs

Here, we provide a graph-theoretic picture of how perfect matchings on a
bipartite graph decouples into perfectly matched regions separated by
membranes. These regions are such, that in all perfect matchings, vertices in
each region are matched to sites within the same region. Further, edges
constituting membranes which separate these regions are never matched in any
perfect matching. It turns out that these regions are precisely the components
of the ‘fine’ version of the Dulmage-Mendelsohn decomposition of bipartite
graph theory[68], well known in computer science and computational graph
theory [67, 68, irving06, 69]. As we will describe below, the literature also
provides us with computationally efficient methods to determine these regions.

We note that in general bipartite graphs a maximum matching is not necessarily
perfect. In general, such maximum matchings decouple into regions which host
monomers in addition to perfectly matched regions and membranes [61, 66].
These regions also turn out to be components of a more general Dulmage-
Mendelsohn decomposition, involving monomer carrying regions. However, this
does not directly concern us in the context of AB tilings, and we will focus
on the special case of perfectly matched graphs.

Consider a bipartite graph $G$ with a perfect matching, with the bipartite
subsets denoted by $\mathcal{U}$ and $\mathcal{V}$. Given a perfect matching
$\mathcal{M}$, any other perfect matching $\mathcal{N}$ can be reached by
flipping the dimer-occupancy states on some set of alternating cycles on the
graph. One can see this by first constructing the symmetric difference
$M\oplus N$. $M\oplus N$ consists of edges which are matched in either
$\mathcal{M}$ or $\mathcal{N}$, but not both. It is easy to see that $M\oplus
N$ decomposes into cycles. By construction, these cycles are alternating
cycles in $\mathcal{M}$. Starting with $\mathcal{M}$, flipping the dimer-
occupancies on these alternating cycles gives us $\mathcal{N}$. The preceding
arguments bring alternating cycles to the centre stage in our discussions on
the finer structure of perfect matchings of bipartite graphs. Loosely
speaking, the perfectly matched regions are the ones into which alternating
cycles localize, while the membranes are edges through which no alternating
cycles pass (such that they are not matched in any perfect matching).

Let us formalize this intuition to define these regions precisely. First,
consider an equivalence relation on the vertices of a graph. Given a maximum
matching $\mathcal{M}$, two vertices $v_{a}$ and $v_{b}$ are related if there
is an alternating loop going through both $v_{a}$ and $v_{b}$. This is an
equivalence relation on the vertices, and therefore it divides up the vertices
into equivalence classes $V_{i}$. The vertices in the class $V_{i}$ along with
the edges which have both vertices in $V_{i}$ define a subgraph $G_{i}$. The
$G_{i}$s precisely describe the regions we are interested in— all vertices in
$G_{i}$ are perfectly matched within $G_{i}$ for all perfect matchings of the
graph $G$. Edges which do not belong to any of these $G_{i}$ constitute the
membranes— these edges are not a part of any alternating cycle, and
consequently do not host a dimer in any perfect matching.

We now turn to the algorithmic determination of these regions [68]. It is
convenient to construct an auxiliary directed graph $G_{d}$. To construct
$G_{d}$, given a perfect matching $\mathcal{M}$ in the graph $G$, we first
direct all unmatched edges from $\mathcal{U}$-vertices to the
$\mathcal{V}$-vertices. Then all matched edges are collapsed to a single
vertex, labelled by the $\mathcal{U}$-site. This specifies the directed graph
$G_{d}$, with vertices labelled by $\mathcal{U}$-vertices. By construction,
alternating cycles of $G$ are now directed cycles of $G_{d}$. This recasting
frames the problem in terms of a standard one: determination of “strongly
connected components” of a directed graph. Two vertices $v_{a}$ and $v_{b}$ of
a directed graph are strongly connected if there exist a directed path from
$v_{a}$ to $v_{b}$, and another directed path from $v_{b}$ to $v_{a}$. Strong
connection defines an equivalence relation, and the corresponding equivalence
classes define the strongly connected components. Standard algorithms, such as
ones by Tarjan [121] and Kosaraju [122] can efficiently solve the problem of
determination of strongly connected components of a bipartite graph.

Finally, we briefly outline an alternative, but illuminating, view of the
problem in terms of block-triangular factorisation (BTF) of matrices, which
was the initial context in which many of the above ideas were introduced [68].
A bipartite graph can be represented by a matrix $G$ with rows denoting one
bipartite subset $\mathcal{U}$, and columns denoting the other subset
$\mathcal{V}$. An edge between an $\mathcal{U}$-vertex $i$ and a
$\mathcal{V}$-vertex $j$ corresponds to a nonzero value of the element
$G_{ij}$. For our purposes, the actual numerical value of $G_{ij}$ is not
important, but it may encode other information like the weights of edges in a
weighted matching problem. Readers may be more familiar with the graph
adjacency matrix $\mathcal{A}$, a square matrix labelled by vertices of the
graph, and whose nonzero entries correspond to edges. In terms of $G$, the
adjacency matrix is

$\mathcal{A}=\left(\begin{array}[]{cc}0&G\\\ G^{T}&0\end{array}\right).$ (12)

The decoupling of the graph into perfectly matched regions and membranes can
also be viewed as a block-triangular factorisation (BTF) of the matrix $G$,
achieved by a permutation of its rows and columns. Such a BTF is of the
general form

$\displaystyle G=\left(\begin{matrix}G_{1}&M_{12}&\ldots&M_{1n}\\\
0&G_{2}&\ldots&M_{2n}\\\ \vdots&\vdots&\ddots&\vdots\\\ 0&0&0&G_{n}\\\
\end{matrix}\right).$ (13)

The diagonal blocks $G_{i}$ are square matrices which denote the perfectly
matched regions, while the off-diagonal blocks $M_{ij}$ denote the edges which
make up membranes. This can be easily seen. Consider the first diagonal block
$G_{1}$. First note that the $\mathcal{U}$-vertices in $G_{1}$ must match to
the $\mathcal{V}$-vertices in $G_{1}$ because we know that $G$ is perfectly
matched and the $\mathcal{V}$-vertices in $G_{1}$ have no neighbours outside
of the $\mathcal{U}$-sites in $G_{1}$. This implies that the edges in the
blocks $M_{11}\cdots M_{1n}$ are never matched in a perfect matching, i.e.,
they constitute membranes. With the $\mathcal{U}$-vertices in $G_{1}$ used up,
the $\mathcal{V}$-vertices in $G_{2}$ must all match to $\mathcal{U}$-vertices
in $G_{2}$, implying that the edges in $M_{23}\cdots M_{2n}$ constitute
membranes. This argument can be continued to show that sites in the regions
$G_{i}$ are perfectly matched to sites in the same region, while edges in
$M_{ij}$ are never matched in any perfect matching. Of course, the BTF
ultimately depends on the graph, and it might happen that no such BTF is
possible for certain graphs, or more precisely the BTF corresponds to a single
diagonal block encompassing the whole graph.

##  Appendix B Inflation structure of ladders on the AB∗ tiling

Figure 23: The inflation of the ladder tiles in Fig. 11. We distinguish three
distinct units that build the stars and ladders of the AB∗ tiling: $P$, $A$,
and $B$. White space separating segments represents impermeable membranes.
Denoting the three different tile environments that appear in any segment as
$S$, $R$, and $R^{\prime}$, we have $A=SRS$, $B=SR^{\prime}R^{2}R^{\prime}S$.
The segments are marked on the tiles by coloured arcs of internal angles
$\frac{\pi}{4}$, $\frac{\pi}{4}$, $\frac{\pi}{2}$ for segments $P$, $A$, $B$
respectively, which retain the symmetry of the original segment.

As explained in Sec. IV, the structure of AB∗ is composed of stars, ladders
and membranes. The AB inflation rule $\sigma$ implies an inflation rule,
displayed in Fig. 23, for the ladder tiles of Fig. 11 (technically, to perform
inflation on AB∗, the inflation is performed on the AB tiling and then the
$8$-vertices are once again removed, mapping back to AB∗). Rather than work at
the level of the tiles, we distinguish three repeating units: the basic 2-edge
unit of the star, which we label $P$ (shaded green); a ladder segment with the
structure $SRS$ (square-rhombus-square), which we label as $A$ (shaded light
blue); and a ladder segment with the structure $SR^{\prime}RRR^{\prime}S$,
which we label $B$ (shaded yellow). Each unit connects at its two end-points
with other units, forming longer segments. We note the basic rhombus tile can
appear in two distinct environments ($R$ and $R^{\prime}$): the $R$ rhombi
appear in the $A$ segment or in the centre of the $B$ segment, and have a
single vertex which only has edges to two other vertices in the ladder; the
$R^{\prime}$ rhombi appear sandwiched between $S$ and $R$ in $B$. (Viewing
each ladder as a graph, the $R^{\prime}$ environment is equivalent to the $S$
environment in the way in which it connects to neighbouring tiles, and this
identification is used in defining the transfer matrices for enumerating
matchings, Eq. C.) We denote a tile or segment $T$ repeated consecutively $n$
times as $T^{n}$.

From Fig. 23 we can read off the inflation of the segments:

$P\rightarrow A,\hskip 8.5359ptA\rightarrow{B}^{1/2}A{B}^{1/2},\hskip
8.5359ptB\rightarrow{B}^{1/2}A^{4}{B}^{1/2}.$ (14)

Although a one-to-one identification creates fractional-power $B$ segments,
two of these always join to form a whole segment: $(B^{1/2})^{2}=B$. We are
free to shift our inflation rule by $B^{1/2}$ to the right, obtaining the more
convenient form

$\xi\ \hskip 14.22636pt:\hskip 14.22636ptP\rightarrow A,\hskip
14.22636ptA\rightarrow AB,\hskip 14.22636ptB\rightarrow A^{4}B.$ (15)

A 1D inflation rule $\xi$ over the three-letter666Since $P$ never occurs after
the first inflation the alphabet is effectively two-letter. ‘alphabet’
$(P,A,B)$ is then obtained if we further define

$\xi(MN)=\xi(M)\xi(N)$ (16)

for any ‘words’ $M,N$. Due to the invertibility of $\sigma$, the inverse of
$\xi$ must also exist: we denote it $\xi^{-1}$. The 2D inflation $\sigma$ is
therefore reduced to an effective 1D inflation $\xi$ on the ladders forming
the AB∗ tiling.

The $P$ segments always close into isolated stars with $D_{8}$ symmetry, i.e.
$P^{8}$ (with periodic boundary conditions). Each ladder either closes in a
loop or spans the entire tiling — this follows by noting from the
configurations in Fig. 12 that ladders cannot branch or terminate in the
tiling. Additionally, if a ladder closes, it does so with $D_{8}$ symmetry. To
see this, observe that the inflation of the ladder tiles (Fig. 23) preserves
the symmetry of the segments. Then, given a closed ladder loop, repeated
deflation must eventually result in a loop containing $P$ segments, since
$\xi^{-1}$ only destroys $P$s. It follows that ladders can only close with
$D_{8}$ symmetry.

The possibility of a system-spanning ladder on the infinite tiling is evident
by considering the case of repeated inflation of any single segment; the
infinite ladder is obtained in the limit. The possibility of _multiple_ system
spanning ladders is more interesting. Similar curves to those in Fig. 23 can
be used to decorate the tiles of the Penrose tiling; in that case, Penrose and
Conway have independently shown that at most two system-spanning curves can
exist in a tiling [123]. We expect that a similar statement holds for the
Ammann-Beenker tiling. Such infinite ladders are very rare in any case — from
the LI property of AB, any finite patch of tiling can be taken to lie inside a
closed ladder of large enough extent, wherein all ladders must close. The
existence of these rare ladders will have negligible effect on the matching
problem, and in the main text we assume all ladders are closed with $D_{8}$
symmetry.

With the terminology of Sec. IV.1, we define the star, $P^{8}$, to be the
order-0 ladder, set $A_{0}\equiv P$, and henceforth phrase our discussion in
terms of ladders of order $n\geq 0$ according to the inflation hierarchy. With
the $D_{8}$ symmetry constraint, and assuming periodic boundary conditions, we
obtain the structure of the order-$n$ ladder as

$L_{n}=(\xi^{n}(A_{0}))^{8}\equiv A_{n}^{8}.$ (17)

Thus the order-1 ladder corresponds to $A^{8}$, the order-2 ladder to
$(AB)^{8}$, the order-3 ladder to $(ABA^{4}B)^{8}$, and so on.

The order-$n$ ladders are fractal structures in the limit
$n\rightarrow\infty$, and their fractal dimension can be derived from the
preceding inflation rules. Denoting the number of $A$ ($B$) segments in an
order-$n$ ladder as $\alpha_{n}$ ($\beta_{n}$), the growth under $\xi$ is
specified by the inflation matrix,

$\begin{pmatrix}\alpha_{n+1}\\\ \beta_{n+1}\end{pmatrix}=\begin{pmatrix}1&4\\\
1&1\end{pmatrix}\begin{pmatrix}\alpha_{n}\\\ \beta_{n}\end{pmatrix}.$ (18)

The largest eigenvalue of this matrix is 3, and so the number of both $A$ and
$B$ segments in a ladder grows by 3 under inflation, in the above limit. It
would appear to follow that the length of a ladder likewise increases by a
factor of 3 under inflation. However, there is a subtlety here in the fact
that the orientations of $A$ and $B$ segments are _reversed_ under a single
inflation; this is easily resolved by considering the action under $\xi^{2}$.
Then the length of a ladder increases by a factor of 9, whereas all edge
lengths are scaled by the silver ratio $\delta_{S}^{2}$. The (box-counting)
fractal dimension $d_{F}$ of the ladders is then found by setting
$(\delta_{S}^{2})^{d_{F}}=9$, from which

$d_{F}=\frac{1}{\log_{3}\delta_{S}}\approx 1.246\ldots$ (19)

This is similar to the case on the Penrose tiling, where the membranes were
found to have fractal dimension $1/\log_{2}\varphi$ [61], where $\varphi$ is
the golden ratio.

The statement that an $8_{n}$-vertex is the centre of concentric ladders of
orders $0\leq m\leq n$ follows from the fact that all $8_{0}$-vertices are
enclosed by stars, and an order-$n$ ladder inflates from a star. Consequently,
the number of ladders at a given order $n$ is in one-to-one correspondence
with the number of $8$-vertices of order $m\geq n$. This in turn can be
computed by counting the number of all $8$-vertices on the tiling obtained by
deflating $n$ times. Given a tiling with $N$ vertices, for $N$ large, the
$n$-fold deflated tiling has $\sim N/\delta_{S}^{2n}$ vertices, a fraction
$1/\delta_{S}^{4}$ of which are $8$-vertices. These statements become exact as
$N\to\infty$. Combining these results, we see that the number
$\mathcal{N}_{n}$ of order-$n$ ladders on an $N$-site tiling is given by

$\mathcal{N}_{n}\equiv\nu_{n}N\hskip 14.22636pt\text{with}\hskip
14.22636pt\nu_{n}\to\frac{1}{\delta_{S}^{4+2n}}\text{ as }{N\to\infty}.$ (20)

Here, $\nu_{n}$ is the frequency of order-$n$ ladders, equal to the sum of
frequencies of $8_{m}$-vertices for $m\geq n$ (so $\nu_{0}\equiv\nu_{v8}$ in
the notation of section III). Note that $N$ refers here to the number of
vertices on the ‘parent’ AB tiling; the number of vertices on the AB∗ tiling
is given by eliminating the $N/\delta_{S}^{4}$ 8-vertices, with

$\lim_{N\to\infty}N_{*}=N(1-\delta_{S}^{-4}).$ (21)

##  Appendix C Statistical mechanics of the AB∗ tiling: transfer matrix
calculations

We consider the statistical mechanics of perfect matchings of the AB∗ tiling,
which, as noted in Sec. IV.1, is particularly simple on account of the
membrane constraints. This allows us to derive an exact asymptotic form for
the free energy of perfect matchings on the AB∗ tiling, and compute e.g.
monomer correlations on the ladders.

The most general partition function for the dimer problem on a graph $G$ is a
weighted sum over all dimer configurations $\mathcal{C}$,

$Z=\sum_{\mathcal{C}}w(\mathcal{C}).$ (22)

Restricting to equally weighted perfect matchings (i.e. $w=1$ if $\mathcal{C}$
is a perfect matching, otherwise $w=0$), $Z$ simply counts perfect matchings.
Given a perfect matching of $G$, all other perfect matchings can be obtained
by augmenting alternating cycles (Sec. II.1). On AB∗ an alternating cycle
cannot intersect a membrane. Therefore, the enumeration of configurations on
AB∗ is obtained as the product over the enumerations on each ladder. That is,
the partition function factorizes over ladders, with each ladder defining an
independent 1D dimer problem. All ladders of order $n$ have the identical
partition function $Z_{n}$, and so the partition function in the thermodynamic
limit, $Z_{*}$, is simply

$Z_{*}=\prod_{n=0}^{\infty}Z_{n}^{\mathcal{N}_{n}}.$ (23)

where $\mathcal{N}_{n}$ is the number of order-$n$ ladders on the tiling,
given in Appendix B. The one dimensional nature of the stars and ladders
suggests that the partition functions $Z_{n}$ can be efficiently calculated in
terms of transfer matrices. To outline our approach for the AB∗ ladders, we
first consider the simpler problem of enumerating coverings of a closed
periodic ladder consisting only of square tiles.

The basic repeating unit of the ladder can be directly lifted to write down
the transfer matrix in graphical notation:

$i$$i^{\prime}$$j$$j^{\prime}$$\alpha$

which simply assigns an index to each edge of the unit. Each index runs over
the two values $(0,1)$, representing the edge in an uncovered state and a
state with a dimer. The transfer matrix entry corresponding to a given set of
indices $(iji^{\prime}j^{\prime}\alpha|$ is assigned a weight $w=1$ if the
corresponding state obeys the hard-core dimer constraint and perfectly matches
the two black vertices, otherwise we set $w=0$. For example, $(10010|$ is a
valid dimer configuration, but $(11001|$ is not. The internal index $\alpha$
is then summed over, and the left (right) indices are combined into a single
index $(ij|$ ($(i^{\prime}j^{\prime}|$) to enable us to write down the
transfer matrix
$\mathcal{P}_{iji^{\prime}j^{\prime}}\equiv(ij|i^{\prime}j^{\prime})$, or

$\mathcal{P}=\begin{pmatrix}1&1&0&0\\\ 1&0&0&0\\\ 0&0&0&1\\\
0&0&1&0\end{pmatrix}.$ (24)

Note that we have chosen to order the indices as $(00|,\ (11|,\ (10|,\ (01|$
to take advantage of the block diagonal nature of $\mathcal{P}$. This
splitting reflects a more fundamental property of the configuration space of
perfect matchings, wherein the space is further subdivided into topological
sectors: while all configurations are reachable from one another via
alternating cycles, only configurations in the same sector are connected via
_local_ cycles; configurations in distinct topological sectors can only be
connected via cycles which wind around the entire system (in one of the
directions with periodic boundary conditions). The periodic square ladder has
three possible sectors, $s=0,\pm 1$. The $s=\pm 1$ sectors contain only one
configuration each. These are the ‘staggered’ configurations with dimers
alternating between the top and bottom legs of the ladder. These are captured
by the lower block of $\mathcal{P}$. All other configurations belong to the
$s=0$ sector and are enumerated by the upper block matrix. For a closed
periodic ladder consisting of $M$ plaquettes, the partition function is
then777The same result appears in models of chains of Rydberg atoms [124,
125], owing to a mapping between the dimer constraint and the ‘Rydberg
blockade’ constraint, which forbids two neighbouring atoms to be in
simultaneously excited states.

$\tilde{Z}_{M}=\mathrm{Tr}(\mathcal{P}^{M})=F_{M+1}+F_{M-1}+2,$ (25)

with $F_{M}$ the $M$-th Fibonacci number, and $F_{1}=F_{2}=1$. The term $+2$
is the staggered contribution.

The aperiodic ladders defined by Eq. (17) are treated in an analogous fashion.
Clearly (24) still defines the transfer matrix between two square tiles. We
similarly introduce the matrix for an $A$-section rhombus (left) and the
$B$-section central ($R$-type) rhombi (right) as

$i^{\prime}$$i$$j^{\prime}$$j$

$j^{\prime}$$j$$i^{\prime}$$i$

with the internal states of the rhombi again summed over and only the external
legs $(iji^{\prime}j^{\prime})$ ‘free’. These are written explicitly as

$\mathcal{Q}=\begin{pmatrix}2&1&0&0\\\ 1&0&0&0\\\ 0&0&0&1\\\
0&0&1&0\end{pmatrix},\hskip 28.45274pt\mathcal{R}=\begin{pmatrix}3&1&0&0\\\
1&0&0&0\\\ 0&0&0&1\\\ 0&0&1&0\end{pmatrix}\hskip 14.22636pt.$ (26)

It is seen that each rhombus simply adds a state for which none of the free
legs hosts a dimer. Again the ladders decouple into three topological sectors,
with two staggered configurations entirely analogously to the periodic
ladders.

The three matrices $\mathcal{P},\ \mathcal{Q},\ \mathcal{R}$ allow for exact
enumeration of the ladder configurations. Unfortunately, they do not commute