טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentAleksandrowicz Gadi
SubjectEnumeration of Lattice Animals
DepartmentDepartment of Computer Science
Supervisor Professor Gill Barequet
Full Thesis textFull thesis text - English Version


Abstract

Lattice animals, which can be defined as connected subgraphs of the dual graph of a given lattice, are well-known combinatorial objects, studied both in pure and recreational mathematics, and in various

different fields, such a statistical physics and computational geometry. Of particular interest are lattice animals on the standard rectangular lattice

(called polyominoes in the two dimensional case and polycubes for higher dimensions).


In this work, we concern ourselves with the problem of enumerating lattice animals: computing, or estimating, how many lattice animals exist for a given type and size.

This is a difficult combinatorial problem; even for the relatively simple case of the two-dimensional rectangular lattice not much is known, and other lattices are much less studied.


We investigate the problem in several directions:


Enumeration algorithms: We describe an algorithm for enumerating directly lattice animals on every possible lattice. Using a parallel version of the algorithm we counted many types

of lattice animals and found many results never given in the literature so far.


Analytical analysis: We describe formulae for several sequences of lattice animals (specifically, some of the diagonals in a table of polycubes, arranged by size and dimension).


Transfer-matrix methods: We describe a method for computing algorithmically the generating function of lattice animals on a so-called ``twisted cylinder''.

These animals are of special interest since there are fewer of them than regular polyominoes (of any size $n$), thus, their growth-rate limit is a lower bound to the growth-rate of polyominoes (whose computation is

one of the main problems in the field).


Bijection with permutations: We describe a novel method of identifying polyominoes with permutations, and characterizing classes of polyominoes using forbidden permutation patterns.