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

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 methods. It is also the first algorithm for this problem with a polynomial, rather than exponential, memory requirement, and it is extremely parallelisable. This allows us to make dramatic improvements to the previous best known upper bounds. We apply our algorithm to five models, including independent sets on the square lattice (also known as the hard squares lattice gas from statistical mechanics). In all cases we extend the number of rigorously known digits of the growth rate by 4-6 digits.