Ronnie Barequet, Gill Barequet, and Günter Rote:

Formulae and growth rates of high-dimensional polycubes

  1. In: European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), Bordeaux, September 2009. Editors: Jaroslav Nešetřil and André Raspaud. Electronic Notes in Discrete Mathematics 34 (2009), 459–463. doi:10.1016/j.endm.2009.07.076
  2. Combinatorica 30 (2010), 257–275. doi:10.1007/s00493-010-2448-8


A d-dimensional polycube is a facet-connected set of cubes in d dimensions. Fixed polycubes are considered distinct if they differ in their shape or orientation. A proper d-dimensional polycube spans all the d dimensions, that is, the convex hull of the centers of its cubes is d-dimensional. In this paper we prove rigorously some (previously conjectured) closed formulae for fixed (proper and improper) polycubes, and show that the growth-rate limit of the number of polycubes in d dimensions is 2edo(d). We conjecture that it is asymptotically equal to (2d−3)e + O(1/d).

  pdf file (gzipped)   free PDF view@Springer
other papers about this subject
Last update: August 15, 2017.