Journal article

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

Yao-ban Chan, Andrew Rechnitzer

Linear Algebra and its Applications | ELSEVIER SCIENCE INC | Published : 2018


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..

View full abstract

University of Melbourne Researchers


Funding Acknowledgements

The authors would like to thank Ian Enting and Brian Marcus for many helpful and interesting discussions, and WestGrid for providing access to their computer cluster. Financial support from the Natural Sciences and Engineering Research Council of Canada (NSERC) though its Discovery Program is gratefully acknowledged by the authors.