对数凹Holant测度的无度依赖谱独立性
核心概要
本文在简单图上为对数凹Holant问题建立了不依赖最大度数的谱独立性上界,并由此得到单体-二聚体模型在活度λ下Glauber动力学的弛豫时间O_λ(m)、b-匹配在逸度λ>0下的O_{b,λ}(m),以及均匀b-匹配的O(bm),其中m为边数。
深度剖析
对满足插入几率有界(γ≤θ_uv(i,j)≤Θ)且顶点阈值b_v≤b的对数凹Holant测度,作者证明其谱独立性上界为O(1+Θ+(b-1)T²),该上界不随最大度Δ增长。 此前Chen与Gu在最大度为Δ的图上给出的界为2(P_max-1)≤2((1+r_max²λ_max)^Δ-1),随Δ指数增长;本文把对Δ的依赖替换为对局部参数γ、Θ、b的依赖。 定理4给出一般性陈述,证明通过边-顶点方差界(引理7)与顶点方差界(引理6)经Schur补结合完成,并在附录A给出基于方差最大化的替代证明。
对单体-二聚体模型,在任意有限简单图上、任意固定活度λ>0下,测度为O((1+λ)²)-谱独立,且Glauber动力学满足t_rel=O_λ(m)、t_mix(ε)=O_λ(m(n log n+log(1/ε)))。 该界在每次可行钉扎后成立且与最大度无关,回应了Chen、Liu与Vigoda提出的超越通过控制总影响所得界的问题;此前在无限Δ-正则树上总影响为Θ_λ(√Δ)。 由定理4取b=1、γ=Θ=λ直接得到,混合时间结论见推论5(i),其证明在附录B中通过场动力学比较(定理10)与最小正构型概率估计完成。
对容量0≤b_v≤b、逸度λ>0的b-匹配,测度为C(1+λ)[1+λ+(b-1)max{1,λ^{2b}}]-谱独立,Glauber动力学满足t_rel=O_{b,λ}(m);均匀b-匹配(λ=1)改进为Cb-谱独立与t_rel=O(bm)。 此前均匀b-匹配的谱独立界为O_b(Δ^b),混合时间为O_Δ(n log n);本文把对Δ的依赖移除,并把弛豫时间写成关于边数m的线性形式。 谱独立界由定理4代入γ=Θ=λ得到;弛豫时间与混合时间由推论5(ii)给出,附录B结合定理10、定理11及μ_min的两种计数上界(2^m与(n+1)^{bn})完成推导。
证明的核心技术是把边指示变量的协方差用对角矩阵控制:先用递归耦合得到与最大度无关的顶点占据度方差界,再构造仅依赖端点度的调和代理量K_e=φ_e(D_u,D_v)使E[K_e|X_{-e}]=E[X_e|X_{-e}],从而把边方差归约为对角项加顶点加权和。 递归耦合中交替不一致路径在内部顶点处对占据度的贡献相互抵消,这一抵消给出度耦合独立性,从而绕开了总影响对最大度的固有依赖。 引理6、引理7给出两个方差界,定理14给出占据度的块动力学谱隙下界1-2r,代理量的构造见定义17及其后向递推,匹配情形的显式常数C_1=2+36λ、C_2=6在4.2节给出。
启示与展望
该结果面向有限简单图上的对数凹Holant测度,要求签名满足对数凹、无内部零且f_v(0)>0,并要求插入几率落在[γ,Θ]区间、顶点阈值b_v≤b;在此设定下,谱独立性与弛豫时间界对每个固定活度λ均与最大度无关。均匀b-匹配的界可通过补映射迁移到均匀b-边覆盖,其中B=max{1,max_v(d_v-b_v)}。这为在无界度图上分析单体-二聚体、b-匹配与b-边覆盖的Glauber动力学提供了可直接引用的复杂度基准。
本文为全文阅读,但公式在文本中经过排版转换,部分不等式的上下标与常数(如C_1、C_2、A_⋆的具体取值)需对照原排版确认。作者在1.3节提到Chihao Zhang与Zihan Zhang在并行独立工作中也对无界度图上的单体-二聚体模型建立了仅依赖活度的常数谱独立性界,两条路线的常数与适用范围是否一致值得后续对照。此外,1.4节披露使用AI工具(含GPT-5.6 Sol)协助形成主要证明思路与编辑手稿,作者声明对数学内容与最终表述负责;读者若关心证明细节,可结合附录中的两条独立证明路径交叉核对。
