Reflection positivity, rank connectivity, and homomorphism of graphs

2004/04/26 by M. Freedman, Michael Freedman, Freedman, M. +6 · 3 citations
Mathematics · Physics and Astronomy · #05C99 (Primary) #82B99 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Graph theory and applications #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Random Matrices and Applications #math-ph #math.CO #math.MP #msc:05C99 #msc:82B99

paper · pdf · doi:10.48550/arxiv.math/0404468

17 pages Latex

arxiv created 2004/04/26 · openalex publication_date 2004/04/26 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

It is shown that a graph parameter can be realized as the number of homomorphisms into a fixed (weighted) graph if and only if it satisfies two linear algebraic conditions: reflection positivity and exponential rank-connectivity. In terms of statistical physics, this can be viewed as a characterization of partition functions of vertex models.

Cited by

• A Nonhomogeneous Boundary-Value Problem For The Nonlinear KdV Equation on Star Graphs
• Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem
• Using dense graph limit theory to count cocycles of random simplicial complexes

Related

• Edge-reflection positivity and weighted graph homomorphisms
• Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms
• Counting Homomorphisms and Partition Functions
• Mixed partition functions and exponentially bounded edge-connection rank
• The graph theoretic moment problem