Distances on Rhombus Tilings

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 ◦ 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 (octogonal 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 by hand)