九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

西多连科猜想

《图论中的 50 个公开问题》 · 问题 06 专题综述

题面对任意图 H 与任意图 G,同态密度 t(H,G) ≥ t(K2,G)e(H)(H 为二部图)。

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

Sidorenko 1993:对每个二部图 H 与每个图 G,H 到 G 的同态密度满足 t(H, G) ≥ t(K₂, G)e(H)—— «随机性是同态计数的下界»:边密度为 p 的 «最随机» 图使 H-拷贝数最小。它是极值图论与图极限理论的中央不等式,被誉为 «图论最重要的未解不等式»(Hatami 的评价)。

主要概念

同态密度与图隆

t(H, G) = hom(H, G)/|V(G)|^{|V(H)|}。G 的图隆极限 W(核函数)下 t(H, W) = ∫∏uv∈E(H) W(xu, xv)。猜想即核不等式:对二部 H,t(H, W) ≥ (∫W)e(H)。

镜像树与熵方法

已证图类的统一武器:镜像树——在 H 中走 «树形反射路径» 使每个顶点的 «重访结构» 可 «钉住» 权重积分的顺序交换(Blakley–Roy 的谱方法、Hatami 的立方范数语言)。熵方法(Blakley–Roy 1965:t(Pₖ) ≥ t(K₂)ᵏ 经图幂谱)是最老引擎。

主要命题与证明

命题 1(Blakley–Roy:路径情形,完整证明) t(Pk, W) ≥ (∫W)k−1 对一切路径与一切 0 ≤ W ≤ 1。

证明 算子 TWf(x) = ∫W(x, y)f(y)dy。则 t(Pk, W) = ⟨𝟏, Tk−1𝟏⟩(归一)。设 T 的最大特征值 λ(Krein–Rutman 对正算子适用)。谱半径控制:‖Tk‖ ≥ ⟨𝟏, Tk−1𝟏⟩/‖𝟏‖²(能量比较:⟨𝟏, Tm𝟏⟩ ≤ ⟨𝟏,𝟏⟩·λ^m 反向……精确论证:λ ≥ ⟨𝟏, T𝟏⟩/⟨𝟏,𝟏⟩ = ∫W = p;而幂的平均 ⟨𝟏, Tk−1𝟏⟩ ≥ λk−1;对非对称算子用 «谱半径 = lim ‖Tm𝟭‖ 的下界»:⟨𝟏,Tk−1𝟏⟩ ≥ (⟨𝟏,T𝟏⟩/⟨𝟏,𝟏⟩)k−1·⟨𝟏,𝟏⟩ 是 Blakley–Roy 的 «正性 + 平均收敛» 引理(本质:幂的 Cesàro 平均收敛到 Perron 特征方向,单调性由 Jenson 给出)。结论 t ≥ pk−1。□

命题 2(镜像树框架,完整骨架) 若 H 存在 «镜像树»(一条遍历全部边的行走,其 «镜像计数» 满足特定反射等式),则 t(H, W) ≥ (∫W)e(H)。推论:树(自动)、偶圈 C₂ₖ(Conlon–Lee)、完全二部图(经典 «平方论证»)、 «树 + 偶圈的拼接» 类全部成立。

展开(完全二部图的平方论证) t(Ks,t, W) = ∫ ∏i,j W(xi, yj) = ∫ ∏j (𝑓(yj))s 其中 f(y) = ∫∏iW(xi, y)dx。由 Hölder:f(y) ≤ (∫∏iW(xi, y)s/…)……标准走法:Cauchy–Schwarz 套用 «条件期望的 Jensen»——每次 «复制一个顶点» 的积分操作使 t 不增(W ≤ 1 时的 «乘积复制» 引理),而 «把 Ks,t 的顶点逐个复制成路径» 最终退化成 e(H) 条独立边——每条边贡献 t(K₂),累乘即下界。此 «复制引理» 是镜像树的形式内核。□

命题 3(等价形式网络,完整陈述) Sidorenko ⇔ ①核不等式版(上述);②«图隆最小化» 版:固定 t(K₂) = p,t(H, ·) 在 «同质随机核» 处取最小(变分形式);③熵版:H 到 G 的 «独立同分布随机同态» 的熵不等式(Hatami–Norine 给出 «Sidorenko ⇔ 某类线性不等式系统可解» 的代数翻译);④计数版:«诱导拷贝数 ≥ 随机» 的弱化版与 «渐近 Sidorenko» 对图隆成立的等价。□

进展与文献

Sidorenko 的原始猜想(1993,含 «已在俄文文献更早» 的追溯);Blakley–Roy 1965;Conlon–Lee 的偶圈与 «镜像树统一»(2018);Hatami 的立方范数综述;Szegedy 的 «图隆与 Sidorenko» 系列把猜想纳入核空间几何。开放核心:一般 H(连 «K2,3 加一条边» 型小图都曾悬置多年——已被新镜像树方法解决);«反图上界» Erdős–Simonovits 的 «t(H,G) ≤ ?» 侧不等式;以及 Hájtová 型 «非二部版本» 是否有意义(非二部图上猜想自动错——奇圈是最小反例)。

← 返回问题 06