The Taub Faculty of Computer Science Events and Talks

Lattice animals are edge-connected sets of cells over various lattices. Some famous examples are polyominoes, polyhexes, polyiamonds and polycubes which are in the square, hexagonal triangular and cubical lattices respectively. Lattice animals have been studied extensively both as a combinatorial object, and as modeling tool in statistical physics. The two most significant problems related to lattice animals are the counting problem and the growth rate problem. The first is simply counting how many lattice animals with $n$ calls are there. This number is denoted by $A_\lattice(n)$ where $\lattice$ describes the specific lattice in question. The second problem relates to the growth rate of $A_\lattice(n)$. It have been shown that $\lim_{n \to \infty} A_\lattice(n+1)/A_\lattice(n)$ exists for all major lattices, and is denoted by $\lambda_\lattice$. The exact values of $\lambda_\lattice$ are unknown, however some bounds exists for it. Another area that have seen extensive research is studying lattice animals by their perimeter. The perimeter of a lattice animal is the set of unoccupied cells adjacent to the cells of the animal. The motivation to study polyominoes by their perimeter emerge from statistical physics where the numbers of lattice animals with a certain number of cells and perimeter size are used to model statistical processes such as percolation processes. In this work we some questions related to polyominoes and lattice animals. We studied minimum-perimeter lattice animals, which are lattice animals with the minimum number of perimeter cells for their area. We show some combinatorial properties of minimum-perimeter lattice animals, and by doing so proving a long standing conjecture in the field of enumerative chemistry. We also provide efficient algorithms for the enumeration of minimum-perimeter lattice animals. We also studied the number of ways two polyominoes and polycubes can be composed with each other to create a new, larger, polycube. This question emerged from an older study which tried to improve the upper bound on the growth rate of $A_\lattice(n)$ for polyominoes. Another area of study in this work was to study a classic argument that was used for the calculation of bounds on $\lambda_\lattice$ for various lattices. We refine this argument and by doing so we improved the best known bounds for the growth rate of certain classes of polyominoes and polycubes. Lastly, we tackled one of the biggest problems in the field of studying polyominoes, computing $A_\lattice(n)$ for the square lattice. We were able to improve on the best known algorithm and by doing so extend the known values of $A_\lattice(n)$ from $n=56$ to $n=70$.