Classical Dimers on Penrose Tilings

We study the classical dimer model on rhombic Penrose tilings, whose edges and vertices may be identified as those of a bipartite graph. We find that Penrose tilings do not admit perfect matchings (defect-free dimer coverings). Instead, their maximum matchings have a monomer density of $81-50\phi \approx 0.098$ in the thermodynamic limit, with $\phi =(1+\sqrt{5})/2$ the golden ratio. Maximum matchings divide the tiling into a fractal of nested closed regions bounded by loops that cannot be crossed by monomers. These loops connect second-nearest-neighbor even-valence vertices, each of which lies on such a loop. Assigning a charge to each monomer with a sign fixed by its bipartite sublattice, we find that each bounded region has an excess of one charge, and a corresponding set of monomers, with adjacent regions having opposite net charge. The infinite tiling is charge neutral. We devise a simple algorithm for generating maximum matchings and demonstrate that maximum matchings form a connected manifold under local monomer-dimer rearrangements. We show that dart-kite Penrose tilings feature an imbalance of charge between bipartite sublattices, leading to a minimum monomer density of $(7-4\phi )/5\approx 0.106$ all of one charge.

Popular Summary

Fill a chess board with dominoes, remove one, and then shift and rotate the remaining dominoes so that the two exposed black-and-white squares appear to move around the board. This simple game—an example of a classical “dimer model”—provides a powerful analogy for studying particle-antiparticle pairs, charge fractionalization, and even high-temperature superconductors. Here, we apply this model to Penrose tilings, aperiodic mosaics built from rhombus-shaped tiles.

We ask whether it is possible to color the edges of the tiles such that each vertex connects to precisely one colored edge. The answer is no, and we find the minimum number of uncovered vertices that must exist. This number has a connection to the famous golden ratio, a number that appears repeatedly in classical architecture and nature.

The fact that the minimum number of uncovered vertices is nonzero is interesting. Just as the domino analogy shows that dimer models can represent particles being created from the vacuum, for example, this finite density shows that the theory has particles present in the vacuum itself. Even stranger is that there are particles of opposite charge simultaneously present in the vacuum. They are unable to annihilate with one another because of the underlying constraints on dimer placement implied by the structure of the Penrose tiling.

Our analysis takes the dimer model to a new setting, beyond the paradigm of periodicity and disorder. This in turn might lead to new insights into theories featuring topological order, including topological quantum computation and high-temperature superconductivity.

Figure 1

A finite section of the Penrose tiling constructed of two rhombuses (colored red and blue here).

Figure 2

(a) The Penrose tiling can be created by decorating the rhombuses with matching rules, where the decorations of neighboring edges must match. (b) An alternative method of creating the tiling uses inflation rules, in which each tile is subdivided into a combination of the two tiles as shown. Black lines indicate graph edges and gray circles graph vertices. (c) Decorating the tiles leads to different Penrose tilings made from different tile types: the $P1$ pentagonal tiling and the $P2$ dart-kite tiling.

Figure 3

The possible vertices in the $P2$ dart-kite tiling (left), their equivalents in the $P3$ rhombic tiling (middle), and the inflations of each (right). We label the $P3$ vertices according to the number of edges connected to them. Tile matching rules distinguish the $5_{A,B}$ vertices and are indicated; $P2$ suns are labeled according to the number of darts connected to them [53]. The $P2$ vertices divide into two bipartite sublattices: star-queen-king-ace (black vertices) and deuce-jack-suns (white vertices).

Figure 4

Each vertex type in Fig. 3 is accompanied by a set of tiles which always appears around it, termed a local empire [32].

Figure 5

(a) A maximal matching of a graph is a dimer covering such that no further edge can be covered with a dimer (purple) without causing a vertex (gray circles) to connect to two dimers. (b) A maximum matching additionally contains the maximum number of dimers. (c) If every vertex in a maximum matching connects to a dimer, the result is a perfect matching. (d) An alternating cycle is enclosed by the dashed line in this perfect matching of a bipartite graph. Augmenting the cycle (switching which edges are covered by dimers) results in another perfect matching. (e) Deleting one dimer results in a monomer-antimonomer pair. Augmenting paths are alternating paths with both ends terminating on monomers. Augmenting the path removes both monomers. No augmenting path can be present in a maximum matching. (f) An alternating path terminating on one monomer is highlighted. Augmenting the path moves the monomer. We term a minimal monomer move the augmentation of an alternating path of minimum length, which enacts a monomer hop across one unoccupied and one occupied edge.

Figure 6

Elements used in the proof that (a) a 6-vertex (blue) cannot host a monomer in a maximum matching, and (b) the dimer which must emanate from the 6-vertex must be placed on one of the three purple edges indicated. The direction of the 4- and 6-vertices is defined to align with the arrow. Thick black lines indicate edges which cannot be covered by dimers in maximum matchings. Solid (dashed) lines indicate definite (potential) uncoverable edges. Potential uncoverable edges are those that may or may not become uncoverable depending on how the local empire overlaps with others in the full tiling.

Figure 7

A maximum matching of a finite section of the Penrose tiling. Certain edges (thick black lines) of even-valence vertices (dark gray) cannot be covered by dimers (purple) in maximum matchings. Monomers colored blue or red according to their bipartite charge cannot cross the closed thick black loops.

Figure 8

(a) Deleting uncoverable edges in Fig. 7 disconnects the graph into monomer regions (the incomplete outermost region is removed). Neighboring monomer regions contain opposite net bipartite charge. The monomer indicated with a gold cross and arrow is able to reach the gold vertices by augmenting its alternating paths. It is not able to reach all vertices, even of its own charge; the obstruction is made by dimers rather than monomers (see Sec. 6). (b) Decorating the basic inflation elements with dimers in the final inflation results in the dimer covering shown. The following dimer inflation algorithm gives a maximum matching: Whenever a vertex is covered by two dimers, delete one. One monomer is then associated with each $5_{A,B}$-vertex with zero or one 7-vertices as second-nearest neighbors, and three monomers are associated with each $5_A$-vertex with two 7-vertices as second-nearest neighbors.

Figure 9

Decorating the tiles with red and blue curves as indicated, continuity of the curves implies the matching rules of Fig. 2. At most, two red curves may cross the entire system [32, 54]. All others must close around regions of $D_5$ symmetry. The curves follow chains of thick rhombuses, one of which is highlighted in blue (all thick rhombuses are adjacent to precisely two others). The curves also follow chains of second-nearest-neighbor even-valence vertices (monomer membranes): a 4-6-4 segment is highlighted with a thick black line. Therefore, these chains also close around regions of $D_5$ symmetry centered on either a $5_A$- or $5_B$-vertex. The thick black line can be seen to curve away from the 4-vertex with curvature $2\pi /5$ and toward the 6-vertex with curvature $-4\pi /5$, with the directions of the vertices defined in Fig. 6.

Figure 10

Proof that the dimer inflation algorithm of Sec. 4a associates monomers with $5_{A,B}$-vertices based on how many 7-vertices they have as second-nearest neighbors [points (i)–(iii) in that section]. (a) The local empire of the 4-vertex is large enough to cover the Penrose tiling, allowing for overlaps. (b) Inflating using the dimer-decorated inflation rules leads to a set of tiles large enough to cover the inflated tiling. (c) To confirm statements (i)–(iii) about monomer placement, it is necessary to check every continuation of the boundary vertices. Two continuations are shown, with relevant features highlighted: a $5_B$-vertex, and $5_A$-vertices with zero, one, and two 7-vertices as second-nearest neighbors.

Figure 11

The local empire of the 6-vertex with key vertices identified, used in the proof in Sec. 4b and Appendix pp2 that the dimer inflation algorithm in Fig. 8 generates maximum matchings. Solid (dashed) circles indicate vertices of definite (potential) valence: red 7-vertices, blue $5_A$-vertices, and pink $5_B$-vertices. Solid (dashed) thick black lines indicate definite (potential) segments of monomer membranes (which cannot be covered by dimers or crossed by monomers).

Figure 12

The listed vertex types must be separated by paths of even ($e$, solid lines) or odd ($o$, dashed lines) length if the vertices are separated by an even number of monomer membranes (including zero). If the vertices are separated by an odd number of monomer membranes, $e$ and $o$ should be interchanged. The box labeled “$5_A$” excludes the “$5_A-7$” and “$7-5_A-7$” configurations, and $5_A-7$ excludes $7-5_A-7$. See Fig. 10 and Sec. 4b.

Figure 13

Numerical results for the density of monomers in finite sections of the Penrose tiling. To achieve results with the least possible bias, we consider inflations of each basic tile: the thick (red squares) and thin (blue circles) rhombuses for $P3$ and the dart (red crosses) and kite (blue crosses) for $P2$ (see Sec. 7). For the rhombic tiling, solid symbols correspond to systems in which monomers are placed according to the dimer inflation algorithm (DIA) of Sec. 4a, whereas hollow symbols correspond to systems in which maximum matchings are found using the Hopcroft-Karp algorithm (HK, also used for the dart-kite tiling). The analytical results of $81-50\phi \approx 0.098$ for the rhombic $P3$ tiling and $(7-4\phi )/5\approx 0.106$ for the dart-kite $P2$ tiling are shown by the black dashed lines.

Figure 14

A region of the Penrose dart-kite ($P2$) tiling. The vertices (Fig. 3) divide into bipartite sublattices: star-queen-king-ace (red) and deuce-jack-suns (blue). Dark gray decagons indicate cartwheels, regions which can cover the infinite tiling allowing for overlaps [81].

Figure 15

A maximum matching of the Penrose dart-kite ($P2$) tiling in Fig. 14. Monomers are shown in red. All lie on the same bipartite sublattice.

Figure 16

The rhombic Penrose tiles (light gray) decorated with edges (black), vertices, and dimers (purple) such that each tile of the same type is identical, and the resulting bipartite graph admits a perfect matching.

Figure 17

A maximum matching of the Socolar-Taylor tiling [56, 93]. Purple edges indicate dimers; the dark blue (four dark red) vertices indicate monomers, while light blue (light red) vertices connect to blue (red) monomers via alternating paths (note the two distinct colors of light red, indicating distinct monomer regions; the separation of the different blue regions is clear). Monomer membranes are identified with thick black lines.

Figure 18

A maximum matching of the Boyle-Steinhardt $12B$ tiling [56]. Colors as in Fig. 17. Note the existence of perfectly matched regions within monomer membranes, thick black lines. These resemble manta rays converging on a coral reef at the center. These perfectly matched regions appear to be unique to the $12B$ and $12C$ tilings.

Figure 19

Proof no monomer can be based on a 4-vertex in a maximum matching. See accompanying text in Appendix pp1-s2.

Figure 20

Proof no monomer can be based on a $5_C$-vertex appearing between a 4-vertex and a 6-vertex in a maximum matching. See accompanying text in Appendix pp1-s2.

Figure 21

Proof that, of the edges emanating from a 6-vertex, only the edges indicated in Fig. 6 may host dimers. See accompanying text in Appendix pp1-s2.

Figure 22

Proof that, of the edges emanating from a 4-vertex, only the edges indicated in Fig. 6 may host dimers. See accompanying text in Appendix pp1-s2 and Fig. 21.