A small aperiodic set of Wang tiles. (English) Zbl 0861.05017

Kari, Jarkko

Discrete Math. 160, No. 1-3, 259-264 (1996).

A Wang tile is a unit square tile with colored edges. Consider tilings of the Euclidean plane by arbitrarily many copies from a given finite tile set \(T\) of Wang tiles translated to integer lattice points and such that contiguous edges have the same color. Such a tiling, determined by a function \(f:Z^2\to T\), is periodic if there exists \((a,b)\in Z^2\backslash\{(0,0)\}\) such that \(f(x,y)= f(x+a,y+b)\) for every \((x,y)\in Z^2\). A tile set \(T\) is called aperiodic if there exists a tiling, but there does not exist any periodic tiling. In 1966 R. Berger [Mem. Am. Math. Soc. 66 (1966; Zbl 0199.30802)] constructed an aperiodic tile set consisting of over 20,000 Wang tiles. The number has since been reduced, including a set consisting of 16 Wang tiles due to R. Amman. In the paper under review, the number is further reduced to 14 Wang tiles.

Reviewer: A.Vince (Gainesville)

MSC:

05B45	Combinatorial aspects of tessellation and tiling problems
52C20	Tilings in \(2\) dimensions (aspects of discrete geometry)

Keywords:

Wang tile; integer lattice points; periodic tiling; aperiodic tile set

References:

[1]	Beatty, S.; Beatty, S., Problem 3173, Am. math. monthly, Am. math. monthly, 34, 159, (1927), solutions in · JFM 53.0198.06
[2]	Berger, R., The undecidability of the domino problem, Mem. amer. math. soc., 66, (1966) · Zbl 0199.30802
[3]	Grünbaum, B.; Shephard, G.C., Tilings and patterns, (1987), W.H. Freeman and Company New York · Zbl 0601.05001