Hamiltonian Cycles on Ammann-Beenker Tilings

Abstract

We provide a simple algorithm for constructing Hamiltonian graph cycles (visiting every vertex exactly once) on a set of arbitrarily large finite subgraphs of aperiodic two-dimensional Ammann-Beenker (AB) tilings. Using this result, and the discrete scale symmetry of AB tilings, we find exact solutions to a range of other problems which lie in the complexity class NP-complete for general graphs. These include the equal-weight traveling salesperson problem, providing, for example, the most efficient route a scanning tunneling microscope tip could take to image the atoms of physical quasicrystals with AB symmetries; the longest path problem, whose solution demonstrates that collections of flexible molecules of any length can adsorb onto AB quasicrystal surfaces at density one, with possible applications to catalysis; and the three-coloring problem, giving ground states for the $q$-state Potts model ($q\ge 3$) of magnetic interactions defined on the planar dual to AB, which may provide useful models for protein folding.

arXiv comment25 pages, 16 figures

References in corpus (32)

• Topological States and Adiabatic Pumping in Quasicrystals
• Why Do Proteins Look Like Proteins?
• Matter-wave diffraction from a quasicrystalline optical lattice
• Superconductivity and strong interactions in a tunable moiré quasiperiodic crystal
• Bulk Termination of the Quasicrystalline Five-Fold Surface of Al_{70}Pd_{21}Mn_{9}
• Observing localisation in a 2D quasicrystalline optical lattice
• Topological equivalence of crystal and quasicrystal band structures
• Solution of the Complex Action Problem in the Potts Model for Dense QCD
• Operator Spectrum and Exact Exponents of the Fully Packed Loop Model
• Antiferromagnetic order in the Hubbard Model on the Penrose Lattice
• Field theory of compact polymers on the square lattice
• Spectral Theory of Sparse Non-Hermitian Random Matrices
• Analysis of a fully packed loop model arising in a magnetic Coulomb phase
• Liouville Field Theory of Fluctuating Loops
• Exact Results for Hamiltonian Walks from the Solution of the Fully Packed Loop Model on the Honeycomb Lattice
• A maximum density rule for surfaces of quasicrystals
• Superlattice structure in the antiferromagnetically ordered state in the Hubbard model on the Ammann-Beenker tiling
• Mathematical diffraction of aperiodic structures
• Exact enumeration of Hamiltonian circuits, walks, and chains in two and three dimensions
• Conformational Entropy of Compact Polymers
• Nature of Protected Zero Energy States in Penrose Quasicrystals
• Classical Dimers on Penrose Tilings
• Conformal field theory of the Flory model of polymer melting
• Physical properties of an Aperiodic monotile: Graphene-like features, chirality and zero-modes
• Quasicrystalline Bose glass in the absence of disorder and quasidisorder
• Quasiperiodicity and 2D Topology in 1D Charge Ordered Materials
• On the universality of compact polymers
• Statistical mechanics of dimers on quasiperiodic Ammann-Beenker tilings
• Field theoretic approach to the counting problem of Hamiltonian cycles of graphs
• Dulmage-Mendelsohn percolation: Geometry of maximally-packed dimer models and topologically-protected zero modes on site-diluted bipartite lattices
• The breaking of continuous scale invariance to discrete scale invariance: a universal quantum phase transition
• Self-dual quasiperiodic percolation

Cited by in corpus (2)

• Anomalous proteinaceous shells with octagonal local order
• Flat quasicrystalline tilings in terms of density wave approach