与えられた周囲長の新しい小正則グラフ：ケージ問題とその先へ

基本情報

• 論文ID: 2511.07247
• タイトル: New small regular graphs of given girth: the cage problem and beyond
• 著者: Geoffrey Exoo, Jan Goedgebeur, Jorik Jooken, Louis Stubbe, Tibo Van den Eede
• 分類: math.CO（組合数学）、cs.DM（離散数学）
• 発表日: 2025年11月11日
• 論文リンク: https://arxiv.org/abs/2511.07247

概要

ケージ問題は、最小頂点数を持つ$(k,g)$-グラフ、すなわち$k$-正則グラフで周囲長（girth）が$g$であるグラフを探索することに関する。中核的な目標は、$n(k,g)$（このようなグラフの最小位数）を決定し、対応する極値グラフを特定することである。本論文は計算的観点からケージ問題およびその複数の変体を研究し、4つの相補的なグラフ生成アルゴリズムを開発した：リフト（lifts）に基づく完全列挙生成、禁忌探索ヒューリスティック、登山ヒューリスティック、および切除技術である。これらの方法を利用して、古典的ケージ問題の11のケースで新しい上界を確立した：$n(3,16) \leq 936$、$n(3,17) \leq 2048$、$n(4,9) \leq 270$、$n(4,10) \leq 320$、$n(4,11) \leq 713$、$n(5,9) \leq 1116$、$n(6,11) \leq 7783$、$n(8,7) \leq 774$、$n(10,7) \leq 1608$、$n(12,7) \leq 2890$、$n(14,7) \leq 4716$。これらの結果は22年間変わらなかった複数の最良既知界を改善し、特に$n(4,10)$を長年の384から320に低下させたことは実質的な改善である。

研究背景と動機

問題定義

1. 中核的問題：ケージ問題は$(k,g)$-ケージ（cage）を探索する。これは最小頂点数$n(k,g)$を持つ$k$-正則グラフで周囲長が$g$であるグラフである。周囲長はグラフ内の最短サイクルの長さである。
2. 問題の重要性：
   • 理論的意義：ケージは極値グラフ理論の中心的研究対象であり、Moore界などの古典的理論と密接に関連している
   • 実用的応用：疎で高度に対称な構造は、通信ネットワーク設計、誤り訂正符号、暗号学などの分野で応用価値を持つ
   • ネットワーク設計：効率的で均一な情報伝播をサポートし、中心ノードの過負荷を回避し、障害に対してロバストなトポロジー構造を提供する
3. 既存方法の限界：
   • ほとんどのパラメータペア$(k,g)$に対して、正確な値$n(k,g)$は未知である
   • 既存の界は多年にわたって改善されていない（一部の界は22年間保持されている）
   • Moore グラフは$g \in \{3,4,5,6,8,12\}$の場合にのみ存在する可能性がある
   • 計算複雑度は$k$と$g$の増加に伴い急速に増加する
4. 研究動機：
   • 現代の計算能力と最適化アルゴリズムを利用して、長期間変わらない界を改善する
   • ケージ問題およびその変体を処理するための体系的な計算方法を開発する
   • 具体的なグラフインスタンスの構成を通じて理論研究に証拠を提供する（例えば、偶周囲長ケージの二部性予想）

中核的貢献

1. アルゴリズムフレームワーク：4つの相補的なグラフ生成アルゴリズムを開発した
   • 電圧グラフリフトに基づくバックトラッキングアルゴリズム（BTA）
   • 禁忌探索ヒューリスティック（TS）
   • 登山ヒューリスティック
   • 切除技術
2. 古典的ケージ問題の突破：11個の新しい上界を確立した。以下を含む：
   • $n(4,10) \leq 320$（384から大幅に低下）
   • $n(3,16) \leq 936$（960から改善）
   • $n(3,17) \leq 2048$（2176から改善）
   • $n(4,11)$と$n(6,11)$に対する初めての非自明な上界
3. 変体問題の進展：
   • 辺周囲長正則（egr）グラフ：21個の新しい界（2個の厳密な界）
   • 頂点周囲長正則（vgr）グラフ：29個の新しい界（7個の厳密な界）
   • $(k,g,g+1)$-グラフ：6個の新しい界
   • $(k,g)$-スペクトラム：34個の以前に未解決だった位数を決定
4. 計算資源と再現性：
   • 約5 CPU年の計算作業
   • すべてのコードとデータはGitHubで公開
   • 完全な検証と健全性チェックを提供

方法の詳細

タスク定義

入力：正則度$k$、周囲長$g$、オプションの追加制約（頂点/辺周囲長正則性など）

出力：条件を満たす最小位数グラフ、または改善された上界$n(k,g)$

制約：グラフは$k$-正則（各頂点の次数が$k$）で、周囲長が少なくとも$g$（最短サイクルの長さ$\geq g$）である必要がある

中核技術：電圧グラフリフト（Voltage Graph Lifts）

基本原理

基グラフ$G=(V,E)$、群$\Gamma$、電圧割り当て$\alpha: A \rightarrow \Gamma$（$A$は有向辺集合）が与えられたとき、リフトグラフ$G_\alpha$の頂点集合は： $V(G_\alpha) = \{u_s | u \in V, s \in \Gamma\}$

各弧$(u,v) \in A$と各$s \in \Gamma$に対して、弧$(u_s, v_{s \cdot \alpha(a)}) \in A(G_\alpha)$が存在する。

主要性質

1. 正則性の保持（観察1）：$G$が$k$-正則当且つつ$G_\alpha$が$k$-正則
2. 連結性の必要条件（観察2）：$G$が非連結ならば$G_\alpha$は非連結
3. 周囲長の計算（命題1）：$G_\alpha$の周囲長は$G$の有向グラフにおける最短閉路非反転パス（正味電圧が$0_\Gamma$）の長さに等しい
4. 生成木の簡略化（命題2）：生成木上のすべての電圧を$0_\Gamma$に設定しても、リフトグラフの同型類は変わらない

アルゴリズム1：バックトラッキングアルゴリズム（BTA）

構造化除外規則

構造に基づく除外（電圧割り当てに依存しない）：

1. 半辺制約：半辺に対応する弧は、位数2の群元素のみを割り当てることができる
2. 生成木の最適化：生成木$T$を選択し、その辺の電圧を$0_\Gamma$に設定
3. 環に基づく除外：非木辺に対して、電圧$a$を割り当てると長さ$(q+1)s$（ここで$a^s=0_\Gamma$）で目標周囲長より小さいサイクルが生成される場合、その電圧を除外

割り当てに基づく除外（部分的な電圧割り当てに依存）：

1. 規範性チェック（アルゴリズム1）：
   • 群自同構$\phi_\Gamma$と辺自同構$\phi_G$を利用
   • 辞書式順序で最小の代表元のみを保持
   • 部分割り当てが非規範的ならば、その完成すべてを除外可能
2. 増分周囲長検証（アルゴリズム2）：
   • 新しい割り当て辺を使用する閉路非反転パスのみをチェック
   • 増分性を利用して効率を向上

アルゴリズムフロー（アルゴリズム3）

BTA(G, Γ, g_min):
  1. 構造チェックを実行し、実行可能な電圧集合Nを決定
  2. 電圧を再帰的に割り当て：
     - 各有用な弧dに対して、N(d)内の各電圧を試行
     - 周囲長チェックと規範性チェックを適用
     - 通過した場合、次の弧を再帰的に処理
     - バックトラック時に状態を復元
  3. 完全な割り当て後、リフトグラフを構成しフィルタリング

アルゴリズム2：禁忌探索（TS）

動機

大規模インスタンスに対してBTAは計算コストが大きいため、TSは有望な電圧割り当てを探索的にサンプリングする。

主要コンポーネント

近傍定義：正確に1つの辺に対応する群元素を変更するすべての代替割り当て

コスト関数：

1. 周囲長ベース（$c_{girth}$）： $c_{girth} = \sum_{i=1}^m f(q_i, a_i), \quad f(q,a) = \begin{cases} \frac{1}{q \cdot \text{Ord}(a)} & \text{if } \text{Ord}(a) \neq 1 \\ C & \text{otherwise} \end{cases}$ ここで$C$は大きなペナルティ定数、$m$はサンプリングパス数
2. 正則性ベース（$c_{reg}$）： $c_{reg} = \min\left[\text{Var}(f_V), \text{Var}(f_D)\right]$ ここで$f_V$と$f_D$はそれぞれ頂点と弧が周囲長環に出現する頻度

禁忌リスト：最近の修正操作を保存し、即座の復帰を防止、長さは$3|\Gamma|$

摂動メカニズム：局所最適に陥った場合、ランダムな修正を適用して脱出

ハイパーパラメータ設定（表1）

• 辺/群自同構数の制限：200/2000
• BTA と TS の時間制限：各20秒/インスタンス
• 近傍最小周囲長：$g_{nbr} = g_{min} - 2$（周囲長問題）または$g_{nbr} = g_{min}$（正則性問題）

アルゴリズム3：登山ヒューリスティック

前述の方法との違い：基グラフと電圧割り当てを同時に探索

フロー：

1. $n$個の孤立頂点から開始
2. 各反復：
   • 追加可能なすべての弧ペアと電圧割り当て$t \in T(G)$を考慮
   • $|T(G_t)|$を最大化する修正を選択（貪欲戦略）
3. リフトグラフが記録を破るかチェック

アルゴリズム4：切除技術

基本的な考え方：既知の小$(k,g+1)$-グラフから頂点を削除し、辺を追加して$k$-正則グラフを完成させる

具体的な戦略：

1. 周囲長7、偶数次$8 \leq k \leq 14$：
   • $(k,8)$-ケージから距離4の2つの頂点$u,v$を削除
   • $N_1(u), N_1(v), N_2(u,v)$を削除
   • 切除集合のサイズ：$3k$（de RuiterとBiggsの$3k-1$から改善）
2. 周囲長11：
   • $(4,12)$-ケージから：距離6の$u,v$を削除、$N_1(u), N_1(v), N_3(u,v)$および$N_2(u) \cap N_4(v)$内の1つの頂点を削除、$3k+3$個の頂点を切除
   • $(6,12)$-ケージから：類似の戦略、$5k-1$個の頂点を切除

実験設定

計算資源

• 総計算量：約5 CPU年
• インフラストラクチャ：フランドル・スーパーコンピュータセンター（VSC）
• 実装言語：C++ベース（推定、明示的に記載されていない）

基グラフと群の生成

1. 群：GAP システムを使用してすべての位数$n < 1024$の非同型群を生成
2. 基グラフ：
   • multigraph生成器の拡張（multigraph+）
   • 平行辺、ループ、半辺を含む連結正則グラフを生成
   • Nautyを使用して同型グラフを除去

検証戦略

1. 入力検証：
   • 群：GAPから直接取得
   • 基グラフ：pregraph生成器と比較（位数13まで）
2. 最適化の正確性：
   • 各最適化を個別に無効化（グラフ自同構、群自同構、周囲長界）
   • 生成された非同型リフトグラフの数が一致することを検証
3. 完全性検証：
   • 3つの独立した実装と比較：
     • $K_{1,3}$ベース構成
     • GrayおよびTheta グラフリフト
     • ブロック循環グラフ生成器（循環群リフトと等価）
   • すべてのケースで出力が完全に一致

フィルタリングプロセス

1. 連結性チェック
2. 同型フィルタリング：Nautyを使用して規範表現を構成
3. 周囲長と正則性の検証：29のアルゴリズムを使用

実験結果

主要結果：古典的ケージ問題（表2）

顕著な改善

切除技術の成果

• $(8,7) \leq 774$（777から3頂点改善）
• $(10,7) \leq 1608$（1611から3頂点改善）
• $(12,7) \leq 2890$（2893から3頂点改善）
• $(14,7) \leq 4716$（4719から3頂点改善）

主要な発見

1. $(4,10)$のブレークスルー：384から320に低下、低下率16.7%、最も驚くべき改善
2. 二部性の証拠：新しい$(3,16)$と$(4,10)$グラフは両方とも二部グラフであり、「偶周囲長ケージは二部グラフである」という予想を支持
3. 構成の詳細（図4）：
   • $(3,16)$：群$C_{13} \rtimes C_9$（位数117）を使用、基グラフ8頂点
   • $(4,10)$：群$C_5 \times D_4$（位数40）を使用、基グラフ8頂点

変体問題の成果

辺周囲長正則グラフ（表3）

• 21個の新しい界、その中2個の厳密な界（上下界が等しい）：
  • $n(4,5,4) = 30$（新規決定）
  • 複数の$(6,5,\lambda_e)$ケースで初めて上界を取得

頂点周囲長正則グラフ（表4）

• 29個の新しい界、その中7個の厳密な界：
  • $n(3,7,1) = n(3,7,2) = n(3,7,4) = 42$
  • $n(4,5,1) = n(4,5,6) = n(4,5,7) = 30$
  • 複数の$(4,6,\lambda_v)$ケースで大幅に改善

$(k,g)$-スペクトラム（表5）

• 34個の以前に未解決だった位数を決定
• 主に以下に集中：
  • $(3,11)$と$(3,12)$：7個の新しい位数
  • $(4,7)$と$(4,8)$：12個の新しい位数
  • $(5,7)$：24個の新しい位数（184から256）

$(g+1)$-環なしグラフ（表6）

• 6個の新しい界：
  • $n(3,11,12) \leq 228$（272から改善）
  • $n(3,13,14) \leq 600$（800から改善）
  • $n(3,15,16) \leq 1760$（2162から改善）

アルゴリズム効率分析

時間配分戦略

• 各基グラフ-群の組み合わせ：BTA 20秒、TS 20秒
• TS初期解探索：2秒
• グラフ自同構探索：2秒

アルゴリズムの相補性

1. BTA：小インスタンスの完全列挙、完全性を保証
2. TS：大インスタンスの探索的サンプリング、スケーラビリティが良好
3. 登山：基グラフと割り当てを同時に最適化、柔軟性が高い
4. 切除：既知の大グラフを利用、対象性が強い

関連研究

古典的ケージ問題の研究

1. 理論的界：
   • Moore界（1963）：基本的な下界
   • Sauer (1967)：$n(k,g) < n(k,g+1)$不等式
   • Wong (1982)：ケージ総説
2. 構成方法：
   • Balaban (1972-1973)：$(3,10)$と$(3,11)$ケージ
   • Benson (1966)：$(k,12)$ケージ
   • Biggs一連の研究：複数の小周囲長グラフ
3. 計算方法：
   • McKay等（1998）：ケージ用の高速バックトラッキング
   • Exoo (2002-2020)：電圧グラフ技術
   • de Ruiter & Biggs (2015)：整数計画法と切除

リフト理論

• Gross & Tucker (1987)：位相グラフ理論の基礎
• Exoo & Jajcay (2011)：電圧グラフリフトの周囲長理論
• 本論文：体系的な最適化とヒューリスティック方法の拡張

変体問題

1. 周囲長正則グラフ：
   • Jajcay等（2018）：辺周囲長正則グラフ
   • Jajcay等（2024）：頂点周囲長正則グラフ
   • Goedgebeur & Jooken (2025)：完全列挙生成
2. スペクトラム問題：
   • Eze等（2025）：$(k,g)$-スペクトラムの理論と計算方法
3. 短環なしグラフ：
   • Eze等（2026）：$(k,g,g+1)$-グラフおよびケージ問題との関連

本論文の利点

1. 体系的フレームワーク：ケージ問題と複数の変体を統一的に処理
2. アルゴリズムの相補性：4つの方法が異なる規模と特性をカバー
3. 実質的な改善：複数の長期記録を打破
4. 開放リソース：コードとデータが完全に公開

結論と議論

主要な結論

1. 古典的ケージ問題のブレークスルー：
   • 11個の新しい上界、その中$(4,10)$の改善が最も顕著（384→320）
   • 一部の界は22年間保持された後、初めて改善
   • $(4,11)$と$(6,11)$に対する初めての非自明な上界
2. 変体問題の進展：
   • 辺/頂点周囲長正則グラフ：50個の新しい界（9個の厳密な界）
   • $(k,g)$-スペクトラム：34個の新規決定位数
   • $(g+1)$-環なしグラフ：6個の改善界
3. 方法論的貢献：
   • リフトに基づく体系的なアルゴリズムフレームワーク
   • 構造化および割り当てベースの除外規則
   • 探索的および完全列挙方法の効果的な組み合わせ

限界

1. 計算複雑度：
   • 大きな$(k,g)$パラメータはまだ処理困難
   • 大量の計算資源が必要（5 CPU年）
   • ヒューリスティック方法は最適解の発見を保証しない
2. 方法の適用範囲：
   • リフト方法は適切な基グラフと群の存在に依存
   • 切除技術は既知の大グラフを開始点として必要
   • 特定のパラメータ組み合わせは改善されていない（既知のケージなど）
3. 理論的ギャップ：
   • ほとんどのケースで上下界の差はまだ大きい
   • 新しい下界改善は提供されていない
   • 一部のパラメータでは上界が「?」（未知）と標記されている
4. ハイパーパラメータの感度：
   • 時間制限、禁忌リストサイズなどは経験的調整が必要
   • ハイパーパラメータ最適化の体系的研究がない

今後の方向

1. 理論的方向：
   • 新しく構成されたグラフから無限族を導出
   • Moore界およびその変体を改善
   • 偶周囲長ケージの二部性予想を証明または反証
2. アルゴリズムの改善：
   • より効率的な周囲長計算アルゴリズムの開発
   • 機械学習支援のヒューリスティック設計の探索
   • 現代的なマルチコアアーキテクチャを利用した並列化
3. 切除技術の一般化：
   • 切除集合選択戦略の体系化
   • より多くの$(k,g)$パラメータペアへの推広
   • 切除方法の有効性の理論的分析
4. 応用の探索：
   • 新発見グラフのネットワーク設計への応用
   • 誤り訂正符号での応用の探索
   • 暗号学関連特性の研究

深い評価

利点

1. 重大な実証的貢献：
   • 22年間保持された複数の記録を打破、特に$(4,10)$の大幅改善
   • 多数の具体的構成を提供し、理論研究の素材を提供
   • 特定のパラメータに対する初めての非自明な界限
2. 方法論的革新：
   • 体系的な除外規則：構造的および割り当てベースの除外が探索空間を大幅に削減
   • アルゴリズムの相補性：BTA、TS、登山、切除が異なるシナリオをカバー
   • 増分検証：アルゴリズム2の増分周囲長チェックが効率を向上
   • 規範性チェック：対称性を利用して冗長計算を回避
3. 実験設計の厳密性：
   • 多層検証戦略（入力、最適化、完全性）
   • 3つの独立実装との比較
   • 詳細なハイパーパラメータ設定説明
   • 完全な再現性サポート
4. 研究の広さ：
   • 古典的問題だけでなく4つの変体を体系的に研究
   • 複数の変体に対する初めての上界を確立
   • 異なる問題を統一フレームワークで処理
5. 開放科学の実践：
   • コードとデータが完全に公開（GitHub）
   • グラフはHouse of Graphsデータベースに収録
   • 検証可能な証明書を提供（構成されたグラフ）

不足

1. 理論的深さの限定：
   • 主に計算/実証的作業で、深い理論的洞察に欠ける
   • 新しい下界や理論的分析を提供していない
   • 特定のパラメータで改善が顕著な理由の理論的説明に欠ける
2. 方法の完全性：
   • ヒューリスティック方法（TS、登山）に完全性保証がない
   • ハイパーパラメータ選択は経験的で、体系的研究に欠ける
   • 異なるアルゴリズムの理論的保証や収束性の分析がない
3. 実験報告の詳細：
   • 異なる改善に対する各アルゴリズムの具体的貢献が報告されていない
   • 実行時間の詳細分析に欠ける
   • 失敗ケースや困難なインスタンスの議論がない
4. スケーラビリティの問題：
   • より大きな$k$と$g$に対する方法の実行可能性が不明
   • パラメータ増加に伴う計算資源需要の規則性が分析されていない
   • 一部の結果が「≥100」と標記され、完全な探索がされていないことを示唆
5. 文章構成：
   • 技術的詳細が密集しており、非専門家にとって読みやすさに課題
   • 一部のアルゴリズム説明（アルゴリズム4の疑似コード欠落など）が不完全
   • 結果表が多数あるが、統一的な要約分析に欠ける

影響力

1. 学術的影響：
   • 高い：ケージ問題は古典的な極値グラフ理論の問題で、長期記録の改善は重要
   • 57-Moore グラフなどの著名な未解決問題への間接的な研究経路を提供
   • 方法は他の極値グラフ問題に推広可能
2. 実用価値：
   • 中程度：新しいグラフはネットワークトポロジー設計、誤り訂正符号に利用可能
   • オープンソースツールは他の研究者が利用可能
   • アルゴリズムフレームワークは関連する組合せ最適化問題に適用可能
3. 再現性：
   • 優秀：完全なコードとデータが公開
   • 詳細な検証戦略が信頼性を向上
   • 具体的な構成は独立して検証可能
4. 後続研究の可能性：
   • 新しい構成が無限族の発見を促す可能性
   • アルゴリズムフレームワークは他のグラフ生成問題に適用可能
   • 変体問題の初期結果が新しい研究方向を開く

適用シーン

1. 直接応用：
   • 小型高周囲長正則グラフが必要なネットワーク設計
   • LDPC符号などの誤り訂正符号の構成
   • 鍵共有などの暗号学応用
2. 研究ツール：
   • 極値グラフ理論の計算実験
   • グラフ同型と規範化アルゴリズムのテスト
   • 組合せ最適化ヒューリスティックのベンチマーク
3. 教育資源：
   • 純粋数学における計算方法の応用を示す
   • アルゴリズム設計と最適化のケーススタディ
   • 開放科学と再現可能研究の範例
4. 推広分野：
   • 他の極値グラフ問題（Ramsey数、Turán問題など）
   • 制約充足問題
   • 組合せ設計と符号理論

参考文献（精選）

1. 基礎理論：
   • 45 Sachs (1963)：すべての$k \geq 2, g \geq 3$に対して$(k,g)$-グラフが存在することを証明
   • 31 Gross & Tucker (1987)：位相グラフ理論とリフト理論
   • 47 Wong (1982)：ケージの包括的総説
2. 計算方法：
   • 24 Exoo等 (2011)：$(3,11)$と$(4,7)$ケージの計算的決定
   • 38 McKay等 (1998)：高速バックトラッキング原理
   • 15 de Ruiter & Biggs (2015)：整数計画法
3. 最新の進展：
   • 22 Exoo & Jajcay (2011)：電圧グラフリフトの周囲長理論
   • 29 Goedgebeur & Jooken (2025)：辺周囲長正則グラフの完全列挙生成
   • 34 Jajcay等 (2024)：頂点周囲長正則グラフ
4. ツール：
   • 37 McKay & Piperno (2014)：Nautyグラフ同型ソフトウェア
   • 27 GAP システム：群論計算
   • 12 House of Graphs：グラフデータベース

総合評価：これは計算組合せ数学の高品質論文であり、体系的なアルゴリズム開発と大規模計算実験を通じて、古典的ケージ問題およびその変体で顕著な実証的進展を達成している。方法論上の革新（特に除外規則とアルゴリズムの相補性）と厳密な検証戦略が主要な強みである。理論的深さは限定的であるが、実証的貢献、開放科学の実践、および領域への推進力により、この論文は極値グラフ理論の重要な貢献となっている。極値グラフ理論、グラフアルゴリズム、または組合せ最適化に従事する研究者にとって、この論文は貴重な方法とリソースを提供する。