Exact and Approximate Compression of Transfer Matrices for Graph Homomorphisms
2008 (English)In: LMS Journal of Computation and Mathematics, ISSN 1461-1570, Vol. 11, 1-14 p.Article in journal (Refereed) Published
The aim of this paper is to extend the previous work on transfer matrix compression in the case of graph homomorphisms. For H-homomorphisms of lattice-like graphs we demonstrate how the automorphisms of H, as well as those of the underlying lattice, can be used to reduce the size of the relevant transfer matrices. As applications of this method we give currently best known bounds for the number of 4- and 5-colourings of the square grid, and the number of 3- and 4-colourings of the three-dimensional cubic lattice. Finally, we also discuss approximate compression of transfer matrices.
Place, publisher, year, edition, pages
Cambridge University Press, 2008. Vol. 11, 1-14 p.
IdentifiersURN: urn:nbn:se:umu:diva-52122DOI: 10.1112/S1461157000000498ISI: 000207626900001OAI: oai:DiVA.org:umu-52122DiVA: diva2:497231