$\lambda$ (Klarner's constant) is greater than 4

The Faculty of Informatics is pleased to announce a seminar given by Gill Barequet

DATE: Monday, June 24th, 2013
PLACE: USI Lugano Campus, room SI 006, Informatics building (Via G. Buffi 13)

TIME: 15.30

ABSTRACT:
Polyominoes are edge-connected sets of cells on the square lattice.  The study of polyominoes originated in statistical physics, namely in models of percolation processes and the collapse of branched polymers, and is now a popular field in combinatorics. 

A major goal in this area is computing the limit growth rate of polyominoes, which is usually referred to as ``Klarner's constant'' and is denoted by $\lambda$.  Until very recently, not a single digit of $\lambda$ has been known. 

The best lower and upper bounds on $\lambda$ were roughly 3.98 and 4.65, respectively.

I will first present the technique we used a few years ago for bounding $\lambda$ from below by investigating the growth rates of polyominoes on ``twisted'' cylinders, which we proved to be lower bounds on $\lambda$.

By using tools from linear algebra, notably the Perron-Frobenius theorem, we were able to estimate the growth rates of polyominoes on cylinders of perimeter up to 22, setting 3.9801 as a lower bound on $\lambda$.

I will then describe the computation we performed in May 2013 on a supercomputer at Hasso Plattner Institute in Potsdam, Germany.  Using 128 virtual cores with 2 TB of main memory (RAM), and applying some tricks for

saving running time and memory consumption, our program computed the growth rate of polyominoes on a cylinder of perimeter 27, setting 4.002537 as a lower bound on $\lambda$, thus, breaking the mythical 4.0 barrier.

The first work is work with Micha Moffie, Ares Rib\'o, and G\"unter Rote. The recent computation is joint work with G\"unter Rote and Mira Shalah.

BIO:
Gill Barequet is an Associate Professor of Computer Science at the Technion (Israel Institute of Technology), Haifa.  He earned his Ph.D. in computer science in 1994 from Tel Aviv University.  His research interests include computational and discrete geometry, combinatorics, and combinatorial geometry. 

HOST: Prof. Evanthia Papadopoulou