New bounds on Klarner's constant

FC6029 (Dep. CC)
Friday, 20 November, 2015 - 14:30

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 limit growth rate of polyominoes, also known as ``Klarner's constant'' and 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 rates of polyominoes on ``twisted'' cylinders.  Using a supercomputer, we estimated the growth rate of polyominoes on a cylinder of perimeter 27, proving that
lambda >= 4.0025 and thus braking the "mythical 4 barrier".  We also developed a new technique for showing that lambda <= 4.5685, which is the first improvement of the upper bound on lambda in over 40 years.

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


Gill Barequet