Gill Barequet, Günter Rote, and Mira Shalah:

λ>4: An improved lower bound on the growth constant of polyominoes

1. Extended abstract in: Abstracts of the 30th European Workshop on Computational Geometry (EuroCG'14), Ein-Gedi, Israel, March 2014, Editors: Paz Carmi, Matthew Katz, and Shakhar Smorodinsky, 4 pages.
2. In: "Algorithms—ESA 2015", Proc. 23rd Annual European Symposium on Algorithms, Patras, 2015. Editors: Nikhil Bansal and Irene Finocchi. Lecture Notes in Computer Science, Vol. 9294, Springer-Verlag, 2015, pp. 83–94. doi:10.1007/978-3-662-48350-3_8
3. Communications of the ACM 59, No. 7, July 2016, 88–95. doi:10.1145/2851485, free PDF @ACM

Abstract

A polyomino (or lattice animal) is an edge-connected set of squares on the two-dimensional square lattice. Counting polyominoes is an extremely hard problem in enumerative combinatorics, with important applications in statistical physics for modeling processes of percolation and collapse of branched polymers. We investigated a fundamental question related to polyominoes, namely, what is their growth constant, the asymptotic ratio between A(n + 1) and A(n) when n goes to infinity, where A(n) is the number of polyominoes of size n. This value is also known as "Klarner's constant" and denoted by λ. So far, the best lower and upper bounds on λ were roughly 3.98 and 4.65, respectively, and so not even a single decimal digit of λ was known. Using extremely high computing resources, we have shown (still rigorously) that λ>4.00253, thereby settling a long-standing problem: proving that the leading digit of λ is 4.

Note

Our main tool for certifying the quality of the eigenvalue approximation, Inequality (1) of our paper, is a classical result, which is known under the name Collatz–Wielandt inequality.