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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1601019 (Why is no real title available?)
- scientific article; zbMATH DE number 4004880 (Why is no real title available?)
- scientific article; zbMATH DE number 1490041 (Why is no real title available?)
- A Sum of Squares Approximation of Nonnegative Polynomials
- Algorithms in invariant theory
- Closures of quadratic modules
- Counting graph homomorphisms
- Extremal positive semidefinite forms
- Graph invariants related to statistical mechanical models: Examples and problems
- Large networks and graph limits
- Limits of dense graph sequences
- Positive polynomials and sums of squares
- Pólya's theorem with zeros
- Random graphons and a weak positivstellensatz for graphs
- Reflection positivity, rank connectivity, and homomorphism of graphs
- SOS approximations of nonnegative polynomials via simple high degree perturbations
- The K-moment problem for compact semi-algebraic sets
- Undecidability of linear inequalities in graph homomorphism densities
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)
