Upper bounds on the growth rates of independent sets in two dimensions via corner transfer matrices

Abstract

We devise an algorithm to calculate upper bounds on the growth rates of the number of independent sets on a variety of regular two-dimensional lattices, using an amalgamation of techniques from linear algebra, combinatorics, and statistical mechanics. Our method uses Calkin and Wilf's transfer matrix eigenvalue upper bound together with the Collatz–Wielandt formula from linear algebra. To obtain a good bound, we need an approximate eigenvector, which we find using Baxter's corner transfer matrix ansatz and Nishino and Okunishi's corner transfer matrix renormalisation group method. This results in an algorithm for computing upper bounds which is far faster in practice than all other known met..