טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentZheng Yufei
SubjectTwo Researches on Lattice Animals
DepartmentDepartment of Computer Science
Supervisor Professor Gill Barequet


Abstract

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.