Planar-Toroidal Decomposition of $K_{12}$

Each language version is independently generated for its own context, not a direct translation.

この論文は、数学の「グラフ理論」という分野における、とても面白い「パズル」の解決を報告したものです。専門用語を避け、身近な例えを使って簡単に説明しましょう。

🎨 物語のテーマ：「12 人のパーティーと 2 つの部屋」

想像してください。12 人の人が集まるパーティー（これを数学の言葉で「完全グラフ K12」と呼びます）があるとします。このパーティーでは、誰と誰もが直接会話できる状態になっています。つまり、12 人の全員が互いに手を握り合っているような状態です。

さて、この「全員が繋がり合う状態」を、2 つの異なる部屋に分けて整理したいとします。

部屋 A（平らな部屋）： ここは「平面（フラット）」な部屋です。壁も天井もありませんが、床に描かれた線が決して交差してはいけません。地図のように、線が重ならないように配置できる部屋です（これを「平面グラフ」と呼びます）。
部屋 B（ドーナツ型の部屋）： ここは「ドーナツ（トーラス）」の形をした部屋です。ドーナツには穴が開いていますが、その表面に線を描くなら、交差しても大丈夫なルールです（これを「トーラスグラフ」と呼びます）。

問い： 「12 人の全員が繋がり合う状態（K12）を、この『平らな部屋』と『ドーナツ型の部屋』の 2 つに分けて、完全に整理できるでしょうか？」

これが、1978 年に Anderson と White という研究者たちが「できるのか？」と疑問に思った問題です。

🔍 研究者たちの挑戦：「できるはずだ、でもできない！」

この論文の著者たち（Allan Bickle と Russell Campbell）は、この疑問に答えるために、2 つのアプローチを取りました。

1. 頭脳戦（理論的なアプローチ）

まず、数学の公式や論理を使って、「もし可能だとしたら、どんな条件を満たさなければならないか」を調べました。

「部屋 A（平らな部屋）には、線が多すぎると交差してしまうので、人数や線の数に上限がある」
「もし 12 人が部屋 A にいるなら、残りの線は部屋 B（ドーナツ）に行く必要がある」
「特定の人のつながり方（次数）がこうだと、矛盾が生まれる」

彼らは「もしこのパズルが解けるなら、こんな形にならなければならない」という条件をいくつも絞り込みました。しかし、理論だけでは「絶対に無理だ」と証明するには、まだ隙間が残っていました。

2. 総当たり戦（コンピューターの力）

そこで、彼らはコンピューターに頼りました。

「12 人」の「平らな部屋（平面グラフ）」の作り方は、全部で7,595 通りあります。
コンピューターは、この 7,595 通りのすべてについて、「残りの線（補グラフ）がドーナツ型の部屋に収まるか？」を一つずつチェックしました。

結果：
「残念ながら、1 つも成功しませんでした！」

つまり、**「12 人の全員が繋がり合う状態を、平らな部屋とドーナツ型の部屋に完璧に分けることは不可能」**であることが証明されました。

💡 意外な発見：「2 本だけ消せばできる！」

さらに面白い発見がありました。
「完全に分けるのは無理だが、2 本の線（会話）を諦めて消し去れば、残りはドーナツ型の部屋に収まるのか？」と試してみたのです。

結果： なんと、123 通りの組み合わせが見つかりました！
これらは、平らな部屋に 12 人を配置し、残りの線から2 本だけを「今回は無理」として削除すれば、ドーナツ型の部屋に綺麗に収まるパターンです。

図 1 と図 2 は、その成功例のイメージ図です。点線で描かれた 2 本の線が「削除された会話」を表しています。

🏆 この研究の意義

この研究は、数学界の長い疑問（「N(0,1) = 12 か？」という問題）に決着をつけました。

結論： 「12 人」のケースでは、平らな部屋とドーナツ型の部屋に完全に分けることはできない。
意味： これにより、以前に提唱されていた「どんな人数でも、平らな部屋とドーナツ型の部屋に分けられるかもしれない」という予想（Bickle/White の予想）が、12 人のケースで誤りであることが証明されました。

📝 まとめ

この論文は、**「12 人の全員が繋がり合うという複雑な関係を、平らな紙とドーナツの 2 つの表面に、交差なしで完全に書き分けることは不可能だ」**と証明したものです。

平らな紙には限界があり、ドーナツにはある程度の余裕がある。
しかし、12 人という人数は、その 2 つの限界をちょうど超えてしまう「魔法の数字」だったのです。
もし2 本の線を捨てるなら、なんとかなる（123 通りの方法がある）という、少しだけ救いのある結論も出ています。

これは、数学的なパズルを、理論とコンピューターの総当たり戦で解き明かした、現代の探偵物語のような研究です。

Each language version is independently generated for its own context, not a direct translation.

この論文「Planar-Toroidal Decomposition of K12（K12 の平面・トーラス分解）」は、離散数学および理論計算機科学の分野において、完全グラフ $K_{12}$ を「平面グラフ」と「トーラスグラフ（トーラス上に埋め込めるグラフ）」の 2 つに分解できるかどうかという長年の未解決問題に決着をつけた研究です。

以下に、問題の背景、手法、主要な貢献、結果、および意義について詳細な技術的サマリーを記述します。

1. 問題の背景と定義

分解（Decomposition）: グラフ $G$ の辺集合を、空でない部分グラフ（ファクター）の集合に分割すること。
厚さ（Thickness）: グラフ $G$ を分解する必要がある平面グラフの最小数 $\theta(G)$ 。
トーラス厚さ（Toroidal Thickness）: グラフ $G$ を分解する必要があるトーラス埋め込み可能グラフの最小数。
研究の動機:
- 1978 年、Anderson と White は、 $K_{12}$ を平面グラフとトーラスグラフの 2 つに分解できるかどうかを問いました。
- これは、 $N(0, 1)$ （平面とトーラスにそれぞれ埋め込める 2 つの部分グラフに分割できない最小の完全グラフのサイズ）を決定する問題と等価です。
- 既存の結果として、 $N(0, 0)=9$ （平面のみ）、 $N(1, 1)=14$ （トーラスのみ）などが知られていましたが、 $N(0, 1)$ の値は不明でした。
- 2013 年の Bickle と White の予想（Conjecture 1.5）は、 $n \ge 11$ において $\gamma(G) + \gamma(\bar{G})$ の下限が達成されるとしていましたが、 $n=12$ の場合、この予想が成り立つためには $K_{12}$ の平面・トーラス分解が存在する必要があると解釈されていました。

2. 手法（Methodology）

著者らは、理論的なアプローチと大規模なコンピュータ探索を組み合わせるハイブリッド手法を用いました。

A. 理論的アプローチ

$K_{12}$ の分解が存在すると仮定した場合、平面グラフ $G$ とその補グラフ $\bar{G}$ （トーラスグラフ）が満たすべき必要条件を導出しました。

次数の制約:
- 最大次数 $\Delta(G) \le 8$ 、最小次数 $\delta(G) \ge 3$ などの制約を導出。
- 次数 8 の頂点を持つ場合、その非隣接頂点 3 個は独立集合を形成し、かつ次数 8 の頂点同士はすべて隣接している必要があることを証明（Lemma 2.3）。
三角形の数の計数:
- Goodman の公式を用いて、グラフとその補グラフの三角形の数の和を次数列の関数として表現。
- 平面グラフは少なくとも 20 個の三角形を持ち、トーラスグラフは少なくとも 24 個の三角形を持つ必要があるため、特定の次数列（例：$5^{12}$ など）を持つグラフは候補から除外可能であることを示しました（Corollary 2.5）。
分離集合（Separating Sets）の解析:
- 平面グラフ $G$ が特定の構造（分離三角形や分離 4 輪）を持つ場合、補グラフ $\bar{G}$ がトーラスに埋め込めないことを証明。
- 具体的には、 $K_{4,5}$ や $K_{3,6}$ などの部分グラフの出現がトーラス埋め込みの障害となることを利用し、多くのケースを排除しました（Theorem 2.7, 2.8）。

B. コンピュータ探索

理論的アプローチだけではすべてのケースを排除できなかったため、計算機による網羅的探索を行いました。

対象データ: 12 頂点の最大平面グラフ（三角分割）は全部で 7,595 個存在します（Combinatorial Object Server より）。
フィルタリング:
- 最大次数が 9 以上のグラフを除外（3,476 個を除去）。
- 次数 8 の頂点と非隣接な 3 頂点が独立集合を形成しないグラフを除外。
埋め込み検証:
- 残った平面グラフの補グラフについて、トーラスへの埋め込みが可能か検証。
- ステップ 1: 補グラフそのものがトーラス埋め込み可能か（結果：なし）。
- ステップ 2: 補グラフから 1 辺を削除した場合（結果：なし）。
- ステップ 3: 補グラフから 2 辺を削除した場合（結果：123 組のユニークなペアが見つかる）。
実装:
- Intel i7-9750H プロセッサ搭載のノート PC で実行。
- 2 辺削除の探索には約 59 日かかった。
- 同型な埋め込みを除去し、123 組の「最大トーラス埋め込み（2 辺欠損）」を特定。
- 生成された 7,595 個の平面三角分割の画像コレクションも GitHub で公開。

3. 主要な結果（Results）

$K_{12}$ の分解の不存在:
- $K_{12}$ を平面グラフとトーラスグラフの 2 つに分解することは不可能であることが証明されました。
- つまり、 $N(0, 1) = 12$ です（ $K_{11}$ は分解可能であることが既知のため）。
辺数の関係:
- $G$ が 12 頂点の平面グラフで、 $H \subseteq G$ がトーラスグラフである場合、 $H$ は $G$ より少なくとも 2 辺少ないことが示されました。
- 等号が成立する（ $G$ から 2 辺を除いたものがトーラスグラフになる）ケースは、123 組のユニークな $(G, H)$ のペアとして特定されました。
予想の反証:
- Bickle/White の予想（Conjecture 1.5）は、 $n=12$ の場合に反証されました。 $n=12$ において、 $\gamma(G) + \gamma(\bar{G}) = 1$ となるグラフ $G$ は存在しないためです。

4. 意義と貢献（Significance）

未解決問題の解決: 1978 年以来の Anderson と White による問いに決着をつけ、 $N(0, 1)$ の正確な値を 12 として確定させました。
理論と計算の融合: 複雑なトポロジカルな問題に対し、理論的な制約条件による絞り込みと、大規模な計算機探索を組み合わせる手法の有効性を示しました。
アルゴリズムとデータセットの提供:
- トーラス埋め込みアルゴリズムの検証に使える 123 組の特殊なグラフペアを公開しました。
- 12 頂点のすべての平面三角分割（7,595 個）の画像とデータセットを GitHub で公開し、将来的な研究やアルゴリズム開発の基盤を提供しています。
今後の研究への示唆:
- $N(\gamma, \gamma')$ の他の値や、より一般的なグラフ分解問題に対するアプローチとして、分離集合や三角形の計数を用いた理論的フィルタリング手法が有効であることが示されました。

結論

この論文は、 $K_{12}$ が平面とトーラスの 2 つのグラフに分解できないことを証明し、関連するグラフ理論の予想を反証しました。また、その証明過程で得られた膨大なデータと、理論的アプローチと計算機探索を統合した手法は、離散幾何学およびグラフ埋め込み分野における重要なリソースとなっています。

Planar-Toroidal Decomposition of K12K_{12}K12​