Abstract:

Despite the fact that polyominoes (edge-connected sets of squares on a
square lattice) are known as a fun geometric game, and have many 
applications, such as in cryptology, their study originated in statistical 
physics when researchers were seeking properties of liquid flow through 
grained material.  A major question in this field is what is the limit of 
polyomino growth rate.  This quantity, which is also called Klarner's 
constant and denoted as $\lambda$, has the fascinating property that not 
even a single significant digit of it is known!  The best currently-known 
lower and upper bounds on $\lambda$ are 3.874 and 4.650, respectively.  
(The claimed lower bound 3.927 turned out to be erroneous.)

This talk presents a novel technique for bounding $\lambda$ from below.
We investigate $\lambda_W$, the limit growth rate of polyominoes on a
\emph{twisted} cylinder of width (perimeter) $W$, and show that it is a
lower bound on $\lambda$.  By using tools from classical linear algebra,
notably the Perron-Frobenius Theorem, we have so far been able to estimate
$\lambda_W$ up to $W=22$.  Thus, we improved significantly upon the
previously-known lower bound by determining $\lambda \geq \lambda_{22} \geq
3.9801$, missing painfully the mythic 4.0-barrier by only 0.02.
The talk will consist of two 45-minute parts.  In the first part I will
describe the method in general, and in the second part I will prove the
correctness of the method.

Joint work with Micha Moffie, Ares Ribo and Gunter Rote.