Exact and approximate compression of transfer matrices for graph homomorphisms

DOI10.1112/S1461157000000498MaRDI QIDQ3091955zbMATH OpenFDO

Authors P. H. Lundow, Klas Markström

Publication date 15 September 2011

Published in LMS Journal of Computation and Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1112/S1461157000000498

zbMATH Keywords

\(H\)-homomorphisms of lattice-like graphsapproximate compression of transfer matricesgraph homomorphismstransfer matrix compression

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Recommendations

• Compression of transfer matrices
• Transfer-matrix methods meet Ehrhart theory
• A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings
• Computing the partition function for graph homomorphisms
• Counting homomorphisms and partition functions

Cites work

• An improved upper bound for the \(3\)-dimensional dimer problem
• Compression of transfer matrices
• Graph homomorphisms and phase transitions
• scientific article; zbMATH DE number 4091530 (Why is no real title available?)
• Reflection positivity, rank connectivity, and homomorphism of graphs
• The Ising partition function for 2D grids with periodic boundary: Computation and analysis
• The matching polynomial of a polygraph
• Theory of computation of multidimensional entropy with an application to the monomer-dimer problem
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. I: General theory and square-lattice chromatic polynomial.
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. II: Extended results for square-lattice chromatic polynomial.
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. III: Triangular-lattice chromatic polynomial
• Tutte polynomials and related asymptotic limiting functions for recursive families of graphs

Cited in

(8)

• On the validations of the asymptotic matching conjectures
• Transfer-matrix methods meet Ehrhart theory
• Upper bounds on the growth rates of independent sets in two dimensions via corner transfer matrices
• Efficient computation of permanents, with applications to boson sampling and random matrices
• Compression via Matroids
• Compression of transfer matrices
• The channel capacity of read/write isolated memory
• The bivariate Ising polynomial of a graph

This page was built for publication: Exact and approximate compression of transfer matrices for graph homomorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3091955)