Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

A New Lower Bound on the Growth Constant of Polycubes in Three Dimensions
event speaker icon
Matan Mamistvalov (M.Sc. Thesis Seminar)
event date icon
Monday, 27.06.2022, 13:30
event location icon
Zoom Lecture: 98302771831
event speaker icon
Advisor: Prof. G. Barequet
In this thesis, we deal the approximation problem of the growth rate of polycubes in three dimensions. We consider three-dimensional polycubes, which are finite collections of face-connected 3D-cubes, centered in points of $\mathbb{Z}^3$, where the lexicographically smallest cube is centered in $(0,0,0)$. If we denote the number of 3D polycubes comprised of $n$ cubes by $A(n)$, then we know from prior results that this sequence behaves like an exponential, and so we denote its growth rate by $\lambda$. There are several prior lower bounds for $\lambda$, each improving upon the other, the latest one before this work is by Barequet, Ben-Shachar and Osegueda. In their work, the new method of \emph{recursive compositions} is used explicitly, where it was implicitly in used in a few previous works. In its essence, it creates distinct classes of polycubes of size $n$ made of compositions of polycubes of smaller numbers,such that when summing their cardinalities parametrized by $n$, we get lower bounds on $A(n)$, which can then be used to get lower bounds on $\lambda$. They also used the method of recursive compositions in a general manner fitting many multidimensional cubical lattices, achieving the lower bound of $6.6521$. We make a more specialized use of this method to the 3D cubical lattice, achieving a lower bound of $\lambda \geq 6.6799$.