Speaker: Gill Barequet
Dept. of Computer Science, Technion

Title: New bounds on Klarner's constant

Abstract:
Polyominoes are edge-connected sets of cells on the square lattice.
The study of polyominoes originated in statistical physics and is now a
popular field in combinatorial geometry.  A major goal in this area is to
determine the asymptotic growth constant of polyominoes (a.k.a. "Klarner's
constant") which is usually denoted by $\lambda$.  Until recently, the
best known lower and upper bounds on $\lambda$ were 3.98 and 4.65, resp.

We bounded $\lambda$ from below by investigating the growth constants of
polyominoes on "twisted" cylinders.  Using a supercomputer, we analized
polyominoes on a cylinder of perimeter 27, proving that $\lambda \geq 4.0025$
and thus braking the "mythical 4 barrier."  We also developed a new technique
for the upper bound, showing that $\lambda \leq 4.5685$.  This was the first
improvement of the upper bound in more than 40 years.

The first work was done jointly with G\"unter Rote (FU, Berlin) and
Mira Shalah (Technion, Haifa).  The second work was done jointly with
Ronnie Barequet (Tel Aviv University).