Pauling の正則グラフの残留エントロピー推定について（次数増加の場合）

基本情報

• 論文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 は偶数）に対して、オイラー向きとは、各頂点の入次数が出次数に等しくなるような辺の向き付けを意味する。残留エントロピーを以下のように定義する： $\rho(G) := \frac{1}{n}\log EO(G)$ ここで EO(G) はオイラー向きの数、n は頂点数である。

2. 問題の重要性

• 物理的背景：残留エントロピーは統計物理の氷モデル（ice-type models）において重要な意義を持ち、水氷結晶の微視的状態数と関連している
• 数学的意義：特定の格子（正方格子、三角格子、六角形氷単層）に対しては残留エントロピーの正確な値が既知であるが、一般的なグラフの漸近的挙動は依然として未解決問題である
• 理論的価値：組合数学、統計物理、確率論を結びつける

3. Pauling 推定

Pauling は 1935 年に、各辺を独立に確率的に向き付けると仮定した場合の启発的推定を提案した。頂点 i の入次数が出次数に等しい確率は $2^{-d}\binom{d}{d/2}$ である。n 個の頂点のイベントが独立であると仮定すると、以下を得る： $\hat{\rho}(G) = \log\binom{d}{d/2} - \frac{d}{2}\log 2$

Lieb と Wu は任意のグラフに対して $\rho(G) \geq \hat{\rho}(G)$ を証明した。

4. 既存研究の限界

• 先行結果（Isaev, McKay, Zhang 5）は、良好な拡張性質を持ち $d \geq \log^8 n$ を満たすグラフにのみ適用可能であった
• ランダムグラフの結果（6）は高確率性質に依存している
• Las Vergnas 7 の結果は周囲長が $\log d$ より速く増加することを要求している

5. 研究の動機

予想 1.1：d-正則グラフ列 G(n) に対して、偶数 $d = d(n) \to \infty$ ならば、$\rho(G) = \hat{\rho}(G) + o(1)$ である。

本論文の目標は、より弱い条件下でこの予想を証明することである。

核心的貢献

1. 主定理（定理 2.1）：短閉路数の制約条件下で予想 1.1 を証明する。条件は以下の通り：
   • $\ell_{max} = \omega(\log d)$ と定数 C > 0 が存在する
   • すべての $3 \leq \ell \leq \ell_{max}$ に対して：$c_\ell(G) \leq Ce^{-(l+1)}d^{\ell-1}n$
2. 固有値条件系（系 2.2）：最大 $nd^{-\omega(1)}$ 個の固有値が $[-d^{1-\delta}, d^{1-\delta}]$ の外にある場合（ある定数 δ > 0）、予想が成立する
3. 周囲長条件系（系 2.3）：周囲長 $g \to \infty$ の d-正則グラフ列に対して、予想が成立する（$d \to \infty$ を要求しない）
4. デカルト積系（系 2.4）：デカルト積 $G_t = H_1^{(t)} \square \cdots \square H_t^{(t)}$ に対して、次数の二乗和が $\sum_{i=1}^t (h_i^{(t)})^2 = O(d_t^{2-\delta})$ を満たす場合、特に超立方体 $Q_d$ に適用可能である
5. 技術的革新：問題をランダムオイラー分割が誘導する閉路数の積率生成関数分析に変換する

方法の詳細説明

問題設定

d-正則グラフ G（d は偶数）が与えられたとき、残留エントロピー $\rho(G) = \frac{1}{n}\log EO(G)$ を計算し、その漸近的な値が Pauling 推定 $\hat{\rho}(G)$ に等しいことを証明する。

核心的方法論の枠組み

1. オイラー分割表現

定義：オイラー分割 P は、グラフの辺を複数の閉路に分割したものである。各頂点の辺ペアリング（pairing）は一意にオイラー分割を決定する。

重要公式： $\rho(G) = \hat{\rho}(G) + \frac{1}{n}\log \mathbb{E} 2^{|T(P)|}$ ここで P は均一ランダムオイラー分割、T(P) は P が誘導する閉路集合である。

同値性：予想は $\mathbb{E} 2^{|T(P)|} = e^{o(n)}$ を証明することと同値である。

2. 閉路分解戦略

$k = \lfloor\min\{\ell_{max}/2, \log^2 d\}\rfloor$ と定義し、閉路を以下のように分類する：

• 長閉路 $L_k(P)$：k 個を超える異なる頂点を含む閉路の数
• 短閉路 $S_k(P)$：最大 k 個の異なる頂点を含む閉路の数

Hölder 不等式を使用する： $\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. 長閉路の制御（補題 3.4）

重要補題（補題 3.1）：偶数 m と λ ≥ 0 に対して、 $\mathbb{E} e^{\lambda X(m)} \leq (Bm)^{(e^\lambda-1)/2}$ ここで $X(m)$ は $1/(2j-1)$（j=1,...,m/2）をパラメータとする独立ベルヌーイ確率変数の和である。

ペアリング独立性（補題 3.2）：ランダムペアリングにおいて、頂点 v を通過する異なる閉路の数は分布 X(m) に従い、他の頂点のペアリングと独立である。

積率生成関数の界（補題 3.3）：頂点部分集合 U に対して、 $\mathbb{E} e^{\lambda Y(U)} = d^{O(|U|)}$

最終的な界：$|U| = \lfloor n/k\rfloor$ のランダム部分集合を選択し、確率少なくとも 1/2 で $L_k \leq 2Y(U)$ を利用して、以下を得る： $\mathbb{E} e^{\lambda L_k} \leq (edk)^{O(n/k)} = e^{o(n)}$

4. 短閉路の制御（補題 4.5）

スイッチング方法（定理 4.1）を使用する。これは強力な組合数学的計数ツールである。

スイッチングの定義：オイラー分割 P と閉路 T が与えられたとき、T-スイッチングは T が通過する各頂点でペアリングを修正する：

• 頂点 v が T に t 回訪問され、対応する辺ペアが $(e_1,e_1'),\ldots,(e_t,e_t')$ である
• t 個の追加辺ペア $(e_{t+1},e_{t+1}'),\ldots,(e_{2t},e_{2t}')$ を選択する
• これらを新しいペアリング $\{e_1,e_{t+1}\},\ldots,\{e_t,e_{2t}\}$ と $\{e_1',e_{t+1}'\},\ldots,\{e_t',e_{2t}'\}$ に置き換える

スイッチンググラフ：有向多重グラフ Γ を構築する：

• 頂点：$\mathbf{m} = (m_3,\ldots,m_L)$、ちょうど $m_\ell$ 個の長さ ℓ の短閉路を持つオイラー分割クラスを表す
• 辺：色 ℓ の有向辺 $(\mathbf{m},\mathbf{m}')$ は、C(m) から C(m') へのℓ-スイッチングが存在することを表す

重要な推定（補題 4.3）：

• P ∈ C(m) から出発するℓ-スイッチング数：$\geq \|\mathbf{m}\|_1(d-2L)^\ell/L$
• P' ∈ C(m') に到達するℓ-スイッチング数：$\leq c_{k,\ell}$

重み関数： $\hat{\alpha}(e) \leq \frac{2c_{k,\ell}L^2}{d^\ell m}$

定理 4.1 の適用：以下を定義する $M_0 := 2CnL^2/d, \quad Y = \bigcup_{m>M} C_m, \quad Z = \bigcup_{m\leq M_0} C_m$

すべての $\|\mathbf{m}\|_1 > M_0$ の辺に対して $\hat{\alpha}(e) < 1/2$ であるため、以下を得る： $|Y| \leq 2e^{-M+M_0}|Z|$

尾確率の界： $\mathbb{P}(S_k(P) > M) \leq 2e^{-M+M_0}$

積率の界：積分表現を通じて、 $\mathbb{E} e^{\lambda S_k(P)} \leq e^{\lambda M_0} + \frac{2e^{\lambda M_0}}{1-\lambda} = e^{o(n)}$ ここで $\lambda = \frac{7}{5}\log 2 \approx 0.97 < 1$ である。

技術的革新点

1. 分解戦略の巧妙性：k 値の選択を通じて長短閉路の寄与のバランスを取り、Hölder 不等式の指数選択（7/2 と 7/5）は慎重に設計されている
2. スイッチング方法の革新的応用：
   • オイラー分割の計数問題を有向グラフ上のフロー問題に変換する
   • 短閉路数量仮説を利用してスイッチング重みを制御する
   • 定理 4.1 を通じて尾確率の指数減衰を得る
3. 条件の弱化：
   • $d \geq \log^8 n$ から $d \to \infty$ に弱化
   • 強い拡張性から短閉路数量制約に弱化
   • 固有値条件は $nd^{-\omega(1)}$ 個の外れ値のみを必要とする
4. 統一的枠組み：周囲長増加、固有値制約、デカルト積など複数の状況を同時に処理する

実験設定

理論証明の性質

本論文は純粋な理論論文であり、数値実験や計算実験は含まれていない。すべての結果は厳密な数学的証明である。

応用例

論文は以下のグラフクラスで予想が成立することを系によって検証している：

1. 周囲長増加グラフ（系 2.3）
2. スペクトル制約グラフ（系 2.2）
3. 超立方体 $Q_d$（d は偶数）
4. 循環デカルト積：局所的に高次元正方格子に収束
5. ランダム正則グラフ（参考文献 6 の結果を引用）

実験結果

主要結果

定理 2.1 の条件検証：

1. 周囲長 g → ∞ のグラフ：
   • 長さ ℓ < g の閉路の数はゼロであり、自動的に条件を満たす
   • d = O(1) でも成立する
2. 固有値制約グラフ：
   • 閉歩の数 $\leq \sum_i \lambda_i^\ell$
   • 最大 $nd^{-f(n)}$ 個の固有値が $[-d^{1-\delta}, d^{1-\delta}]$ の外にある場合
   • $\ell_{max} = \frac{1}{2}f(n)\log d$ を取ると、条件が満たされる
3. デカルト積：
   • Hoeffding 不等式を利用して固有値分布を制御する
   • $\sum_i (h_i^{(t)})^2 = O(d_t^{2-\delta})$ に対して条件が満たされる
   • 超立方体：$h_i = 1$ であり、$\sum h_i^2 = t = o(d_t^2)$ を満たす

技術的結果

長閉路の界（補題 3.4）： $\mathbb{E} e^{\lambda L_k(P)} = e^{o(n)}, \quad \forall \lambda \geq 0, \, k \gg \log d$

短閉路の界（補題 4.5）： $\mathbb{E} 2^{\frac{7}{5}S_k(P)} = e^{o(n)}$

重要な不等式チェーン