Non-Trivial Squares and Sidorenko's Conjecture
The electronic journal of combinatorics, Tome 32 (2025) no. 4
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)\geq 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)\geq 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.
@article{10_37236_11339,
author = {Pranav Garg and Annie Raymond and Amanda Redlich},
title = {Non-Trivial {Squares} and {Sidorenko's} {Conjecture}},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {4},
doi = {10.37236/11339},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11339/}
}
Pranav Garg; Annie Raymond; Amanda Redlich. Non-Trivial Squares and Sidorenko's Conjecture. The electronic journal of combinatorics, Tome 32 (2025) no. 4. doi: 10.37236/11339
Cité par Sources :