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


Two Researches on Lattice Animals
event speaker icon
Yufei Zheng, M.Sc. Thesis Seminar
event date icon
Sunday, 22.4.2018, 13:30
event location icon
Taub 301
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.
[Back to the index of events]