Random graphons and a weak Positivstellensatz for graphs

DOI10.1002/jgt.20611zbMath1242.05249arXiv0902.1327OpenAlexW100995880MaRDI QIDQ2888890

Balázs Szegedy, László Lovász

Publication date: 4 June 2012

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0902.1327

zbMATH Keywords

graphongraph limitrandom graph modelweak positivstellensatz

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Related Items

Unnamed Item, Tropicalization of graph profiles, Invariant measures via inverse limits of finite structures, Undecidability of polynomial inequalities in weighted graph homomorphism densities, 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, Positive graphs, Simple graph density inequalities with no sum of squares proofs, Positivstellensätze for quantum multigraphs, The Inducibility of Graphs on Four Vertices, Counting flags in triangle-free digraphs, INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES, Percolation on an infinitely generated group

Cites Work

• Limits of dense graph sequences
• Szemerédi's lemma for the analyst
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Quick approximation to matrices and applications
• Moments of two-variable functions and the uniqueness of graph limits
• Graph limits and parameter testing
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Undecidability of linear inequalities in graph homomorphism densities
• A Sum of Squares Approximation of Nonnegative Polynomials