Undecidability of tiling the plane with a fixed number of Wang bars

2024/04/06 by Yang, Chao, Zhang, Zhujun
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.2404.04504

Abstract

To study the fixed parameter undecidability of tiling problem for a set of Wang tiles, Jeandel and Rolin show that the tiling problem for a set of 44 Wang bars is undecidable. In this paper, we improve their result by proving that whether a set of 29 Wang bars can tile the plane is undecidable. As a consequence, the tiling problem for a set of Wang tiles with color deficiency of 25 is also undecidable.

Related

• Undecidability of Translational Tiling of the Plane with Four Tiles
• Undecidability of Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes
• Two Tiling is Undecidable
• Undecidability of Translational Tiling of the Plane with Orthogonally Convex Polyominoes
• Undecidability of Tiling the Plane with a Set of 5 Polyominoes