Sidorenko猜想

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猜想可以描述为：

Sidorenko Conjecture：

∫ ∏ h(xᵢ，yⱼ)dμˢ⁺ᵗ ≥ (∫ hdμ²)ᵐ

(i，j)∈E

我们抛开上面那些复杂的数学语言和形式，Sidorenko猜想本身是极其美丽的。注意到，我们要考虑的问题本身是，给定一个二部图 H ，我们想知道在一个给定点数 n 和边密度 p 的图 G 里，能包含这个结构图 H 的数目最小值是多少？ Sidorenko猜想是说，当 G 是一个给定边密度的随机图的时候，结构图 H的数目在渐近意义下是最小的。

下面介绍一些已知的结果。

1. Sidorenko本人在1993年证明了当 H 是完全二部图 Kₛ，ₜ ，偶圈 C₂ₖ ，树时，该猜想成立。

2. Hatami在2010年证明了Cube满足Sidorenko猜想。

3. 关于该猜想的第一个大突破来源于Conlon-Fox-Sudakov，他们证明了若 H 这个二部图中，存在一个点与另一部的点全部连边，那么这个 H 满足Sidorenko猜想，这篇文章与2010年发表在GAFA，从投稿到接收只用了1个月。他们利用的就是Dependent Random Choice（话说我发现用这个方法的paper有很大的概率能提高审稿人的阅读兴趣与审稿效率）。

4. 利用entropy method，Li和Szegedy证明了一个更大的图类reflection trees满足Sidorenko猜想。他们只要利用了logarithmic convexity inequalities。文章发表在Combinatorica。

5. Conlon，Kim，J.Lee 和C.Lee将4的结果推广到了更广的一些图，称之为tree-arrangeable graphs。有几篇文章发表在JLMS，Advance，Trans AMS等期刊

6. 最近，Conlon和它的博士生Lee研究了关于Subdivision of complete graph，证明了其也满足Sidorenko猜想。以及一些相关的新图类，文章发表在Discrete Analysis上。

7. 我在梦里幻想过我证完了这个猜想，不知道是不是真的。

哈代曾经说过，There is no permanent place in the world for ugly mathematics。我感觉Sidorenko猜想本身就是个非常beautiful的猜想。关于这个猜想，我想任何的进展都会被认为是improtant的。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。