Center for Algorithms and Theory of Computation

CS 269S, Fall 2018: Theory Seminar
Bren Hall, Room 1423, 1pm


October 12, 2018:

Lower Bounding the Growth Constants of Lattice Animals

Jordan Jorgensen

Lattice animals, specifically polyominoes, polyhexes and polyiamonds, are edge-connected sets of cells in the square, hexagonal, and triangular lattices respectively. Asymptotically, the number of each type of fixed lattice animal increases exponentially by some constant factor, known as its growth constant, as the size of the lattice animal increases. The exact values of these growth constants are not known, so we will discuss some methods of proving lower bounds on their values. Specifically we will discuss an improvement to the traditional 'concatenation argument' in which we show that appending lattice animals together can be used to lower bound the number, and thus the growth constant, of lattice animals. We will also show an improvement on the best known lower bound for the growth constant of polyiamonds by using an old method developed by Rands and Welsh (1981) based on Psuedo-Renewal Sequences.

(Based on joint work with Gill Barequet.)