Reflection positivity, rank connectivity, and homomorphism of graphs

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

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

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

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, Graph norms and Sidorenko's conjecture, 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, 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, Dual graph homomorphism functions, The bivariate Ising polynomial of a graph, Graph invariants in the spin model, An extension of the bivariate chromatic polynomial, From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems, 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, Exact and Approximate Compression of Transfer Matrices for Graph Homomorphisms, A hypergraph blow-up lemma, 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

• Unnamed Item
• Unnamed Item
• Graph invariants related to statistical mechanical models: Examples and problems
• Exponentially bounded positive definite functions
• Positive definite functions on Abelian semigroups
• The coloring of graphs
• Positive-definite functions on involution semigroups
• Edge coloring models and reflection positivity