Search

A graph profile records all possible densities of a fixed finite set of graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known, and little is known about hypergraph profiles. We introduce the tropicalization of graph and hypergraph profiles. Tropicalization is a well-studied operation in algebraic geometry, which replaces a variety (the set of real or complex solutions to a finite set of algebraic equations) with its "combinatorial shadow". We prove that the tropicalization of a graph profile is a closed convex cone, which still captures interesting combinatorial information. We explicitly compute these tropicalizations for arbitrary sets of complete and star hypergraphs. We show they are rational polyhedral cones even though the corresponding profiles are not even known to be semialgebraic in some of these cases. We then use tropicalization to prove strong restrictions on the power of the sums of squares method, equivalently Cauchy-Schwarz calculus, to test (which is weaker than certification) the validity of graph density inequalities. In particular, we show that sums of squares cannot test simple binomial graph density inequalities, or even their approximations. Small concrete examples of such inequalities are presented, and include the famous Blakley-Roy inequalities for paths of odd length. As a consequence, these simple inequalities cannot be written as a rational sum of squares of graph densities. [ABSTRACT FROM AUTHOR]

The article examines the connection between varieties of minimal degree and sums of squares. Topics covered include the relation of nonnegativity with sums of squares, generalization of Hilbert's 1888 classification of nonnegative firms, connection between real and complex algebraic geometry and list of varieties for which nonnegative quadratic forms are sums of squares.

We introduce positive Gorenstein ideals. These are Gorenstein ideals in the graded ring R[x] with socle in degree 2d which when viewed as a linear functional on R[x]2d is nonnegative on squares. Equivalently, positive Gorenstein ideals are apolar ideals of forms whose differential operator is nonnegative on squares. Positive Gorenstein ideals arise naturally in the context of nonnegative polynomials and sums of squares, and they provide a powerful framework for studying concrete aspects of sums of squares representations. We present applications of positive Gorenstein ideals in real algebraic geometry, analysis and optimization. In particular, we present a simple proof of Hilbert's nearly forgotten result on representations of ternary nonnegative forms as sums of squares of rational functions. Drawing on our previous work (2012), our main tools are Cayley-Bacharach duality and elementary convex geometry. [ABSTRACT FROM AUTHOR]

The article explores the linear inequalities that differentiate nonnegative polynomials from sums of squares (soS). An equation for the definining linear inequalities for the nonnegative polynomials or positive semidefinite (psd) cone is given. It discusses the derivation of inequalities using the Cayley-Bacharach relation. A description of the differences between attainable values of psd and sos forms on the intersection segments is also provided.