Non-trivial squares and Sidorenko's conjecture

2022/06/21 by Pranav Garg, Garg, Pranav, Annie Raymond +3 · 1 citation
Mathematics · Computer Science · #Graph theory and applications #Limits and Structures in Graph Theory #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2206.10058

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)≥ t(K₂;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)≥ t(K₂;G)^|E(H)| has a sum of squares certificate. We then discuss other limitations for sums of squares proofs beyond trivial squares.

Cited by

• Characterizing Graphs as Algebraic Squares

Related

• Sidorenko's conjecture for subdivisions and theta substitutions
• Characterizing Graphs as Algebraic Squares
• Two Approaches to Sidorenko's Conjecture
• Simple Graph Density Inequalities with no Sum of Squares Proofs
• A very short proof of Sidorenko's inequality for counts of homomorphism between graphs