Change search
ReferencesLink to record
Permanent link

Direct link
Exact and Approximate Compression of Transfer Matrices for Graph Homomorphisms
KTH Physics, AlbaNova University Center, SE-106 91 Stockholm, Sweden.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2008 (English)In: LMS Journal of Computation and Mathematics, ISSN 1461-1570, Vol. 11, 1-14 p.Article in journal (Refereed) Published
Abstract [en]

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.
National Category
Discrete Mathematics
URN: urn:nbn:se:umu:diva-52122DOI: 10.1112/S1461157000000498ISI: 000207626900001OAI: diva2:497231
Available from: 2012-02-10 Created: 2012-02-10 Last updated: 2015-05-22Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Lundow, Per-HåkanMarkström, Klas
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
LMS Journal of Computation and Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 16 hits
ReferencesLink to record
Permanent link

Direct link