Gill Barequet, Gunter Rote and Mira Shalah, λ > 4 : an improved lower bound on the growth constant of polyominoes, Communications of the ACM, 59 (7), 88-95, July 2016.

Abstract:

What is λ? The universal constant λ appears in the study of three seemingly completely unrelated fields: combinatorics, percolation, and branched polymers. In combinatorics, the analysis of self-avoiding walks (SAWs, non-self-intersecting lattice paths starting at the origin, counted by lattice units), simple polygons or self-avoiding polygons (SAPs, closed SAWs, counted by either perimeter or area), and polyominoes (SAPs possibly with holes, edge-connected sets of lattice squares, counted by area), are all related. In statistical physics, SAWs and SAPs play a significant role in percolation processes and in the collapse transition which branched polymers undergo when being heated. A recent collection edited by A. J. Guttmann provides an excellent review of all these topics and the connections between them. In this paper we describe our effort to prove that the growth constant (or asymptotic growth rate, also called the connective constant) of polyominoes is strictly greater than 4. To this aim we exploited to the maximum possible computer resources which were available to us. Eventually we obtained a computer-generated proof which was verified by other programs implemented independently.

Bibtex: 

@article{JBRS16,
	author = {Gill Barequet and Gunter Rote and Mira Shalah},
	title = {$lambda > 4$ :: an improved lower bound on the growth constant of polyominoes},
	journal = {Communications of the ACM (CACM)},
	volume = {59},
	pages = {88--95},
	month = {July},
	year = {2016},
}