Reflection positivity, rank connectivity, and homomorphism of graphs

DOI10.1090/S0894-0347-06-00529-7zbMath1107.05089arXivmath/0404468OpenAlexW2141382791WikidataQ57308735 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

Equilibrium statistical mechanics (82B99) Coloring of graphs and hypergraphs (05C15) Graph theory (05C99)

Related Items

Perfect matchings, rank of connection tensors and graph homomorphisms, Random graphons and a weak Positivstellensatz for graphs, Zero-freeness and approximation of real Boolean Holant problems, Moments of two-variable functions and the uniqueness of graph limits, A Most General Edge Elimination Polynomial, Evaluations of Graph Polynomials, Transfer-matrix methods meet Ehrhart theory, On partition functions for 3-graphs, Graph parameters from symplectic group invariants, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, The odd-valued chromatic polynomial of a signed graph, Classification of a Class of Counting Problems Using Holographic Reductions, The Complexity of Boolean Holant Problems with Nonnegative Weights, Forcing operators on star graphs applied for the cubic fourth order Schrödinger equation, Logics of Finite Hankel Rank, From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems, On the existence of real R-matrices for virtual link invariants, Graphon convergence of random cographs, New directions in real algebraic geometry. Abstracts from the workshop held March 19--24, 2023, Partition functions from orthogonal and symplectic group invariants, Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants, Undecidability of polynomial inequalities in weighted graph homomorphism densities, Graph parameters and semigroup functions, Characterizing partition functions of the vertex model, Connection matrices and Lie algebra weight systems for multiloop chord diagrams, Homomorphisms between graphs embedded in surfaces, The rank of edge connection matrices and the dimension of algebras of invariant tensors, Complexity classification of the six-vertex model, Estimating and understanding exponential random graph models, A new lower bound based on Gromov's method of selecting heavily covered points, 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, Colouring, constraint satisfaction, and complexity, The inducibility of blow-up graphs, Positivstellensätze for quantum multigraphs, Edge-reflection positivity and weighted graph homomorphisms, On the Complexity of Holant Problems, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Undecidability of linear inequalities in graph homomorphism densities, Characterizing partition functions of the edge-coloring model by rank growth, Generalized quasirandom graphs, Tensor subalgebras and first fundamental theorems in invariant theory, The Inducibility of Graphs on Four Vertices, Dual graph homomorphism functions, Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP, The bivariate Ising polynomial of a graph, An analytic approach to stability, Edge coloring models and reflection positivity, Connection Matrices for MSOL-Definable Structural Invariants, Contractors and connectors of graph algebras, Mixed partition functions and exponentially bounded edge-connection rank, Extremal graphs for homomorphisms, Dichotomy for Holant\(^\ast\) problems on the Boolean domain, On the number of \(B\)-flows of a graph, Graph norms and Sidorenko's conjecture, Graph invariants in the spin model, Dichotomy result on 3-regular bipartite non-negative functions, Recurrence relations for graph polynomials on bi-iterative families of graphs, Characterizing partition functions of the spin model by rank growth, Bipartite 3-regular counting problems with mixed signs, Dichotomy result on 3-regular bipartite non-negative functions, Bipartite 3-regular counting problems with mixed signs, Exact and Approximate Compression of Transfer Matrices for Graph Homomorphisms, A hypergraph blow-up lemma, Approximability of the eight-vertex model, FKT is not universal -- a planar holant dichotomy for symmetric constraints, A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights, An extension of the bivariate chromatic polynomial, Graph homomorphisms, the Tutte polynomial and “q-state Potts uniqueness”, On traces of tensor representations of diagrams, On Lie algebra weight systems for 3-graphs, Matroid invariants and counting graph homomorphisms

Cites Work