Exact and Approximate Compression of Transfer Matrices for Graph Homomorphisms

DOI10.1112/S1461157000000498zbMath1223.05177MaRDI QIDQ3091955

Per Håkan Lundow, Klas Markström

Publication date: 15 September 2011

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

zbMATH Keywords

graph homomorphisms; \(H\)-homomorphisms of lattice-like graphs; approximate compression of transfer matrices; transfer matrix compression

Mathematics Subject Classification ID

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics

05C15: Coloring of graphs and hypergraphs

Related Items

The channel capacity of read/write isolated memory, The bivariate Ising polynomial of a graph, 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

Cites Work

• Unnamed Item
• The matching polynomial of a polygraph
• 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
• Graph homomorphisms and phase transitions
• The Ising partition function for 2D grids with periodic boundary: Computation and analysis
• An improved upper bound for the \(3\)-dimensional dimer problem
• Theory of computation of multidimensional entropy with an application to the monomer-dimer problem
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Compression of transfer matrices
• 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.