Distances on Rhombus Tilings

Details Distances on Rhombus Tilings Distances on Rhombus Tilings

2009-11-14

arxiv.org/abs/0911.2804v2

Theor. Comput. Sci. 412(36): 4787-4794 (2011)

Computer Science

Discrete Mathematics

18 pages, 9 figures, submitted to Theoretical Computer Science (special issue of DGCI'09)

Scientific paper

10.1016/j.tcs.2011.04.015

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{\deg} 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).

Affiliated with

Also associated with

No associations

Rating

Distances on Rhombus Tilings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distances on Rhombus Tilings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distances on Rhombus Tilings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-323492