On the number of isohedral polyominoes
https://doi.org/10.22405/2226-8383-2024-25-1-138-154
Abstract
A polyomino is a connected figure on a plane composed from a finite number of unit squares adjacent to each other on the sides. A tiling of a plane into polyominoes is called isohedral if the symmetry group acts transitively on it, that is, if for any two polyominoes of the tiling there is a global symmetry of the tiling that moves one polyomino into the second. The paper considers the problem of counting the number of polyominoes of area 𝑛 that generate isohedral tilings of the plane. It is shown that the number of such polyominoes does not exceed 𝐶(𝜀)𝑛^4(𝜔 + 𝜀)^𝑛, where 𝜔 is the connective constant of the square lattice Z^2. It is known that 𝜔 < 2.7. Similar estimates were also obtained in the case where the perimeter rather than the area of the polyomino is fixed. In addition, a similar estimate is valid for the number of isohedral tilings of the plane themselves under the additional condition of regularity of the tilings Previously, similar results were obtained in the case of lattice tilings of the plane into
polyominoes, for the so-called 𝑝2-splits, as well as for lattice tilings into centrally symmetric polyominoes.
The proof is based on the criteria for the existence of an isohedral tiling of the plane into polyominoes obtained by Langerman and Winslow, as well as on counting the number of selfavoiding
random walks on the lattice Z2, both standard and with a given symmetry group.
In conclusion, possible directions for further research and some open problems are briefly discussed.
About the Authors
Anton Vladimirovich Shutov
Vladimir State University named after Alexander and Nikolay Stoletovs
Russian Federation
Russian Federation
doctor of physical and mathematical sciences
Albina Andreevna Mokrova
Vladimir State University named after Alexander and Nikolay Stoletovs
Russian Federation
Russian Federation
candidate of physical and mathematical sciences
References
1. Golomb S. W. 1954, “Checker boards and polyominoes”, American Mathematical Monthly, vol. 61, pp. 672–682. (https://doi.org/10.2307/2307321)
2. Golomb S. W. 1994, “Polyominoes, 2nd edition”, Princeton University Press, New Jercey, 196 p. (https://doi.org/10.1515/9780691215051)
3. Gardner M. 1975, “More about tiling the plane: the possibilities of polyominoes, polyiamonds, and polyhexes”, Scientic American, pp 112–115. (https://doi.org/10.1038/scientificamerican0875-112)
4. Rhoads G. C. 2005, “Planar tilings by polyominoes, polyhexes, and polyiamonds” Journal of Computational and Applied Mathematics,vol. 174, pp. 329–353. (https://doi.org/10.1016/j.cam.2004.05.002)
5. Rhoads G. C. 2003, “Planar Tilings and the Search for an Aperiodic Prototile”, PhD dissertation, Rutgers University.
6. Rawsthorne D. 1988, “Tiling complexity of small n-ominoes (n < 10)”, Discrete Math., vol. 70, no. 1, pp. 71–75. (https://doi.org/10.1016/0012-365X(88)90081-7)
7. Myers J. 2016, “Polyomino, polyhex and polyiamond tiling”, Available at: https://www.polyomino.org.uk/mathematics/polyform-tiling/
8. Fontaine A. & Martin G. 1984, “Polymorphic polyominoes”, Math. Mag., vol. 57, no. 5, pp. 275–283.
9. (https://doi.org/10.1080/0025570X.1984.11977126)
10. Kazuyuki A. & Yoshinobu H. 2018, “On the number of p4-tilings by an 𝑛-omino”, Internat. J. Comput. Geom. Appl., vol. 29, no. 1, pp. 3–19. (https://doi.org/10.1142/S0218195919400016)
11. Maleev A. V. 2013, “Algorithm and computer-program search for variants of polyomino packings in plane”, Kristallografija, vol. 58, no. 5, pp. 749–756. (https://doi.org/10.7868/S0023476113040140)
12. Fukuda H. & Mutoh N. & Nakamura G. & Schattschneider D. 2007, “A method to generate polyominoes and polyiamonds for tilings with rotational symmetry”, Graphs and Combinatorics, vol. 23, no. 1, pp. 259–267. (https://doi.org/10.1007/s00373-007-0719-y)
13. Fukuda H. & Mutoh N. & Nakamura G. & Schattschneider D. 2008, “Enumeration of polyominoes, polyiamonds and polyhexes for isohedral tilings with rotational symmetry”, Computational Geometry and Graph Theory - International Conference, KyotoCGGT 2007, Kyoto, Japan, June 11–15, 2007. Revised Selected Papers, Springer, pp. 68–78. (https://doi.org/10.1007/978-3-540-89550-3_7)
14. Horiyama T. & Samejima M. 2009, “Enumeration of polyominoes for p4 tiling”, Proc. 21st Canadian Conf. Computational Geometry (CCCG 2009), pp. 29–32.
15. Beauquier D. & M. Nivat M. 1991, “On translating one polyomino to tile the plane”, Discrete Comput. Geom., vol. 6, no. 6, pp. 575–592. (https://doi.org/10.1007/BF02574705)
16. Brlek S. & Provencal X & Fedou J.-M. 2009, “On the tiling by translation problem”, Discrete Applied Mathematics, vol. 157, no. 3, pp. 464–475. (https://doi.org/10.1016/j.dam.2008.05.026)
17. Gambini I. & Vuillon L. 2007, “An algorothm for deciding if a polyomino tiles the plane by translations”, RAIRO Theoretical Informatics and Applications, vol. 41, no. 2, pp. 147–155. (https://doi.org/10.1051/ita: 2007012)
18. Keating K. & Vince A. 1999, “Isohedral polyomino tiling of the plane”, Discrete Comput. Geom., vol. 21, no. 4, pp. 615–630. (https://doi.org/10.1007/PL00009442)
19. Lanngerman S. & Winslow A. 2016, “A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino”, Proc. of 32nd International Symposium on Computational Geometry (SoCG 2016), vol. 50, pp. 1–50. (https://doi.org/10.4230/LIPIcs.SoCG.2016.50)
20. Brlek S. & Frosini A. & Rinaldi S. & Vuillon L. 2006, “Tilings by translation: enumeration by a rational language approach”, The electronic journal of combinatorics, vol. 13, p. 15. (https://doi.org/10.37236/1041)
21. Maleev A. V. & Shutov A. V. 2013, “On the number of translational plane tilings by polyomino”, Trudy IX Vserossiiskoi nauchnoi shkoly “Matematicheskie issledovaniya v estestvennyh naukah” (Proc. IX All-Russian scientfic school "Mathematical Research in Natural sciences Apatity, pp. 101–106.
22. Shutov A. V. & Kolomeykina E. V. 2013, “The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino”, Model. Anal. Inform. Sist., vol. 20, no. 5, pp. 148–157. (https://doi.org/10.18255/1818-1015-2013-5-148-157)
23. Shutov A. V. & Kolomeykina E. V. 2015, “The estimating of the number of lattice tilings of a plane by a given area centrosymmetrical polyomino”, Model. Anal. Inform. Sist., vol. 22, no. 2, pp. 295–303. (https://doi.org/10.18255/1818-1015-2015-2-295-303)
24. Shutov A. V. & Kolomeykina E. V. 2016, “The estimation of the number of p2-tilings of a plane by a given area polyomino”, Chebyshevskii Sbornik., vol. 17, no. 3, pp. 204–214. (https://doi.org/10.22405/2226-8383-2016-17-3-204-214)
25. Goodman-Strauss C. 2010, “Can’t decide? undecide!”, Notices of the American Mathematical Society, vol. 57, no. 3, pp. 343–356.
26. Hilbert D. 1902, “Mathematical problems”, Bulletin of the American Mathematical Society, vol. 8, no. 10, pp. 437-479. (https://doi.org/10.1090/S0002-9904-1902-00923-3)
27. Grunbaum B. & Shephard G. C. 1977, “The eighty-one types of isohedral tilings in the plane”, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 82, no. 2, pp. 177–196.(https://doi.org/10.1017/S0305004100053810)
28. Heesch H. & Kienzle O. 1963, “Flachenschluss: System der Formen luckenlos aneinanderschliessender Flachteile”, Springer.
29. Schattschneider D. 1980, “Will it tile? try the Conway criterion!”, Mathematics Monthly, vol. 53, no. 4, pp. 224-233. (https://doi.org/10.2307/2689617)
30. Bauerschmidt R. & Duminil-Copin H. & Goodman J. & Slade G. 2010, “Lectures on selfavoiding walks”, Probability and Statistical Physics in Two and More Dimensions. Clay Mathematics Proceedings, vol. 15, pp. 395–476.
31. Schattschneider D. 1921, “John Conway, Tilings, and Me!”, Mathematical Intelligencer, vol. 43, no. 2, pp. 124–129. (https://doi.org/10.1007/s00283-021-10062-0)
Review
For citations:
Shutov A.V., Mokrova A.A. On the number of isohedral polyominoes. Chebyshevskii Sbornik. 2024;25(1):138-154. (In Russ.) https://doi.org/10.22405/2226-8383-2024-25-1-138-154
Views:
273
Email this article 