Graph Puzzles III.1: A Proof of Sabidussi's Compatibility Conjecture

技術的要約：サビディウスィの適合性予想の証明

問題提起
本論文は、有限連結多重グラフの文脈において、サビディウスィ（Sabidussi）の適合性予想（compatibility conjecture）に対処するものである。具体的には、最小次数 $\delta(G) \geq 4$ を持つオイラー多重グラフ $G$（すべての頂点の次数が偶数であるグラフ）を対象とする。すべてのエッジを正確に一度ずつ通る閉路（オイラー・ツアー） $T$ が与えられたとき、グラフ $G$ のエッジを、回路（連結な2正則部分グラフ）へと分割できるかという問題である。ただし、その際、どの回路も $T$ において連続して現れる2つのエッジを含んではならないものとする。

遷移システム（transition systems）の言葉を用いれば、オイラー・ツアーは各頂点における半エッジ（half-edges）のペアリングを誘導する。回路分解が「適合（compatible）」しているとは、回路が、ツアーによって規定された遷移としてペアリングされている半エッジを組み合わせないことを意味する。この予想は、与えられた次数の制約下において、そのような適合的な分解が常に存在することを主張している。

手法
証明は、グラフ理論的な問題から、巡回語（cyclic words）に関する組合せ論的問題への還元を通じて進行し、続いて $\mathbb{F}_2$ 上のパリティ議論を用いた代数的構成へと続く。

1. 巡回語への還元:
   著者らは、オイラー・ツアー $T$ によって訪問される頂点の列を表す巡回語 $w = (v_0, v_1, \dots, v_{m-1})$ を定義する。ツアーのエッジは、これらの文字間の「隙間（gap）」に対応する。問題は、これらの隙間に $\mathbb{F}_2^2$ の要素（4彩色）をどのように彩色するかという問題へと再定式化される。その際、以下の条件を満たす必要がある：

   • 隣接する隙間（ツアーにおける連続するエッジに対応するもの）は、異なる色を受け取る。
   • グラフのすべての頂点 $v$ について、 $v$ の出現に付随する隙間に割り当てられた色の集合は、パリティ条件を満たす。すなわち、各色は、隙間のインシデンスの中で偶数回出現しなければならない。

2. 代数的枠組み:
   証明の核となるのは、セクション3で確立された2つの補題に基づく：

   • 補題 3.1（4彩色パリティ）: $\mathbb{F}_2^2$ の要素の族において、各要素が偶数回含まれるための必要十分条件は、それらの線形和がゼロであり、かつ（特定の双線型形式 $q(x) = x_1x_2$ を通じた）二次和がゼロであることである。
   • 補題 3.2（3状態バランシング）: 有限集合 $U$ と3要素集合 $\Sigma$ に対する大域的な選択原理。関数 $\beta$ が特定の対称性とゼロ和条件を満たす場合、局所的な制約系を満たす割り当ての数は奇数（したがって非ゼロ）となる。

3. 彩色の構成:
   証明は、以下の手順で必要な隙間の彩色を構成する：

   • 各文字 $a$ に対する「局所パターン」 $\Delta_{a,t}$ を定義し、これによって巡回語内の $a$ の出現に対して、和がゼロとなる $\mathbb{F}_2^2$ の非ゼロ値を割り当てる。
   • 語内における異なる文字間の相互作用項 $\beta_{ab}$ を定義する。
   • 補題 3.2 を適用して、各文字 $a$ に対して特定の状態 $t_a \in \Omega$ （ここで $\Omega = \mathbb{F}_2^2 \setminus \{0\}$）を選択する。この選択により、相互作用の制約が消失する。
   • これらの選択を用いて、数列 $y_i$（隙間の色の差）を定義し、それらを積分することで隙間の色 $x_i$ を復元する。
   • 得られた彩色が、補題 3.1 を用いて、各頂点において各カラークラスの次数が偶数になることを示すことで、各頂点における色の和と二次形式の和が消滅することを確認し、各頂点での偶数次数条件を満たすことを検証する。

主要な貢献と結果

• 定理 1.1: 本論文は、最小次数が4以上である任意の有限オイラー多重グラフと任意のオイラー・ツアー $T$ に対して、隣接するエッジが異なる色を持ち、かつ各頂点が各カラークラスにおいて偶数次数を持つような彩色 $\chi: E(G) \to \mathbb{F}_2^2$ が存在することを証明する。
• 系 1.2: その結果として、グラフ $G$ は $T$ によって誘導される遷移システムと適合する回路分解を持つ。
• サイクル二重被覆の改善: 本論文は、支配的回路（dominating circuit）が存在する場合、この結果は、ある3次グラフ $H$ がその回路を含む5サイクル二重被覆を持つことを示唆すると述べている。これは、支配的回路を持つグラフに対して最近証明された8サイクル二重被覆定理（本文中ではOpenAIによるものとされる）を改善するものである。
• 形式化: 証明は、Lean定理証明器によって完全に形式化されている。

意義と主張
本論文は、Kotzig (1968) や Fleischner (1980) の研究以来検討されてきた問題である、サビディウスィの適合性予想の完全な証明を提供すると主張している。過去の研究では、平面グラフ、 $K_5$ 除去グラフ、または特定の次数制約を持つグラフについてはこの予想を確立していたが、本証明は、最小次数の要件を除いてグラフのクラスを制限することなく、すべての偶数次数を直接扱う。

著者らは、この証明が元の予想の強化版であることを明言している。それは単なる分解ではなく、特定の構造的特性を持つ4彩色を提供するものである。この研究は、巡回語の組合せ論と有限体上のパリティ補題の斬新な組み合わせに依拠した、予想に対する決定的な解決策として提示されている。

著者に関する注記
論文には、証明はすべて「GPT 5.6 Pro」によるものであり、執筆は「GPT 5.6 Sol」の支援を受けて準備されたことが明記されている。人間の著者である Nikolay Ulyanov は、数学的議論および記述の生成における AI の役割を認めている。