05947177

j

05947177 Bodini, Olivier Fernique, Thomas Rao, Michael R\'emila, \'Eric Distances on rhombus tilings. Theor. Comput. Sci. 412, No. 36, 4787-4794 (2011). 2011 Elsevier Science Publishers, Amsterdam EN computer-assisted proof flip phason pseudoline arrangement quasicrystal rhombus tiling tiling space

doi:10.1016/j.tcs.2011.04.015

Summary: The rhombus tilings of a simply connected domain of the Euclidean plane are known to form a flip-connected space (a flip is the elementary operation on rhombus tilings which rotates $180^{\circ}$ a hexagon made of three rhombi). Motivated by the study of a quasicrystal growth model, we are here interested in better understanding how ``tight" rhombus tiling spaces are flip-connected. We introduce a lower bound (Hamming-distance) on the minimal number of flips to link two tilings (flip-distance), and we investigate whether it is sharp. The answer depends on the number $n$ of different edge directions in the tiling: positive for $n=3$ (dimer tilings) or $n=4$ (octagonal tilings), but possibly negative for $n=5$ (decagonal tilings) or greater values of $n$. A standard proof is provided for the $n=3$ and $n=4$ cases, while the complexity of the $n=5$ case led to a computer-assisted proof (whose main result can however be easily checked manually).