Tile Color Matching Using Simple Universal Cycles
Anna Virágvölgyi · 2010
In a square tiling, one can mark squares using edge-colored matching rules. I describe a set of matching rules based on universal cycles. These arise when one studies arrangements of different letters from a small alphabet into a single sequence in which all possible permutation of a given length can be found. The results are interesting visually. They may have applications in creating parquet or other two dimensional tiling patterns. Elements Consider an alphabet of k letters, where k (k>2) is always odd. Using this alphabet, create a set of words where each word is of even length 2n, but where no adjacent letters in the word are the same. For each n, if we ignore the direction of reading, the number of possible words is Sn=k(k-1) 2(n-1) . A universal cycle is a compact listing of a class of combinatorial objects [1]. One can prove that for the above sets of words exist universal cycles. An unwrapped universal cycle for n=3, S3=3×2 4 =48 with alphabet {a, b, c}: a b c a b a b a b c b c b c a b c a b c b c a c b a c a b a c b c a c a c a b a b c a c a b c b This cyclic string contains a, b and c equally 16 times. Each above defined word of length 6 occurs exactly once on this cycle: a b a b a c b a b a c a a b a c a c ... etc. Each letter (a, b, c) occurs in the entire set of words the same number of times – 2n(k-1) 2n-2 = 2x3x2 4 = 96. With other symbols (a = , b = , c = ) the above chain is: By substituting stripes for beads due to of the nature of universal cycles each elements of S3 one can get as diagonal striped square tiles. Figure 1: Unwrapped universal cycle with the S3 =48 elements. Areas of the different colors in the Figure 1 are equal to each other. The picture shows how a great number of possible interconnection are between this tiles. This feature enable the tiles to be matched in many ways. The rotated tiles can be matched as well. Bridges 2010: Mathematics, Music, Art, Architecture, Culture