Reflection positivity, rank connectivity, and homomorphism of graphs

DOI10.1090/S0894-0347-06-00529-7zbMath1107.05089arXivmath/0404468WikidataQ57308735 ScholiaQ57308735MaRDI QIDQ3420214

László Lovász, Michael Hartley Freedman, Alexander Schrijver

Publication date: 1 February 2007

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0404468

zbMATH Keywords

partition function; graph homomorphism; reflection positivity; graph parameters; connection matrix; homomorphism of graphs; rank connectivity; vertex coloring models

Mathematics Subject Classification ID

82B99: Equilibrium statistical mechanics

05C15: Coloring of graphs and hypergraphs

05C99: Graph theory

Related Items

The Complexity of Boolean Holant Problems with Nonnegative Weights, Extremal graphs for homomorphisms, A Most General Edge Elimination Polynomial, Evaluations of Graph Polynomials, Classification of a Class of Counting Problems Using Holographic Reductions, Undecidability of linear inequalities in graph homomorphism densities, The Inducibility of Graphs on Four Vertices, Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP, Graph norms and Sidorenko's conjecture, Matroid invariants and counting graph homomorphisms, On partition functions for 3-graphs, Graph parameters from symplectic group invariants, Characterizing partition functions of the vertex model, The rank of edge connection matrices and the dimension of algebras of invariant tensors, A new lower bound based on Gromov's method of selecting heavily covered points, Colouring, constraint satisfaction, and complexity, The inducibility of blow-up graphs, Positivstellensätze for quantum multigraphs, Edge-reflection positivity and weighted graph homomorphisms, Characterizing partition functions of the edge-coloring model by rank growth, The enumeration of vertex induced subgraphs with respect to the number of components, The large deviation principle for the Erdős-Rényi random graph, Distinguishing graphs by their left and right homomorphism profiles, Limits of kernel operators and the spectral regularity lemma, An analytic approach to stability, Recurrence relations for graph polynomials on bi-iterative families of graphs, Characterizing partition functions of the spin model by rank growth, Connection matrices and Lie algebra weight systems for multiloop chord diagrams, Dual graph homomorphism functions, The bivariate Ising polynomial of a graph, Graph invariants in the spin model, An extension of the bivariate chromatic polynomial, Transfer-matrix methods meet Ehrhart theory, On the existence of real R-matrices for virtual link invariants, Partition functions from orthogonal and symplectic group invariants, Complexity classification of the six-vertex model, From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems, A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights, On traces of tensor representations of diagrams, On Lie algebra weight systems for 3-graphs, Moments of two-variable functions and the uniqueness of graph limits, Graph parameters and semigroup functions, Estimating and understanding exponential random graph models, Generalized quasirandom graphs, Tensor subalgebras and first fundamental theorems in invariant theory, On the number of \(B\)-flows of a graph, Graph homomorphisms, the Tutte polynomial and “q-state Potts uniqueness”, Random graphons and a weak Positivstellensatz for graphs, Logics of Finite Hankel Rank, Exact and Approximate Compression of Transfer Matrices for Graph Homomorphisms, A hypergraph blow-up lemma, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants, Edge coloring models and reflection positivity, Connection Matrices for MSOL-Definable Structural Invariants, Contractors and connectors of graph algebras

Cites Work