Hamiltonian Cycles on Ammann-Beenker Tilings
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911949671890944 |
|---|---|
| author | Singh, Shobhna Lloyd, Jerome Flicker, Felix |
| author_facet | Singh, Shobhna Lloyd, Jerome Flicker, Felix |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_01940 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Hamiltonian Cycles on Ammann-Beenker Tilings Singh, Shobhna Lloyd, Jerome Flicker, Felix Statistical Mechanics Strongly Correlated Electrons Mathematical Physics 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. |
| title | Hamiltonian Cycles on Ammann-Beenker Tilings |
| topic | Statistical Mechanics Strongly Correlated Electrons Mathematical Physics |
| url | https://arxiv.org/abs/2302.01940 |