Undecidability of Tiling the Plane with a Set of 5 Polyominoes

2025/08/13 by Kim, Yoonhu
#05B50 (Primary) 05B45 #52C20 #68Q17 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2508.10067

Abstract

In this paper, we give a proof that it is undecidable whether a set of five polyominoes can tile the plane by translation. The proof involves a new method of labeling the edges of polyominoes, making it possible to assign whether two edges can match for any set of two edges chosen. This is achieved by dedicating 1 polyomino to the labeling process.

Citations

• Translational Aperiodic Sets of 7 Polyominoes
• Tiling with Three Polygons is Undecidable
• The undecidability of the domino problem

Related

• Undecidability of Translational Tiling of the Plane with Four Tiles
• Undecidability of Translational Tiling of the Plane with Orthogonally Convex Polyominoes
• An Optimal Algorithm for Tiling the Plane with a Translated Polyomino
• Rectangular tileability and complementary tileability are undecidable
• Two Tiling is Undecidable