  In an earlier paper the authors proved that limits of convergent graph
sequences can be described by various structures, including certain 2-variable
real functions called graphons, random graph models satisfying certain
consistency conditions, and normalized, multiplicative and reflection positive
graph parameters. In this paper we show that each of these structures has a
related, relaxed version, which are also equivalent. Using this, we describe a
further structure equivalent to graph limits, namely probability measures on
countable graphs that are ergodic with respect to the group of permutations of
the nodes.
  As an application, we prove an analogue of the Positivstellensatz for graphs:
We show that every linear inequality between subgraph densities that holds
asymptotically for all graphs has a formal proof in the following sense: it can
be approximated arbitrarily well by another valid inequality that is a "sum of
squares" in the algebra of partially labeled graphs.

Combinatorics;Probability