M.Sc Student | Zheng Yufei |
---|---|

Subject | Two Researches on Lattice Animals |

Department | Department of Computer Science |

Supervisor | Professor Gill Barequet |

Lattice animals are connected subgraphs of a lattice, where Fixed lattice
animals are considered identical if one can be translated into the other. The
fundamental combinatorial problem concerning lattice animals is “How many
animals with n cells are there?” To this end, we consider two types of
lattices, the *d*-dimensional hypercubic lattice and the two-dimensional
triangular lattice, where the animals are frequently referred to as
d-dimensional polycubes and polyiamonds, respectively. Since no general
analytic formula for the number of animals is known for any nontrivial lattice,
in this thesis, we focus on both driving formulae and understanding the growth
constants.

We investigate formulae enumerating *d*-dimensional polycubes by
volume and dimension with a fixed deviation from the maximum possible
perimeter. Aside from the explicit formulae, a general framework for deriving
such formulae is proposed. We further 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.

In this thesis we also suggest a nontrivial extension of a concatenation argument for improving the lower bound on the growth constant of polyiamonds. However, the proposed extension is based on a reasonable yet unproven assumption.