On the number of isohedral polyominoes

A. V. Shutov ; А. А. Mokrova

Čebyševskij sbornik, Tome 25 (2024) no. 1, pp. 138-154.

Résumé

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 $n$ that generate isohedral tilings of the plane. It is shown that the number of such polyominoes does not exceed $C(\varepsilon)n^4(\omega+\varepsilon)^n$, where $\omega$ is the connective constant of the square lattice $\mathbb{Z}^2$. It is known that $\omega2.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 $p2$-tiditgs 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 self-avoiding random walks on the lattice $\mathbb{Z}^2$, both standard and with a given symmetry group. In conclusion, possible directions for further research and some open problems are briefly discussed.

Détail

Keywords: polyominoes, isohedral polyominoes, plane tilings, isohedrality criteria.

Bibliographie

[1] Golomb S. W., “Checker boards and polyominoes”, American Mathematical Monthly, 61 (1954), 672–682 | DOI | MR

[2] Golomb S. W., Polyominoes, 2nd edition, Princeton University Press, New Jercey, 1994, 196 pp. | DOI

[3] Gardner M., “More about tiling the plane: the possibilities of polyominoes, polyiamonds, and polyhexes”, Scientic American, 1975, 112–115 | DOI

[4] Rhoads G. C., “Planar tilings by polyominoes, polyhexes, and polyiamonds”, Journal of Computational and Applied Mathematics, 174 (2005), 329–353 | DOI | MR | Zbl

[5] Rawsthorne D., “Tiling complexity of small n-ominoes (n 10)”, Discrete Math., 70:1 (1988), 71–75 | DOI | MR | Zbl

[6] Rhoads G. C., Planar Tilings and the Search for an Aperiodic Prototile, PhD dissertation, Rutgers University, 2003

[7] Myers J., Polyomino, polyhex and polyiamond tiling https://www.polyomino.org.uk/mathematics/polyform-tiling/

[8] Fontaine A., Martin G., “Polymorphic polyominoes”, Math. Mag., 57:5 (1984), 275–283 | DOI | MR | Zbl

[9] Kazuyuki A., Yoshinobu H., “On the number of p4-tilings by an $n$-omino”, Internat. J. Comput. Geom. Appl., 29:1 (2018), 3–19 | DOI | MR

[10] Maleev A. V., “Algorithm and computer-program search for variants of polyomino packings in plane”, Kristallografija, 58:5 (2013), 749–756 | DOI

[11] Fukuda H., Mutoh N., Nakamura G., Schattschneider D., “A method to generate polyominoes and polyiamonds for tilings with rotational symmetry”, Graphs and Combinatorics, 23, Supplement 1 (2007), 259–267 | DOI | MR | Zbl

[12] Fukuda H., Mutoh N., Nakamura G., Schattschneider D., “Enumeration of polyominoes, polyiamonds and polyhexes for isohedral tilings with rotational symmetry”, Computational Geometry and Graph Theory - International Conference KyotoCGGT, Revised Selected Papers (Kyoto, Japan, June 11–15, 2007), Springer, 2007, 68–78 | DOI | MR

[13] Horiyama T., Samejima M., “Enumeration of polyominoes for p4 tiling”, Proc. 21st Canadian Conf. Computational Geometry. CCCG, 2009, 29–32

[14] Beauquier D., Nivat M., “On translating one polyomino to tile the plane”, Discrete Comput. Geom., 6:6 (1991), 575–592 | DOI | MR | Zbl

[15] Brlek S., Provencal X., Fedou J.-M., “On the tiling by translation problem”, Discrete Applied Mathematics, 157:3 (2009), 464–475 | DOI | MR | Zbl

[16] Gambini I., Vuillon L., “An algorothm for deciding if a polyomino tiles the plane by translations”, RAIRO Theoretical Informatics and Applications, 41:2 (2007), 147–155 | DOI | MR | Zbl

[17] Keating K., Vince A., “Isohedral polyomino tiling of the plane”, Discrete Comput. Geom., 21:4 (1999), 615–630 | DOI | MR | Zbl

[18] Lanngerman S., Winslow A., “A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino”, Proc. of 32nd International Symposium on Computational Geometry, SoCG 2016, 2016, 50:1–50:15 | DOI | MR

[19] Brlek S., Frosini A., Rinaldi S., Vuillon L., “Tilings by translation: enumeration by a rational language approach”, The electronic journal of combinatorics, 13 (2006), 15 pp. | DOI | MR | Zbl

[20] Maleev A. V., Shutov A. V., “On the number of translational plane tilings by polyomino”, Proc. IX All-Russian scientfic school “Mathematical Research in Natural sciences” (Apatity), 2013, 101–106

[21] Shutov A. V., Kolomeykina E. V., “The Estimation of the Number of Lattice Tilings of a Plane by a Given Area Polyomino”, Model. Anal. Inform. Sist., 20:5 (2013), 148–157 | DOI

[22] Shutov A. V., Kolomeykina E. V., “The estimating of the number of lattice tilings of a plane by a given area centrosymmetrical polyomino”, Model. Anal. Inform. Sist., 22:2 (2015), 295–303 | DOI | MR

[23] Shutov A. V., Kolomeykina E. V., “The estimation of the number of p2-tilings of a plane by a given area polyomino”, Chebyshevskii Sbornik, 17:3 (2016), 204–214 | DOI | MR | Zbl

[24] Goodman-Strauss C., “Can't decide? undecide!”, Notices of the American Mathematical Society, 57:3 (2010), 343–356 | MR | Zbl

[25] Hilbert D., “Mathematical problems”, Bulletin of the American Mathematical Society, 8:10 (1902), 437–479 | DOI | MR

[26] Grunbaum B., Shephard G.C., “The eighty-one types of isohedral tilings in the plane”, Mathematical Proceedings of the Cambridge Philosophical Society, 82:2 (1977), 177–196 | DOI | MR | Zbl

[27] Heesch H., Kienzle O., Flachenschluss: System der Formen luckenlos aneinanderschliessender Flachteile, Springer, 1963 | MR

[28] Schattschneider D., “Will it tile? try the Conway criterion!”, Mathematics Monthly, 53:4 (1980), 224–233 | DOI | MR | Zbl

[29] Bauerschmidt R., Duminil-Copin H., Goodman J., Slade G., “Lectures on selfavoiding walks”, Probability and Statistical Physics in Two and More Dimensions, Clay Mathematics Proceedings, 15, 2010, 395–476 | MR

[30] Schattschneider D., “John Conway, Tilings, and Me!”, Mathematical Intelligencer, 43:2 (1921), 124–129 | DOI | MR