Reflection positivity, rank connectivity, and homomorphism of graphs

By Michael H. Freedman, L. Lov'asz, Alexander Schrijver. 2004

199 citations recorded by the source corpus.

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.

Subfields: Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/345a531d43323e15fbccc207e77b793844fd6a88

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Graph norms and Sidorenko’s conjecture (2008, background): “Despite all the machinery that is developed in recent years [10, 2] and has been applied successfully to some important questions [23], still there are many questions regarding these functions that are remained unsolved.”
Regularity Partitions and The Topology of Graphons (2010, background): “) The notion of the density of a graph in a graphon has been introduced in [7].”
Limits of dense graph sequences (2004, background): “6), and then that (a)⇒(c) (which follows from the characterization of homomorphism functions in [5]).”
Counting Graph Homomorphisms (2006, background): “Graph parameters arising this way were characterized in [28].”
Estimating and understanding exponential random graph models (2011, background): “In a sequence of papers [9, 10, 11, 25, 37, 38, 39, 40, 41, 42, 43], Laszlo Lovász and coauthors V.”