Simple graph density inequalities with no sum of squares proofs

DOI10.1007/s00493-019-4124-yzbMath1474.05210arXiv1812.08820OpenAlexW3009908098WikidataQ113904983 ScholiaQ113904983MaRDI QIDQ2221001

Grigoriy Blekherman, Rekha R. Thomas, Annie Raymond, Mohit Singh

Publication date: 25 January 2021

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

sum of squareshomomorphism density

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Semidefinite programming (90C22)

Related Items

Symmetry Reduction in AM/GM-Based Optimization, Tropicalization of graph profiles, Simple graph density inequalities with no sum of squares proofs

Cites Work

• Unnamed Item
• Limits of dense graph sequences
• Bounds on arithmetic projections, and applications to the Kakeya conjecture
• Symmetry in Turán sums of squares polynomials from flag algebras
• Symmetric sums of squares over \(k\)-subset hypercubes
• On the number of pentagons in triangle-free graphs
• Simple graph density inequalities with no sum of squares proofs
• A correlation inequality for bipartite graphs
• Two approaches to Sidorenko’s conjecture
• Random graphons and a weak Positivstellensatz for graphs
• On 3-Hypergraphs with Forbidden 4-Vertex Configurations
• Sidorenko's conjecture for blow-ups
• A multilinear generalisation of the Cauchy-Schwarz inequality
• Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
• Undecidability of linear inequalities in graph homomorphism densities
• Flag algebras
• A Holder Type Inequality for Symmetric Matrices with Nonnegative Entries