Positivstellensätze for quantum multigraphs

DOI10.1016/J.JALGEBRA.2014.08.053zbMATH Open1302.05123arXiv1310.6903OpenAlexW2963839924WikidataQ61677653 ScholiaQ61677653MaRDI QIDQ471898FDOQ471898

Authors: Tim Netzer, Andreas Thom 

Publication date: 17 November 2014

Published in: Journal of Algebra (Search for Journal in Brave)

Abstract: Studying inequalities between subgraph- or homomorphism-densities is an important topic in graph theory. Sums of squares techniques have proven useful in dealing with such questions. Using an approach from real algebraic geometry, we strengthen a Positivstellensatz for simple quantum graphs by Lov'asz and Szegedy, and we prove several new Positivstellens"atze for nonnegativity of quantum multigraphs. We provide new examples and counterexamples.

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

Recommendations

• Undecidability of linear inequalities in graph homomorphism densities
• Simple graph density inequalities with no sum of squares proofs
• Random graphons and a weak positivstellensatz for graphs
• Tropicalization of graph profiles
• Multigraph approach to quantum non-locality

zbMATH Keywords

graph parametersums of squaresnonnegativitypositivstellensatzhomomorphism density

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Real algebraic and real-analytic geometry (14P99)

Cites Work

• Limits of dense graph sequences
• Large networks and graph limits
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Counting graph homomorphisms
• The \(K\)-moment problem for compact semi-algebraic sets
• Pólya's theorem with zeros
• Title not available (Why is that?)
• Extremal positive semidefinite forms
• Algorithms in invariant theory
• Positive polynomials and sums of squares
• Graph invariants related to statistical mechanical models: Examples and problems
• Undecidability of linear inequalities in graph homomorphism densities
• Closures of quadratic modules
• Random graphons and a weak positivstellensatz for graphs
• A Sum of Squares Approximation of Nonnegative Polynomials
• SOS approximations of nonnegative polynomials via simple high degree perturbations

Cited In (5)

• Undecidability of linear inequalities in graph homomorphism densities
• Tropicalization of graph profiles
• Positive graphs
• Matrix extreme points and free extreme points of free spectrahedra
• Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting)

This page was built for publication: Positivstellensätze for quantum multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q471898)