Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T03:28:21.666Z Has data issue: false hasContentIssue false

Exact and Approximate Compression of Transfer Matrices for Graph Homomorphisms

Published online by Cambridge University Press:  01 February 2010

Per Håkan Lundow
Affiliation:
KTH Physics, AlbaNova University Center, SE-106 91 Stockholm, Sweden, phl@kth.se, http://www.theophys.kth.se/~phl
Klas Markström
Affiliation:
Department of Mathematics and Mathematical Statistics, Umeå University, SE-901 87 Umeå, Sweden, Klas.Markstrom@math.umu.se, http://abel.math.umu.se/~klasm

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © London Mathematical Society 2008