Simple graph density inequalities with no sum of squares proofs (Q2221001)

Let \(H\) and \(G\) be graphs without loops and multiple edges. Then a mapping \(f:V(H)\rightarrow V(G)\) is called a graph homomorphism if the map induced by \(f\) assigns to each edge of \(H\) an edge of \(G\). The probability of a random mapping from \(V(H)\) to \(V(G)\) to be a graph homomorphism, denoted by \(t(H;G),\) is called the homomorphism density of a graph \(H\) in a graph \(G\). An expression containing homomorphism densities is non-negative if it holds for all graphs \(G\). A standard method to prove the non-negativity of a density expression is to write it as a sum of squares. The main result of this paper provides a simple sufficient condition for a density expression not to be representable as a sum of squares. Using this result, the authors show that the non-negativity of some non-negative density expressions cannot be proved by the sum of squares method. These results answer in the affirmative two questions raised by Lovász.