Undecidability of Translational Tiling of the Plane with Four Tiles
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912446508171264 |
|---|---|
| author | Yang, Chao Zhang, Zhujun |
| author_facet | Yang, Chao Zhang, Zhujun |
| contents | The translational tiling problem, dated back to Wang's domino problem in the 1960s, is one of the most representative undecidable problems in the field of discrete geometry and combinatorics. Ollinger initiated the study of the undecidability of translational tiling with a fixed number of tiles in 2009, and proved that translational tiling of the plane with a set of $11$ polyominoes is undecidable. The number of polyominoes needed to obtain undecidability was reduced from $11$ to $7$ by Yang and Zhang, and then to $5$ by Kim. We show that translational tiling of the plane with a set of $4$ (disconnected) polyominoes is undecidable in this paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19295 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Undecidability of Translational Tiling of the Plane with Four Tiles Yang, Chao Zhang, Zhujun Combinatorics Computational Geometry Metric Geometry The translational tiling problem, dated back to Wang's domino problem in the 1960s, is one of the most representative undecidable problems in the field of discrete geometry and combinatorics. Ollinger initiated the study of the undecidability of translational tiling with a fixed number of tiles in 2009, and proved that translational tiling of the plane with a set of $11$ polyominoes is undecidable. The number of polyominoes needed to obtain undecidability was reduced from $11$ to $7$ by Yang and Zhang, and then to $5$ by Kim. We show that translational tiling of the plane with a set of $4$ (disconnected) polyominoes is undecidable in this paper. |
| title | Undecidability of Translational Tiling of the Plane with Four Tiles |
| topic | Combinatorics Computational Geometry Metric Geometry |
| url | https://arxiv.org/abs/2506.19295 |