论文标题
非平凡的正方形和Sidorenko的猜想
Non-trivial squares and Sidorenko's conjecture
论文作者
论文摘要
令$ t（h; g）$为图$ g $的图$ h $的同构密度。 Sidorenko的猜想指出，对于任何两部分图$ h $，$ t（h; g）\ geq t（k_2; g）^{| e（h）|} $用于所有图形$ g $。众所周知，当$ h $是一个所谓的琐碎广场时，这种不平等现象无法通过平方法的总和进行认证。在本文中，我们研究了有关Sidorenko的猜想的最新结果，并将涉及琐碎和非平凡正方形的结果进行了分类。然后，我们提出一些计算结果。特别是，我们在最多7个边上对两分图$ h $进行了分类，其中$ t（h; g）\ geq t（k_2; g）^{| e（h）|} $具有平方证书的总和。然后，我们讨论了超出琐碎正方形以外的正方形证明总和的其他局限性。
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.
