Random graphons and a weak positivstellensatz for graphs
From MaRDI portal
Abstract: 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.
Recommendations
Cites work
- A Sum of Squares Approximation of Nonnegative Polynomials
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Graph limits and parameter testing
- Limits of dense graph sequences
- Moments of two-variable functions and the uniqueness of graph limits
- Quick approximation to matrices and applications
- Reflection positivity, rank connectivity, and homomorphism of graphs
- Szemerédi's lemma for the analyst
- Undecidability of linear inequalities in graph homomorphism densities
Cited in
(26)- Characteristic power series of graph limits
- Simple graph density inequalities with no sum of squares proofs
- Limits of random trees. II
- Differential calculus on graphon space
- Moments of two-variable functions and the uniqueness of graph limits
- Poset limits and exchangeable random posets
- Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting)
- Multigraph limit of the dense configuration model and the preferential attachment graph
- Defining recursive predicates in graph orders
- Positivstellensätze for quantum multigraphs
- Percolation on an infinitely generated group
- On derivatives of graphon parameters
- Tropicalization of graph profiles
- Graphons, permutons and the Thoma simplex: three mod-Gaussian moduli spaces
- Limits of order types
- Undecidability of linear inequalities in graph homomorphism densities
- The inducibility of graphs on four vertices
- INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES
- Harmonic analysis of symmetric random graphs.
- Positive graphs
- Limits of multi-relational graphs
- Undecidability of polynomial inequalities in weighted graph homomorphism densities
- Undecidability of polynomial inequalities in tournaments
- Limits of dense graph sequences
- Invariant measures via inverse limits of finite structures
- The Grothendieck constant of random and pseudo-random graphs
This page was built for publication: Random graphons and a weak positivstellensatz for graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2888890)
