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

The Taub Faculty of Computer Science Events and Talks

Two Researches on Lattice Animals
event speaker icon
Yufei Zheng (M.Sc. Thesis Seminar)
event date icon
Sunday, 22.04.2018, 13:30
event location icon
Taub 301
event speaker icon
Advisor: Prof. Gill Barequet
Lattice animals are connected subgraphs of a lattice. In this talk, we consider two types of lattices, the $d$-dimensional hypercubic lattice and the triangular lattice, where the animals are frequently referred to as $d$-dimensional polycubes and polyiamonds, respectively. Denote the number of $d$-dimensional polycubes of volume $n$ and perimeter defect $k$ as $B(n,k,d)$, where $k$ is the deviation from the maximum perimeter. To-date, no formulae of $B(n,k,d)$ are known. In the first part of the talk, we derive a set of formulae of $B(n,k,d)$ for small values of $k$. Moreover, we show that for fixed defect $k$, the generating function of the enumerating sequence $(B(n,k,d))$ is rational. This inevitably sheds some light on the long-standing open problem of counting polyominoes and polycubes. The second part of the talk is dedicated to the lower bound on the growth constant of polyiamonds. We provide an improved lower bound using concatenation argument. A further improvement is also suggested, though based on an unproven yet highly plausible assumption. This research was performed under the supervision of Prof. Gill Barequet.