Ph.D Student | Shalah Mira |
---|---|

Subject | Formulae and Growth Rates of Animals on Cubical and Triangular Lattices |

Department | Department of Computer Science |

Supervisor | Professor Gill Barequet |

A polyomino of
size *n* consists of *n* squares joined along their edges. The
popular computer game Tetris features polyominoes of size 4. Polyominoes can
also be considered on the two-dimensional triangular lattice, or in higher
dimensions, where they are called polyiamonds and polycubes, respectively. In
general, a connected set of cells on a lattice is called a lattice animal.

Lattice animals are well-known combinatorial objects, studied both in pure and recreational mathematics, and in various other fields, such as computational geometry and statistical physics, where they play a fundamental role in modeling branched polymers and the analysis of percolation processes.

The focus of
this work is on fundamental questions along the lines of: how many lattice
animals of size *n* are there? In most cases, even for the relatively
simple case of the two-dimensional square lattice, a simple closed formula for
this number is not known, and so other results are sought: a generating
function, an estimation of their asymptotic growth rate, an efficient counting
algorithm, and so on. Finding *A*(*n*), the number of polyominoes of
size *n*, is one of the “holy grails” of enumerative combinatorics. In
this thesis, we use an interplay between computational methods, on the one
hand, and analytical and theoretical methods, on the other hand, to tackle
these problems in several directions:

**Polyominoes**
We investigate a fundamental question concerning polyominoes, namely, what is
their growth constant λ = lim_{n→∞}
*A*(*n * 1) / *A*(*n*), also known as “*Klarner’s
constant*.” Previously, the best known lower and upper bounds on λ were
roughly 3.98 and 4.65, respectively, and so not even a single decimal digit of
λ was known. Using high computing resources, we improve the upper bound to
about 4.5252, and more importantly, we show that λ > 4.00253, thereby
settling the long-standing problem of proving formally that the leading decimal
digit of λ is 4.

**Polyiamonds**
We prove that λ* _{T}* , the growth constant of polyiamonds,
is between 2.8424 and 3.6050, narrowing the known gap between the lower and
upper bounds on λ

**Polycubes**
We develop a theoretical framework for computing the explicit formula
enumerating polycubes with *n* cubes that span *n−k* dimensions, for a fixed value of *k*.
Besides the interest in the number of these simple combinatorial objects, known
as proper polycubes, these polycubes are key for understanding the behavior of
high-dimensional polycubes. We use this framework to implement a computer
program which reaffirms the known formulae for *k* = 2, 3, and proves
rigorously, for the first time, the formulae for *k* = 4, 5. The main
contribution of this framework is a proof of a conjecture about the general
form of the formula for a general value of *k*.

Our work provides and improves upon some of the few rigorously known results in this area, some of which could have been so far derived only by non-rigorous methods and estimates. It also showcases the power of pairing computers with theory to tackle fundamental problems in combinatorics.