西多连科猜想在图的细分与θ图替换中的新进展：偶路径广义θ图与局部稠密性的统一证明

《Combinatorics, Probability and Computing》：Sidorenko’s conjecture for subdivisions and theta substitutions

本文聚焦于极值图论中的西多连科猜想（Sidorenko's conjecture），该猜想断言所有二分图在同态密度意义下均满足最小性条件。研究人员针对如何构造新的西多连科图类这一关键问题，系统研究了通过将图的边替换为偶路径构成的广义θ图（even generalised theta graph）所得到的图结构。他们证明了当原图满足KNRS猜想（Kohayakawa-Nagle-Rodl-Schacht conjecture）时，此类替换图必为西多连科图；进一步地，在满足特定整除性条件下，对任意图进行非均匀的偶路径θ图替换，其所得图同样满足西多连科猜想。该研究统一并推广了Conlon等人关于图细分与θ图的已有结果，为理解图同态密度的极小性提供了新工具。

　　

在极值图论这片充满挑战与未知的领域中，西多连科猜想（Sidorenko's conjecture）犹如一颗璀璨的明珠，吸引着无数组合数学家为之倾注心血。这个猜想断言，对于任何一个二分图H，其在任意图G中的同态密度t_H(G)至少达到其边密度t_K2(G)的e(H)次方。通俗地说，就是在所有给定边密度的图中，随机图容纳H副本的数量是最少的。尽管自提出以来，该猜想已在树、偶环、完全二分图等特殊图类上得到验证，但其普遍正确性仍是一个悬而未决的难题。

与西多连科猜想紧密相关的是KNRS猜想（Kohayakawa-Nagle-Rodl-Schacht conjecture），它关注的是在局部稠密图（locally dense graph）中，特定子图数量的下界问题。一个自然的问题是，这两个猜想之间是否存在深刻的联系？能否利用一个猜想的结果来推进另一个猜想的解决？近年来，Conlon, Kim, Lee 和 Lee 等人开创性地建立了这种联系，他们证明：如果一个图H满足KNRS猜想，那么它的1-细分图（1-subdivision）就满足西多连科猜想。此外，他们还证明了由偶路径组成的广义θ图（even generalised theta graph，即连接两个根顶点的一组内部不交的偶路径构成的图）本身也是西多连科图。这些成果为构造新的西多连科图类打开了新局面，但也留下了更深远的问题：对于更复杂的图变换，例如用更一般的图结构（而不仅仅是单条路径或简单的K_2,t）去替换原图的边，西多连科性质是否依然能够保持？替换过程是否可以是非均匀的（即对原图的不同边使用不同的替换图）？这些正是Seonghyuk Im, Ruonan Li 和 Hong Liu 在发表于《Combinatorics, Probability and Computing》的这篇论文中旨在回答的核心问题。

为了回答上述问题，研究人员主要运用了图论极限理论（graph limit theory）中的图子（graphon）工具。他们将图子作为宿主图的连续类比，从而在分析上处理同态密度问题。关键技术方法包括：1) 定义并分析用于计数特定子图（如广义θ图）的辅助图子W^Θ；2) 证明在d-正则图子W下，由偶广义θ图Θ生成的辅助图子W^Θ是d^e(Θ)-局部稠密的（Lemma 3.2），这是证明主要结果的核心引理；3) 运用H?lder不等式（Theorem 2.8）将非均匀替换情况下的同态密度下界估计转化为均匀替换情况下的问题，从而利用已证结果；4) 利用KNRS图的性质（Lemma 2.7）和西多连科图的性质，通过积分和Jensen不等式等进行下界估计。研究过程中未涉及生命科学领域的样本队列或实验技术。

研究结果

1. 从KNRS图到西多连科图的统一构造（Theorem 1.3）

研究人员首先证明了，如果图H满足KNRS猜想，那么将H的每一条边替换为同一个偶广义θ图Θ后所得到的新图H'必然是西多连科图。证明的关键在于Lemma 3.2，它表明当W是d-正则图子时，辅助图子W^Θ具有良好的局部稠密性。由于H是KNRS的，它在局部稠密的图子中同态密度有下界，因此t_H'(W) = t_H(W^Θ) ≥ (d^e(Θ))^e(H)= d^e(H')，从而H'是西多连科的。这一结果统一并推广了之前关于1-细分图和偶广义θ图的结论。

2. 非均匀替换与整除性条件（Theorem 1.4）

更进一步的，研究团队将目光投向了非均匀替换的情形。即，对于任意图H，将其每条边e替换为一组内部不交的偶路径（构成一个广义θ图），但允许不同边e被替换的路径长度和数量（记为h_e(2k)，表示在边e的替换中使用长度为2k的路径数）可以不同。他们发现，如果对于每个路径长度2k，所有边替换中使用的该长度路径总数∑_e∈E(H)h_e(2k)能够被顶点对数目^hC₂整除，那么如此得到的图H'仍然是西多连科图。此外，如果所有替换路径只有一种长度2k，且该长度路径的总数不少于^hC₂，H'也是西多连科图。证明巧妙地运用了H?lder不等式，通过对所有顶点排列取平均，将非均匀情况下的同态密度下界转化为一个“均匀化”的图（可视为完全图K_h的边被一个特定的广义θ图替换所得图）的同态密度，从而化归为Theorem 1.3的情形。

3. 特殊 clique 细分的西多连科性质（Theorem 1.6）

作为非均匀细分的一个具体而重要的例子，论文证明了一类特殊的团（clique）细分图是西多连科图。具体来说，考虑完全图K_h，对其边进行细分：所有不关联于某个特定顶点v的边被细分2?₁-1次（即变为长度2?₁的路径），而所有关联于v的边被细分2?₂次（即变为长度2?₂+1的路径，但注意要使最终图为二分图，需要奇数次细分，此处表述需核对原文，Theorem 1.6中提及的是?₂次，可能指细分后路径段数，最终路径长度需计算）。这样得到的二分图H被证明满足西多连科猜想。这个定理实际上是下一个更一般定理的特例。

4. 图乘积与细分操作的结合（Theorem 1.7）

研究人员引入了一个由Bradac, Sudakov 和 Wigderson提出的图乘积操作?_I^a。给定图H₁，其一个独立集I，以及一个顶点a?I，和图H₂，乘积图H₁?_I^aH₂是通过将H₂的每个顶点对应一个H₁的拷贝（这些拷贝在I上重合），然后将所有拷贝中的顶点a拿出来，并在这组顶点上放置一个H₂的拷贝而得到的。Theorem 1.7断言，如果H₁是西多连科图，H₂是KNRS图，那么对乘积图中对应于H₂的边进行2k-1次细分（或替换为偶广义θ图）后得到的图F，是西多连科图。Theorem 1.6中的特殊clique细分可以通过巧妙地选择H₁（一条路径）、H₂（K_h-1）和细分参数，作为此定理的应用而得到。

5. 花图（Flower）的KNRS性质（Theorem 1.8）

最后，论文研究了“花图”（flower），即共享一个公共顶点、其余部分互不相交的若干圈的并集。研究者证明了任何花图都满足KNRS猜想。证明的关键是应用Reiher引理（Lemma 2.6）于花图中的每个奇圈，将花图的计数问题转化为一个树的计数问题，然后利用树是西多连科图的性质得出下界。由于花图的1-细分是偶广义θ图，这也从另一个角度印证了偶广义θ图的西多连科性质。

结论与意义

本研究的结论深刻推进了对西多连科猜想和KNRS猜想的理解。首先，Theorem 1.3和Theorem 1.4极大地扩展了已知的西多连科图类，提供了从KNRS图或任意图出发，通过均匀或非均匀的偶广义θ图替换来系统构造西多连科图的有效方法。这统一了先前关于图细分和θ图的分散结果，揭示了局部稠密性（KNRS性质）与全局最小性（西多连科性质）之间更普遍的联系机制。其次，Theorem 1.7创新性地将图乘积操作引入西多连科猜想的框架，并指出通过适当的细分操作，可以将非二分图乘积转化为满足猜想的二分图，这为处理更复杂的图结构提供了新思路。最后，Theorem 1.8首次证实了花图这类具有循环结构的图是KNRS的，丰富了KNRS图类。

这些成果不仅具有理论上的突破意义，其证明过程中发展出的技术方法，特别是关于辅助图子局部稠密性的分析（Lemma 3.2）以及利用H?lder不等式处理非均匀性的策略，为解决极值图论中其他相关的计数问题提供了有力的新工具。论文最后提出了关于任意二分细分图都是西多连科图的宏大猜想（Conjecture 4.1），为未来的研究指明了方向。总之，这项研究通过深刻的分析和巧妙的构造，在西多连科猜想这一长期悬而未决的问题上取得了重要进展，巩固并深化了我们对图同态密度极小性的认知。