Hamiltonian Cycles on Ammann-Beenker Tilings

• Published in 2024
• Added on 2024-12-02

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 \geq 3\)) of magnetic interactions defined on the planar dual to AB, which may provide useful models for protein folding.

Links

• https://journals.aps.org/prx/abstract/10.1103/PhysRevX.14.031005

Other information

BibTeX entry

@article{HamiltonianCyclesonAmmannBeenkerTilings,
	key = {HamiltonianCyclesonAmmannBeenkerTilings},
	type = {article},
	title = {Hamiltonian Cycles on Ammann-Beenker Tilings},
	author = {Shobhna Singh, Jerome Lloyd, Felix Flicker},
	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 \geq 3\)) of magnetic interactions defined on the planar dual to AB, which may provide useful models for protein folding.},
	comment = {},
	date_added = {2024-12-02},
	date_published = {2024-12-07},
	urls = {https://journals.aps.org/prx/abstract/10.1103/PhysRevX.14.031005},
	collections = {easily-explained,fun-maths-facts,geometry,things-to-make-and-do},
	url = {https://journals.aps.org/prx/abstract/10.1103/PhysRevX.14.031005},
	year = 2024,
	urldate = {2024-12-02}
}