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.
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.
Last update: November 22, 2018.