Polycubes with small perimeter defect. (English) Zbl 1503.05084
Summary: In this paper, we consider enumeration of \(d\)-dimensional polycubes, whose perimeter (defined as the number of empty cells neighboring the polycube) has a fixed deviation from the maximum possible value. We provide a general framework for deriving such formulae, as well as several explicit formulae. In particular, we prove that for any fixed dimension \(d\), the generating function that enumerates polycubes with a fixed defect (with respect to their volume) is rational. Moreover, its denominator is a product of cyclotomic polynomials.
MSC:
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C30 | Enumeration in graph theory |
| 05B50 | Polyominoes |
| 05A15 | Exact enumeration problems, generating functions |
| 82B41 | Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics |
Software:
OEISReferences:
| [1] | The online encyclopedia of integer sequences (OEIS). http://oeis.org. |
| [2] | The open problems project. http://cs.smith.edu/ jorourke/TOPP/. |
| [3] | G. Aleksandrowicz and G. Barequet. Counting \(d\)-dimensional polycubes and nonrectangular planar polyominoes. Int. J. of Computational Geometry & Applications, 19(3):215-229, 2009. · Zbl 1184.05021 |
| [4] | Asinowski, A.; Barequet, G.; Barequet, R.; Rote, G., Proper \(n\)-cell polycubes in \(n{-}3\) dimensions, J. of Integer Sequences, 15, 2, 3 (2012) · Zbl 1292.05080 |
| [5] | Asinowski, A.; Barequet, G.; Zheng, Y., Enumerating polyominoes with fixed perimeter defect, Electronic Notes in Discrete Mathematics, 61, 61-67 (2017) · Zbl 1378.05023 · doi:10.1016/j.endm.2017.06.021 |
| [6] | A. Asinowski, G. Barequet, and Y. Zheng. Polycubes with small perimeter defect. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 93-100. SIAM, 2018. · Zbl 1402.05034 |
| [7] | G. Barequet and B. Magal. Automatic generation of formulae for polyominoes with a fixed perimeter defect. Computational Geometry: Theory and Applications, 2022. Accepted for publication. · Zbl 1498.05050 |
| [8] | Barequet, G.; Rote, G.; Shalah, M., \( \lambda > 4\): An improved lower bound on the growth constant of polyominoes, Comm. of the ACM, 59, 7, 88-95 (2016) · doi:10.1145/2851485 |
| [9] | Barequet, G.; Shalah, M., Counting \(n\)-cell polycubes proper in \(n{-}k\) dimensions, European J. of Combinatorics, 63, 146-163 (2017) · Zbl 1365.05044 · doi:10.1016/j.ejc.2017.03.006 |
| [10] | G. Barequet and M. Shalah. Improved upper bounds on the growth constants of polyominoes and polycubes. In Latin American Symposium on Theoretical Informatics, pages 532-545. Springer, 2021. Full version: Algorithmica, accepted for publication. · Zbl 07600801 |
| [11] | Barequet, R.; Barequet, G.; Rote, G., Formulae and growth rates of high-dimensional polycubes, Combinatorica, 30, 3, 257-275 (2010) · Zbl 1231.05068 · doi:10.1007/s00493-010-2448-8 |
| [12] | Bousquet-Mélou, M.; Rechnitzer, A., The site-perimeter of bargraphs, Advances in Applied Mathematics, 31, 1, 86-112 (2003) · Zbl 1020.05007 · doi:10.1016/S0196-8858(02)00553-5 |
| [13] | S.R. Broadbent and J.M. Hammersley. Percolation processes: I. Crystals and mazes. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 53, pages 629-641. Cambridge University Press, 1957. · Zbl 0091.13901 |
| [14] | A.R. Conway and A.J. Guttmann. On two-dimensional percolation. J. of Physics A: Mathematical and General, 28(4):891, 1995. · Zbl 0853.60095 |
| [15] | Eden, M., A two-dimensional growth process, Dynamics of fractal surfaces, 4, 223-239 (1961) · Zbl 0104.13801 |
| [16] | D.S. Gaunt. The critical dimension for lattice animals. J. of Physics A: Mathematical and General, 13(4):L97, 1980. |
| [17] | D.S. Gaunt, M.F. Sykes, and H. Ruskin. Percolation processes in d-dimensions. J. of Physics A: Mathematical and General, 9(11):1899, 1976. |
| [18] | S.W. Golomb. Polyominoes: Puzzles, patterns, problems, and packings. Princeton University Press, 1996. · Zbl 0831.05020 |
| [19] | Harary, F., Unsolved problems in the enumeration of graphs, Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5, 1-20 (1960) · Zbl 0095.16902 |
| [20] | Jensen, I., Enumerations of lattice animals and trees, J. of Statistical Physics, 102, 3-4, 865-881 (2001) · Zbl 0999.82037 · doi:10.1023/A:1004855020556 |
| [21] | I. Jensen. Counting polyominoes: A parallel implementation for cluster computing. In International Conference on Computational Science, Melbourne, Australia and St. Petersburg, Russia, pages 203-212. Lecture Notes in Computer Science, vol. 2659, Springer, 2003. |
| [22] | Klarner, DA, Cell growth problems, Canadian J. of Mathematics, 19, 851-863, 23 (1967) · Zbl 0178.00904 |
| [23] | Lunnon, WF, Counting multidimensional polyominoes, The Computer Journal, 18, 4, 366-367 (1975) · Zbl 0354.05010 · doi:10.1093/comjnl/18.4.366 |
| [24] | S. Luther and S. Mertens. Counting lattice animals in high dimensions. J. of Statistical Mechanics: Theory and Experiment, 2011(09):546-565, 2011. |
| [25] | Luther, S.; Mertens, S., The perimeter of proper polycubes, J. of Integer Sequences, 20, 2, 22 (2017) · Zbl 1384.05069 |
| [26] | Madras, N., A pattern theorem for lattice clusters, Annals of Combinatorics, 3, 2-4, 357-384 (1999) · Zbl 0935.60089 · doi:10.1007/BF01608793 |
| [27] | N. Madras, C.E. Soteros, S.G. Whittington, J.L. Martin, M.F. Sykes, S. Flesia, and D.S. Gaunt. The free energy of a collapsing branched polymer. J. of Physics A: Mathematical and General, 23(22):5327, 1990. · Zbl 0709.92025 |
| [28] | Martin, JL, The impact of large-scale computing on lattice statistics, J. of Statistical Physics, 58, 3-4, 749-774 (1990) · Zbl 1086.82550 · doi:10.1007/BF01112773 |
| [29] | A. Rechnitzer. The anisotropic generating function of self-avoiding polygons is not D-finite. In Polygons, polyominoes and polycubes, volume 775 of Lecture Notes in Phys., pages 93-115. Springer, Dordrecht, 2009. · Zbl 1180.82088 |
| [30] | Redelmeier, DH, Counting polyominoes: Yet another attack, Discrete Mathematics, 36, 2, 191-203 (1981) · Zbl 0466.05029 · doi:10.1016/0012-365X(81)90237-5 |
| [31] | Temperley, HNV, Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules, Physical Review, 103, 1, 1 (1956) · Zbl 0075.20502 · doi:10.1103/PhysRev.103.1 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
