结果族 186：Uniform influence and sharp thresholds for graph and hypergraph properties · 学科：Combinatorics · 验证状态：暂无形式化证明，请以社区核验为准
在随机图上慢慢撒网：每条边以概率 p 独立出现，p 从 0 拉到 1。”变得连通”“出现三角形”这类不挑顶点的性质，一旦开始发生就发生得飞快——像推倒的多米诺。论文证明：对一切顶点置换不变的非平凡单调图性质，概率从 ε 涨到 1−ε 的 p 区间宽度至多 C·log(1/(2ε))/(log n)²，分母的平方正是最优阶——解决了 Friedgut–Kalai 1996 年尖阈值猜想。
关键词卡片
看个具体例子
数字版：n=10^6 时 (ln n)² ≈ 191，宽度至多 C·log(1/(2ε))/191。最优性由反例保证：包含大小与 log n 成比例的团的性质，其宽度本身就达到 (log n)^(−2) 阶，平方不能再改进；此前最好结果带 η 或 (log log n)² 的损失。
为什么值得关心
尖阈值解释了大规模随机网络的状态切换为何如此突然，也是组合、概率与算法分析共用的基本工具；姊妹篇把同一方法推广到 r-一致超图。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读的”慢慢撒网、多米诺骤倒”说的是：对象是随机图——n 个顶点间每条可能的边独立地以概率 p 出现，性质是边集组成的族（如”连通”“含三角形”）；操作是把 p 从 0 拉到 1。对称条件是不挑顶点名字。现象是：一旦开始发生，概率飙升极快；要量化的是”从 ε 涨到 1−ε”到底占多窄的一段 p。
第二级台阶
用本科语言精确化：图性质指在每个顶点置换下不变的边集族；单调（递增）指加边只可能让图进入该族。阈值宽度为 p_{1−ε}(P) − p_ε(P)，其中 p_a(P) 是性质概率首次达到 a 的边概率。边 e 的枢轴影响是翻转该边翻转结论的概率，总影响 I_p(f) 为其求和；Margulis–Russo 恒等式 μ′(p) = I_p 把”概率增速”与”影响力”精确挂钩。
第三级台阶
定理的语境是 Friedgut–Kalai 1996 年猜想。他们用边坐标上的传递性只能证出宽度 O(log(1/(2ε))/log n)，并猜想完整的顶点置换对称应把分母平方化，且以”含大小正比于 log n 的团”说明此阶最优。驱动引擎是定理 2：一切顶点置换不变的布尔函数满足 Var_p(f) ≤ 2^17·I_p(f)/(log n)²，对一切 0 < p < 1 一致成立、无需单调——”一致于 p”挡住了此前 Bourgain–Kalai 的 η 损失与 KKLMS 只在 p=1/2 处有效的软肋。结论即定理 1：非平凡递增图族的宽度至多 2^19·log(1/(2ε))/(log n)²，猜想被正面解决。平方的来源是纯组合的：s ≤ k²/2 条边的图必有度至多 k 的非孤立点，”条件度 k”由此升级为”原始度 k²/2”。
证明了 Friedgut–Kalai 1996 年提出的尖阈值（sharp threshold）猜想：@@M@@n@@ 个顶点的图上，任何在全体顶点置换下不变的非平凡单调性质，从概率 @@M@@\varepsilon@@ 涨到 @@M@@1-\varepsilon@@ 的边概率区间宽度至多 @@M@@2^{19}\log(1/(2\varepsilon))/(\log n)^2@@，分母中的平方为最优阶。
把图看成 @@M@@\{0,1\}^{E_n}@@ 中的点（@@M@@E_n@@ 为完全图的边集），每条边以概率 @@M@@p@@ 独立出现；图性质（graph property）是在每个顶点置换下不变的边集族，单调（monotone）指加边保持隶属。Friedgut 与 Kalai 在 1996 年利用 KKL 影响力不等式和 Margulis–Russo 概率导数公式证明：传递置换群下不变的单调图性质必有窄的过渡区间，宽度（threshold width）为 @@M@@O(\log(1/(2\varepsilon))/\log n)@@；他们同时猜想（原文 Conjecture 1.2）顶点置换群比”传递”丰富得多的结构应把分母改进为 @@M@@(\log n)^2@@，并指出此阶最优——包含大小与 @@M@@\log n@@ 成比例的团（clique）这一性质，其过渡宽度就能达到 @@M@@(\log n)^{-2}@@ 阶。此后 Bourgain–Kalai（1997）把宽度推进到 @@M@@(\log n)^{-2+\eta}@@（任意固定 @@M@@\eta>0@@）；Kelman–Kindler–Lifshitz–Minzer–Safra 又在 @@M@@p=1/2@@ 处证明了 @@M@@I_{1/2}(f)\ge c(\log n)^2\Var_{1/2}(f)/(\log\log n)^2@@ 的影响力下界。卡点：阈值宽度需要方差–影响力不等式在整个过渡区间上对一切 @@M@@0<p<1@@ 一致，而已有结果或只在无偏测度处有效，或残留 @@M@@\eta@@、重对数损失。
记 @@M@@\mu_p(\mathcal P)@@ 为随机图属于 @@M@@\mathcal P@@ 的概率，@@M@@p_a(\mathcal P)=\inf\{p:\mu_p(\mathcal P)\ge a\}@@；文中对数均以顶点数 @@M@@n@@ 为尺度。
定理 1（Friedgut–Kalai 猜想）：对每个 @@M@@n\ge2@@、每个在全体顶点置换下不变的非平凡增图族 @@M@@\mathcal P@@ 及每个 @@M@@0<\varepsilon<1/2@@，
@@M@@Dp_{1-\varepsilon}(\mathcal P)-p_\varepsilon(\mathcal P)\le\frac{2^{19}}{(\log n)^2}\log\frac1{2\varepsilon}.@@
其驱动引擎是定理 2（方差与影响力）：对每个 @@M@@n\ge2@@、每个在顶点置换下不变的布尔函数 @@M@@f@@ 与每个 @@M@@0<p<1@@（同样不需要单调），
@@M@@D\Var_p(f)\le\frac{2^{17}}{(\log n)^2}I_p(f),@@
其中 @@M@@I_p(f)=\sum_e\Pr_p(f(x_{e\leftarrow1})\ne f(x_{e\leftarrow0}))@@ 为总枢轴影响力（total pivotal influence）。文中还由中位数 @@M@@p_*=p_{1/2}@@ 出发给出过渡曲线的双侧估计：@@M@@\mu(p_*-s)@@ 与 @@M@@1-\mu(p_*+s)@@ 都不超过 @@M@@1/(1+\exp(s(\log n)^2/C_0))@@。
证明分四步：偏倚傅里叶分析、低阶引理、随机顶点块限制、积分得宽度。
先在偏倚乘积测度上建立傅里叶展开（基 @@M@@\chi_i=(x_i-p)/\sigma@@，@@M@@\sigma=\sqrt{p(1-p)}@@），得到两条恒等式：方差是全部非空系数的平方和；加权 Dirichlet 型恒等式 @@M@@\sum_S|S|\hat f(S)^2=\sigma^2I_p(f)@@ 把高傅里叶度（degree）的质量用总影响力封顶。于是全部困难集中在低阶部分。
第二步证明低阶引理：当每个坐标的影响力都不超过总影响的 @@M@@1/m@@ 时，对噪声算子 @@M@@T_\rho@@（@@M@@\rho=\sigma/4@@）建立二到四范数不等式 @@M@@\|T_\rho g\|_4\le\|g\|_2@@——这是 KKL 与 Bonami 超收缩性（hypercontractivity）论证的核心，文中对偏倚情形给出自足的显式证明——经对偶得 @@M@@\|P_{\le k}g\|_2\le\rho^{-k}\|g\|_{4/3}@@，作用到离散导数上并分情况讨论，得 @@M@@\sum_{1\le|S|\le k}\hat h(S)^2\le m^{-1/4}I(h)@@，@@M@@k=\sigma\log m/64@@。右端关于 @@M@@I(h)@@ 线性，这一线性使后续平均合法。
第三步是全文最有创意的顶点块限制（restriction）：均匀随机取约 @@M@@\sqrt n@@ 个顶点的块 @@M@@B@@，把与 @@M@@B@@ 相交的边全部留作自由坐标，其余边赋值固定。由于 @@M@@B@@ 内部的置换逐条固定外部边，任何赋值下限制函数仍享有块内完全对称；自由边的轨道（@@M@@B@@ 内部的边，以及从 @@M@@B@@ 连向每个固定外点的”星”）大小都至少为 @@M@@m@@，故个体影响 @@M@@\le I(f_y)/m@@，低阶引理对每个限制都适用。因估计对 @@M@@I@@ 线性，可先对外部赋值平均（限制恒等式为精确恒等式），再对 @@M@@B@@ 平均，得块估计，右端含因子 @@M@@2m/n@@。
第四步捕捉（capture）：把傅里叶指标 @@M@@S@@ 看成 @@M@@s@@ 条边的图。只要 @@M@@s\le k^2/2@@，它就有非孤立点 @@M@@u@@，度数至多 @@M@@\sqrt{2s}\le k@@；以不小于 @@M@@m/(2n)@@ 的概率，@@M@@B@@ 恰好只在 @@M@@u@@ 接触该图，存活的自由支撑边恰为过 @@M@@u@@ 的 @@M@@1@@ 到 @@M@@k@@ 条（不必恰为一条）。与块估计相除、@@M@@m/n@@ 相消，就把”条件度不超过 @@M@@k@@“升级为”原始度不超过 @@M@@k^2/2@@“的控制——度数的平方化正是 @@M@@(\log n)^2@@ 中平方的来源。更高阶的尾部由 Dirichlet 恒等式压成 @@M@@2\sigma^2I_p(f)/k^2@@；因 @@M@@k@@ 正比于 @@M@@\sigma\log m@@，@@M@@\sigma^2@@ 精确相消，界对一切 @@M@@p@@ 一致，小 @@M@@n@@ 平凡处理。最后由 Russo–Margulis 公式 @@M@@\mu'(p)=I_p(f)@@ 得微分不等式 @@M@@\mu'\ge(\log n)^2\mu(1-\mu)/C_0@@，积分对数几率即得定理 1（取 @@M@@4C_0=2^{19}@@）。
本文主结果暂无形式化证明，请以社区核验为准。姊妹篇《A uniform influence bound for hypergraph properties》原样复用本文的傅里叶估计与块限制论证，并推广到 @@M@@r\ge3@@ 的一致超图（指数变为 @@M@@r/(r-1)@@），两篇共用同一方法骨架、互为印证；族内另有两篇处理阈值位置的比较（积分与分数覆盖的比较、图包含阈值与期望子图计数的比较），本文证明不依赖它们。按 OpenAI 官方声明，未经形式化的结果可能有问题，采信前请留意同行核验进展。
问 1：证明中最关键的一步是什么？
（答：度数平方化的捕捉论证。把傅里叶指标 S 看成 s 条边的图：只要 s ≤ k²/2，就有度至多 k 的非孤立顶点；随机块 B 以约 m/(2n) 的概率恰好只在该点触碰支撑，存活的自由支撑边是过该点的 1 到 k 条。与块估计相除、m/n 因子相消，”条件度 ≤ k”升级为”原始度 ≤ k²/2”——(log n)² 中的平方正是这样来的，取 k 正比于 √(p(1−p))·log n 后偏倚因子在尾部估计中精确相消。）
问 2：Friedgut–Kalai 原定理只差一个 log n，卡在哪里？
（答：FK96 只用到边坐标上置换作用的传递性，那对一切传递群都成立；顶点置换群的真正富余在块结构——块内置换在任意外部边赋值下仍是对称，且自由边轨道（块内边与连向每个外点的星）大小都 ≥ m，个体影响力才被压到 I/m。这一信息传递群没有。）
问 3：(log n)² 还能改进吗？
（答：不能。Friedgut–Kalai 已指出：含大小正比于 log n 的团这一性质，其过渡宽度本身达到 (log n)^{−2} 阶；故固定 ε 时阶已最优，能改进的只有常数（文中 2^19 只是方便的显式选择）。）
问 4：与 Bourgain–Kalai、KKLMS 相比真正新意是什么？
（答：BK97 到达 (log n)^{−2+η}，任意固定 η>0 都差一口气；KKLMS 在 p=1/2 处的影响力下界带 (log log n)² 损失，且阈值宽度需要整个过渡区间上的一致控制。本文的定理 2 同时做到：无 η、无重对数、一致于一切 p、还不要求单调。）
问 5：这类 AI 生成证明最可能出什么错？
（答：偏倚测度下的超收缩性。噪声算子在 ρ=σ/4 处的 2→4 范数不等式 ‖T_ρ g‖₄ ≤ ‖g‖₂ 由文中自足证明——无偏经典结论搬到偏倚情形时的常数换算是历史雷区。其次是平均化的次序：块估计对影响力是线性的，才能先对外部赋值平均（限制恒等式精确成立）再对 B 平均；一旦顺序不当或有非线性残留，账就不平。姊妹超图篇原样复用此处骨架，两篇同源同险。）
问 6：它依赖同族其他结果吗？谁会用到它？
（答：不依赖——引言明确说明两篇阈值位置比较的姊妹篇（积分/分数覆盖比较、包含阈值与期望子图计数比较）与本文互不使用。下游是大规模随机网络的状态切换分析、随机图性质的阈值定位，以及由姊妹篇承接的超图推广。）
总评
（正面解决悬置三十年的 Friedgut–Kalai 尖阈值猜想、阶达最优、引擎不等式还更强（一致于 p、免单调），分量极重；最大风险是与超图姊妹篇共用的偏倚超收缩长链未经形式化，一旦该处有失，两篇俱损。）