Gill Barequet, Gunter Rote and Mira Shalah, λ > 4, Proc. 23rd Ann. European Symp. on Algorithms (ESA), 83-94, 2015.

Abstract:

A polyomino (“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 tends 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 settled a long-standing problem: proving that the leading digit of λ is 4.

Bibtex: 

@inproceedings{CBRS15,
	author = {Gill Barequet and Gunter Rote and Mira Shalah},
	title = {$lambda > 4$},
	booktitle = {Proceedings of the 23rd European Symposium on Algorithms (ESA)},
	pages = {83--94},
	year = {2015},
	venue = {Patras, Greece},
	month = {September}, 
}