Technical Report PHD-2011-11

TR#:PHD-2011-11
Class:PHD
Title: Enumeration of Lattice Animals
Authors: Gadi Aleksandrowicz
Supervisors: Gill Barequet
PDFPHD-2011-11.pdf
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 \emph{polyominoes} in the two dimensional case and \emph{polycubes} for higher dimensions).

In this work, we concern ourselves with the problem of \emph{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:

\textbf{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.

\textbf{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).

\textbf{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).

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

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2011/PHD/PHD-2011-11), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2011
To the main CS technical reports page

Computer science department, Technion
admin