λ > 4

Abstract

A polyomino (or animal) is an edge-connected set of squares on the regular square lattice. Enumeration of polyominoes is an extremely hard problem in enumerative combinatorics, with important applications in statistical physics. We investigate one of the fundamental problems related to polyominoes, namely, computing their asymptotic growth rate λ=lim A(n+1)/A(n) , where A(n) is the number of polyominoes of size n. λ is also known as Klarner's constant. The best lower and upper bounds on so far were roughly 3.98 and 4.65, respectively, meaning that not even a single decimal digit of was known. Our goal was to settle a long-standing problem: proving that λ>4. To this aim, we developed a computer program which required extremely high computing resources in terms of both running time and main memory. Our program showed rigorously that λ>4.00253.