2025-11-14T23:49:11.616268

On Pauling's residual entropy estimate for regular graphs with growing degree

Hasheminezhad, Isaev, McKay et al.
In 1935, Pauling proposed an estimate for the number of Eulerian orientations of a graph in the context of the theoretical behaviour of water ice. The logarithm of the number of Eulerian orientations, normalised by the number of vertices, is called the residual entropy. In an earlier paper, we conjectured that the residual entropy of a sequence of regular graphs of increasing degree was asymptotically equal to Pauling's estimate. Here we prove the conjecture under constraints on the number of short circuits. These constraints hold under weak eigenvalue conditions and apply to sequences of increasing girth and repeated Cartesian products such as hypercubes.
academic

On Pauling's residual entropy estimate for regular graphs with growing degree

基本信息

  • 论文ID: 2509.20671
  • 标题: On Pauling's residual entropy estimate for regular graphs with growing degree
  • 作者: Mahdieh Hasheminezhad (Yazd University), Mikhail Isaev (UNSW Sydney), Brendan D. McKay (Australian National University), Rui-Ray Zhang
  • 分类: math.CO (组合数学)
  • 发表时间: 2025年11月5日 (arXiv v2)
  • 论文链接: https://arxiv.org/abs/2509.20671

摘要

1935年，Pauling在研究水冰的理论行为时提出了一个关于图的欧拉定向数量的估计。欧拉定向数量的对数除以顶点数称为残余熵。在早期论文中，作者猜想度数递增的正则图序列的残余熵渐近等于Pauling估计。本文在短回路数量约束下证明了该猜想。这些约束在弱特征值条件下成立，并适用于围长递增的图序列和重复笛卡尔积（如超立方体）。

研究背景与动机

1. 研究问题

本文研究图的欧拉定向（Eulerian orientations）计数问题。对于一个d-正则图G（d为偶数），欧拉定向是指边的定向使得每个顶点的入度等于出度。定义残余熵为： ρ(G):=1nlog⁡EO(G)\rho(G) := \frac{1}{n}\log EO(G) 其中EO(G)是欧拉定向的数量，n是顶点数。

2. 问题重要性

  • 物理背景：残余熵在统计物理的冰模型（ice-type models）中具有重要意义，与水冰晶体的微观状态数相关
  • 数学意义：对于特定晶格（方格晶格、三角晶格、六边形冰单层），残余熵的精确值已知，但一般图的渐近行为仍是开放问题
  • 理论价值：连接组合数学、统计物理和概率论

3. Pauling估计

Pauling在1935年提出启发式估计：假设每条边独立随机定向，顶点i入度等于出度的概率为2−d(dd/2)2^{-d}\binom{d}{d/2}。如果n个顶点的事件独立，则得到： ρ^(G)=log⁡(dd/2)−d2log⁡2\hat{\rho}(G) = \log\binom{d}{d/2} - \frac{d}{2}\log 2

Lieb和Wu证明了对任何图：ρ(G)≥ρ^(G)\rho(G) \geq \hat{\rho}(G)

4. 现有研究局限

  • 之前的结果（Isaev, McKay, Zhang 5）仅对具有良好扩张性质且d≥log⁡8nd \geq \log^8 n的图成立
  • 随机图的结果（6）依赖高概率性质
  • Las Vergnas 7的结果要求围长增长快于log⁡d\log d

5. 研究动机

Conjecture 1.1：对于d-正则图序列G(n)，若偶数d=d(n)→∞d = d(n) \to \infty，则ρ(G)=ρ^(G)+o(1)\rho(G) = \hat{\rho}(G) + o(1)

本文目标是在更弱的条件下证明该猜想。

核心贡献

  1. 主要定理（Theorem 2.1）：在短闭迹数量约束下证明Conjecture 1.1，条件为：
    • 存在ℓmax=ω(log⁡d)\ell_{max} = \omega(\log d)和常数C > 0
    • 对所有3≤ℓ≤ℓmax3 \leq \ell \leq \ell_{max}：cℓ(G)≤Ce−(l+1)dℓ−1nc_\ell(G) \leq Ce^{-(l+1)}d^{\ell-1}n
  2. 特征值条件推论（Corollary 2.2）：若至多nd−ω(1)nd^{-\omega(1)}个特征值在[−d1−δ,d1−δ][-d^{1-\delta}, d^{1-\delta}]外（某常数δ > 0），则猜想成立
  3. 围长条件推论（Corollary 2.3）：对围长g→∞g \to \infty的d-正则图序列，猜想成立（不要求d→∞d \to \infty）
  4. 笛卡尔积推论（Corollary 2.4）：对笛卡尔积Gt=H1(t)□⋯□Ht(t)G_t = H_1^{(t)} \square \cdots \square H_t^{(t)}，在度数平方和满足∑i=1t(hi(t))2=O(dt2−δ)\sum_{i=1}^t (h_i^{(t)})^2 = O(d_t^{2-\delta})时猜想成立，特别适用于超立方体QdQ_d
  5. 技术创新：将问题转化为随机欧拉划分诱导的闭迹数量的矩生成函数分析

方法详解

任务定义

给定d-正则图G（d偶数），计算残余熵ρ(G)=1nlog⁡EO(G)\rho(G) = \frac{1}{n}\log EO(G)，并证明其渐近等于Pauling估计ρ^(G)\hat{\rho}(G)。

核心方法框架

1. 欧拉划分表示

定义：欧拉划分P是将图的边划分为若干闭迹。每个顶点的边配对（pairing）唯一确定一个欧拉划分。

关键公式： ρ(G)=ρ^(G)+1nlog⁡E2∣T(P)∣\rho(G) = \hat{\rho}(G) + \frac{1}{n}\log \mathbb{E} 2^{|T(P)|} 其中P是均匀随机欧拉划分，T(P)是P诱导的闭迹集合。

等价性：猜想等价于证明E2∣T(P)∣=eo(n)\mathbb{E} 2^{|T(P)|} = e^{o(n)}

2. 闭迹分解策略

定义k=⌊min⁡{ℓmax/2,log⁡2d}⌋k = \lfloor\min\{\ell_{max}/2, \log^2 d\}\rfloor，将闭迹分为：

  • 长闭迹 Lk(P)L_k(P)：包含超过k个不同顶点的闭迹数
  • 短闭迹 Sk(P)S_k(P)：包含至多k个不同顶点的闭迹数

使用Hölder不等式： E2∣T(P)∣=E2Lk(P)+Sk(P)≤(E272Lk(P))2/7(E275Sk(P))5/7\mathbb{E} 2^{|T(P)|} = \mathbb{E} 2^{L_k(P)+S_k(P)} \leq \left(\mathbb{E} 2^{\frac{7}{2}L_k(P)}\right)^{2/7}\left(\mathbb{E} 2^{\frac{7}{5}S_k(P)}\right)^{5/7}

技术组件

3. 长闭迹控制（Lemma 3.4）

关键引理（Lemma 3.1）：对偶数m和λ ≥ 0， EeλX(m)≤(Bm)(eλ−1)/2\mathbb{E} e^{\lambda X(m)} \leq (Bm)^{(e^\lambda-1)/2} 其中X(m)X(m)是参数为1/(2j−1)1/(2j-1) (j=1,...,m/2)的独立伯努利随机变量之和。

配对独立性（Lemma 3.2）：在随机配对中，通过顶点v的不同闭迹数服从分布X(m)，且与其他顶点的配对独立。

矩生成函数界（Lemma 3.3）：对顶点子集U， EeλY(U)=dO(∣U∣)\mathbb{E} e^{\lambda Y(U)} = d^{O(|U|)}

最终界：选择∣U∣=⌊n/k⌋|U| = \lfloor n/k\rfloor的随机子集，利用Lk≤2Y(U)L_k \leq 2Y(U)的概率至少1/2，得到： EeλLk≤(edk)O(n/k)=eo(n)\mathbb{E} e^{\lambda L_k} \leq (edk)^{O(n/k)} = e^{o(n)}

4. 短闭迹控制（Lemma 4.5）

使用switching方法（Theorem 4.1）——这是一个强大的组合计数工具。

Switching定义：给定欧拉划分P和闭迹T，T-switching在T经过的每个顶点修改配对：

  • 顶点v被T访问t次，对应边对(e1,e1′),…,(et,et′)(e_1,e_1'),\ldots,(e_t,e_t')
  • 选择t个额外边对(et+1,et+1′),…,(e2t,e2t′)(e_{t+1},e_{t+1}'),\ldots,(e_{2t},e_{2t}')
  • 替换为新配对{e1,et+1},…,{et,e2t}\{e_1,e_{t+1}\},\ldots,\{e_t,e_{2t}\}和{e1′,et+1′},…,{et′,e2t′}\{e_1',e_{t+1}'\},\ldots,\{e_t',e_{2t}'\}

Switching图：构造有向多重图Γ：

  • 顶点：m=(m3,…,mL)\mathbf{m} = (m_3,\ldots,m_L)，表示恰好有mℓm_\ell条长度为ℓ的短闭迹的欧拉划分类
  • 边：颜色为ℓ的有向边(m,m′)(\mathbf{m},\mathbf{m}')表示存在ℓ-switching从C(m)到C(m')

关键估计（Lemma 4.3）：

  • 从P ∈ C(m)出发的ℓ-switching数：≥∥m∥1(d−2L)ℓ/L\geq \|\mathbf{m}\|_1(d-2L)^\ell/L
  • 到达P' ∈ C(m')的ℓ-switching数：≤ck,ℓ\leq c_{k,\ell}

权重函数： α^(e)≤2ck,ℓL2dℓm\hat{\alpha}(e) \leq \frac{2c_{k,\ell}L^2}{d^\ell m}

应用Theorem 4.1：定义 M0:=2CnL2/d,Y=⋃m>MCm,Z=⋃m≤M0CmM_0 := 2CnL^2/d, \quad Y = \bigcup_{m>M} C_m, \quad Z = \bigcup_{m\leq M_0} C_m

由于α^(e)<1/2\hat{\alpha}(e) < 1/2对所有∥m∥1>M0\|\mathbf{m}\|_1 > M_0的边，得到： ∣Y∣≤2e−M+M0∣Z∣|Y| \leq 2e^{-M+M_0}|Z|

尾概率界： P(Sk(P)>M)≤2e−M+M0\mathbb{P}(S_k(P) > M) \leq 2e^{-M+M_0}

矩界：通过积分表示， EeλSk(P)≤eλM0+2eλM01−λ=eo(n)\mathbb{E} e^{\lambda S_k(P)} \leq e^{\lambda M_0} + \frac{2e^{\lambda M_0}}{1-\lambda} = e^{o(n)} 其中λ=75log⁡2≈0.97<1\lambda = \frac{7}{5}\log 2 \approx 0.97 < 1。

技术创新点

  1. 分解策略的精妙性：通过k值的选择平衡长短闭迹的贡献，使用Hölder不等式的指数选择（7/2和7/5）是精心设计的
  2. Switching方法的创新应用：
    • 将欧拉划分的计数问题转化为有向图上的流问题
    • 利用短闭迹数量假设控制switching权重
    • 通过Theorem 4.1得到尾概率的指数衰减
  3. 条件的弱化：
    • 从d≥log⁡8nd \geq \log^8 n弱化到d→∞d \to \infty
    • 从强扩张性弱化到短闭迹数量约束
    • 特征值条件只需nd−ω(1)nd^{-\omega(1)}个outliers
  4. 统一框架：同时处理围长增长、特征值约束、笛卡尔积等多种情形

实验设置

理论证明性质

本文是纯理论论文，不包含数值实验或计算实验。所有结果都是严格的数学证明。

应用实例

论文通过推论验证了猜想在以下图类上成立：

  1. 围长增长图（Corollary 2.3）
  2. 谱约束图（Corollary 2.2）
  3. 超立方体 QdQ_d（d偶数）
  4. 循环笛卡尔积：局部收敛到高维方格晶格
  5. 随机正则图（引用6的结果）

实验结果

主要结果

Theorem 2.1的条件验证：

  1. 围长g → ∞的图：
    • 长度ℓ < g的闭迹数为0，自动满足条件
    • 即使d = O(1)也成立
  2. 特征值约束图：
    • 闭走的数量≤∑iλiℓ\leq \sum_i \lambda_i^\ell
    • 若至多nd−f(n)nd^{-f(n)}个特征值在[−d1−δ,d1−δ][-d^{1-\delta}, d^{1-\delta}]外
    • 取ℓmax=12f(n)log⁡d\ell_{max} = \frac{1}{2}f(n)\log d，条件满足
  3. 笛卡尔积：
    • 利用Hoeffding不等式控制特征值分布
    • 对∑i(hi(t))2=O(dt2−δ)\sum_i (h_i^{(t)})^2 = O(d_t^{2-\delta})，条件满足
    • 超立方体：hi=1h_i = 1，满足∑hi2=t=o(dt2)\sum h_i^2 = t = o(d_t^2)

技术结果

长闭迹界（Lemma 3.4）： EeλLk(P)=eo(n),∀λ≥0, k≫log⁡d\mathbb{E} e^{\lambda L_k(P)} = e^{o(n)}, \quad \forall \lambda \geq 0, \, k \gg \log d

短闭迹界（Lemma 4.5）： E275Sk(P)=eo(n)\mathbb{E} 2^{\frac{7}{5}S_k(P)} = e^{o(n)}

关键不等式链

\mathbb{E} 2^{|T(P)|} &\leq \left(\mathbb{E} 2^{\frac{7}{2}L_k(P)}\right)^{2/7}\left(\mathbb{E} 2^{\frac{7}{5}S_k(P)}\right)^{5/7}\\ &= (e^{o(n)})^{2/7} \cdot (e^{o(n)})^{5/7}\\ &= e^{o(n)} \end{align}$$ 因此$\rho(G) = \hat{\rho}(G) + o(1)$。 ## 相关工作 ### 1. 历史背景 - **Pauling (1935)**：提出残余熵的启发式估计，用于解释水冰的零点熵 - **Lieb & Wu (1972)**：证明$\rho(G) \geq \hat{\rho}(G)$的下界 ### 2. 精确结果 - **Lieb (1967)**：方格晶格的精确值 - **Baxter (1969)**：三角晶格的精确值 - **Li et al. (2023)**：六边形冰单层的精确值 ### 3. 渐近结果 - **Las Vergnas (1990)**：围长增长快于$\log d$时猜想成立 - **Isaev, McKay, Zhang (2025, [5])**：扩张图且$d \geq \log^8 n$时猜想成立 - **Isaev, McKay, Zhang (2025, [6])**：随机图高概率成立 ### 4. 方法论 - **Switching方法**：Greenhill & McKay (2013), Hasheminezhad & McKay (2010) - **累积量展开**：[5]中的方法 - **概率配对**：Lugo (2009)关于随机对合的循环结构 ### 5. 本文相对优势 - **条件最弱**：只需短闭迹数量约束 - **应用最广**：涵盖围长、特征值、笛卡尔积等多种情形 - **技术统一**：单一框架处理多种图类 ## 结论与讨论 ### 主要结论 1. **定理层面**：在短闭迹数量约束$c_\ell(G) \leq Ce^{-(l+1)}d^{\ell-1}n$（$3 \leq \ell \leq \ell_{max} = \omega(\log d)$）下，Pauling猜想成立 2. **推论层面**： - 围长增长的图序列满足猜想 - 谱约束图满足猜想 - 笛卡尔积（包括超立方体）满足猜想 3. **方法论**：Switching方法结合矩生成函数分析是处理此类问题的有效工具 ### 局限性 1. **条件依赖**： - 仍需$d \to \infty$（除围长情形外） - 短闭迹数量约束虽弱但非平凡 - $\ell_{max} = \omega(\log d)$的要求 2. **技术限制**： - Hölder不等式的指数选择（7/2, 7/5）似乎是技术性的，可能不是最优 - k值的选择依赖于$\ell_{max}$和$\log^2 d$的平衡 3. **应用范围**： - 不适用于度数有界的图序列（$d = O(1)$时仅围长情形成立） - 对不规则图的推广不明显 4. **计算复杂性**： - 结果是渐近的，不提供有限n的误差界 - 没有算法层面的贡献 ### 未来方向 1. **条件放松**： - 能否完全去除短闭迹约束？ - 能否处理$d = O(1)$的一般情形？ 2. **误差项**： - o(1)项的精确阶是多少？ - 能否得到$\rho(G) = \hat{\rho}(G) + O(1/d)$的精细估计？ 3. **不规则图**： - 推广到度序列不完全均匀的图 - 处理二部图的情形 4. **算法应用**： - 能否设计近似计数算法？ - MCMC采样的混合时间分析 5. **物理联系**： - 与相变理论的更深联系 - 其他晶格模型的应用 ## 深度评价 ### 优点 1. **理论深度**： - 证明技术高超，巧妙结合多个领域的工具 - Switching方法的应用展现了组合优化的威力 - 矩生成函数分析严谨细致 2. **结果广度**： - 统一处理多种图类（围长、特征值、笛卡尔积） - 推论覆盖重要应用（超立方体、高维晶格） - 连接组合数学和统计物理 3. **技术创新**： - 长短闭迹的分解策略新颖 - Switching图的构造精巧 - Hölder不等式的使用恰到好处 4. **写作质量**： - 结构清晰，逻辑严密 - 技术细节完整，易于验证 - 背景介绍充分，动机明确 ### 不足 1. **条件非最优**： - $\ell_{max} = \omega(\log d)$的要求可能可以减弱 - Hölder指数的选择（7/2, 7/5）似乎有优化空间 2. **应用局限**： - 对度数有界图（如固定d）的情形覆盖不足 - 不规则图的推广不明显 3. **计算缺失**： - 没有数值验证或具体例子的计算 - 对有限图的误差界未知 4. **物理解释**： - 虽有物理背景，但与相变、临界现象的联系讨论不足 - 残余熵的物理意义可以更深入探讨 ### 影响力 1. **学术贡献**： - 解决了组合数学中的重要猜想（在约束条件下） - 为后续研究提供了强有力的工具和框架 - 可能引发对Switching方法的进一步发展 2. **实用价值**： - 对统计物理中的冰模型提供理论支持 - 对网络科学中的定向问题有启发 - 可能应用于近似计数算法设计 3. **可复现性**： - 证明完整，可以逐步验证 - 技术工具（Theorem 4.1）已在文献中建立 - 推论的验证相对直接 4. **后续研究**： - 激励对条件的进一步弱化 - 推动对不规则图的研究 - 可能引发算法和计算复杂性的工作 ### 适用场景 1. **理论研究**： - 组合数学中的计数问题 - 图论中的欧拉性质研究 - 概率组合学 2. **物理应用**： - 冰模型的统计力学 - 晶格系统的配分函数 - 相变理论 3. **网络科学**： - 大规模网络的定向问题 - 流网络的平衡性分析 - 社交网络的互惠性研究 4. **算法设计**： - 近似计数算法的理论基础 - MCMC方法的混合时间分析 - 随机算法的性能保证 ## 参考文献 ### 关键引用 1. **Pauling (1935)**: 原始猜想的提出，冰晶体的残余熵 2. **Lieb & Wu (1972)**: 下界证明和铁电模型的系统研究 3. **Greenhill & McKay (2013)**: Switching方法的系统化 4. **Isaev, McKay, Zhang (2025, [5])**: 累积量展开方法，$d \geq \log^8 n$的结果 5. **Isaev, McKay, Zhang (2025, [6])**: 随机图的结果，与生成树熵的关联 6. **Las Vergnas (1990)**: 围长条件下的上界 7. **Lugo (2009)**: 随机对合的循环结构，配对独立性 ### 方法论文献 - **Hoeffding (1963)**: 概率不等式 - **McKay (1981)**: 正则图的期望特征值分布 - **Merris (1998)**: Laplacian图特征向量，笛卡尔积的谱性质 --- **总体评价**：这是一篇高质量的理论论文，在弱化的条件下部分解决了组合数学和统计物理中的重要猜想。证明技术精湛，结果覆盖面广，对领域有重要贡献。虽然条件仍非最优，但为完全解决猜想铺平了道路。论文展示了Switching方法的强大威力，值得组合数学研究者深入学习。