Non-trivial squares and Sidorenko's conjecture

arXiv2206.10058MaRDI QIDQ6402663FDOQ6402663

Authors: Pranav Garg, Annie Raymond, Amanda Redlich 

Publication date: 20 June 2022

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)geqt(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)geqt(K_2;G{)}^{|E(H)|}$ has a sum of squares certificate. We then discuss other limitations for sums of squares proofs beyond trivial squares.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

This page was built for publication: Non-trivial squares and Sidorenko's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402663)