Sidorenko猜想 (2-1)

Sidorenko猜想可能是最近一些年，在极值组合领域里冉冉升起的一个重要猜想，或者已经可以认为是一个中心的猜想了。因为除了它本身在极值图论领域的重要性以外，他与若干其它数学分支有紧密的联系，甚至，它与诸如量子场论，量子化学，统计力学等其他科学领域有所关联。因为暂时身边，或者国内我还没有能够认识对这个猜想感兴趣的同行，所以今天想抛砖引玉一下，说不定可以吸引对这个猜想感兴趣的老师同学，一起聊聊这个问题。

给定一个图结构 H ，我们想知道在一个给定点数 n 和边密度 p 的图 G 里，能包含这个结构图 H 的数目最小值是多少。出乎意料的是，即使当 H 是最简单的三角形时，这个问题也是高度的困难的！在2007年左右，Razborov解决了当 H＝K₃ ，也就是三角形的情况。非常值得一提的是，著名的Flag Algebra的方法就是由此提出的。后来人们开始从 K₃ 向一般的完全图 Kᵣ 的研究，2008年， K₄ 的问题被解决，而直到2012年，普林斯顿大学的Christian Reiher渐近意义上解决了这个猜想，文章于2016年发表在数学领域顶尖刊物Annals of Mathematics上。2018年，我的偶像Warwick大学的刘鸿老师和合作者一起，对 K₃ 的问题进行了更细致的分析，写了一篇长为144页的Journal paper，于2020年发表在顶级刊物Forum of Mathematics, Pi上。

接下去我们把注意力放到Sidorenko猜想上，Sidorenko猜想描述的是上述问题中，当H 为二部图的情况。并且我们需要介绍一些关于图同态的概念。

一个从H 到 G 的图同态(Homomorphism)，指得是从 V(H) → V(G) 的一个保持连边关系的映射 f (map)。这里保持连边关系是指当 u，υ 在图 H连边，则f(u) 和 f(υ) 在图 G 中连边。再说一个同态密度的概念，对于给定的图 H G ，记他们的同态密度为 t(H，G) ，指的是，我们均匀随机选择一个从 V(H) → V(G)的映射，它是个从 H 到 G 的同态的概率。用数学表达式就是说：

|{f：V(H) → V(G)}：f is αhomomorphism from H to G}|

t(H，G)＝ ────────────

|V(G)|ᵛ⁽ᴴ⁾|

所以，Sidorenko猜想就是下面这个样子：

Sidorenko Conjecture：

t(H，G) ≥ t(K₂，G)|ᴱ⁽ᴴ⁾|.

当然如果你不喜欢概率密度这种写法，耶可以直接写成数同态的样子。比如说如下，

Sidorenko Conjecture：[公式] 对给定的图 H 和 G ，从 H 到 G 的同态数目至少有

2|E(G)|

(───)|ᴱ⁽ᴴ⁾| · |V(G)|ᵛ⁽ᴴ⁾|

|V(G)|²

当然，我们也可以用Graphon或者更分析的语言去表达这个猜想。

比如说，令μ 是 [0，1] 上的一个勒贝格测度，令 h(x，y) 是一个在 [0，1]² 的有界非负对称可测函数。令 H 是一个左边 u₁，u₂，. . .，uₜ，右边为 υ₁，υ₂，. . .，υₜ 的二部图， m＝|E(H)| ，那么分析语言的Sidorenko猜想可以描述为：

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。