Non-trivial squares and Sidorenko's conjecture

Abstract

Let $t(H;G)$ be the homomorphism density of a graph $H$ into a graph $G$. Sidorenko's conjecture states that for any bipartite graph $H$, $t(H;G)\ge t(K_2;G{)}^{|E(H)|}$ for all graphs $G$. It is already known that such inequalities cannot be certified through the sums of squares method when $H$ is a so-called trivial square. In this paper, we investigate recent results about Sidorenko's conjecture and classify those involving trivial versus non-trivial squares. We then present some computational results. In particular, we categorize the bipartite graphs $H$ on at most 7 edges for which $t(H;G)\ge t(K_2;G{)}^{|E(H)|}$ has a sum of squares certificate. We then discuss other limitations for sums of squares proofs beyond trivial squares.

30 pages, 11 figures