Exact and approximate compressions of transfer matrices for graph homomorphisms
Per Håkan Lundow and Klas Markström
Abstract: 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.
|
