טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentShalah Mira
SubjectFormulae and Growth Rates of Animals on Cubical and
Triangular Lattices
DepartmentDepartment of Computer Science
Supervisor Professor Gill Barequet


Abstract

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 λ = limn→∞ 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 λT from roughly 1.7 to 0.76.                                             

                                                           

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.