Ph.D Thesis | |

Ph.D Student | Aleksandrowicz Gadi |
---|---|

Subject | Enumeration of Lattice Animals |

Department | Department of Computer Science |

Supervisor | PROF. Gill Barequet |

Full Thesis text |

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.