Partitioning perfect graphs into comparability graphs

この論文は、完全グラフの辺集合を比較可能性グラフに分割する際に、多くのクラスや「ほとんどすべての」完全グラフでは最大 2 つで十分である一方、区間グラフでは任意に大きな数が必要となる場合があることを示しています。

要約

完璧なグラフを「比較可能な」グループに分ける：ある数学の探検

この論文は、**「完璧なグラフ（Perfect Graph）」という特殊な図形（ネットワーク）を、「比較可能なグラフ（Comparability Graph）」**というより単純な図形に、いくつに分ければよいのか？という問題を研究したものです。

少し難しい言葉が出てきますが、ここでは**「人間関係のネットワーク」や「本棚」**のような身近な例えを使って、内容をわかりやすく解説します。

---

1. 物語の舞台：2 つの「図形」の世界

まず、登場する 2 つのキャラクターを理解しましょう。

• 完璧なグラフ（Perfect Graph）：
  これは、とても秩序だった社会のようなものです。この社会では、「一番大きな仲良しグループ（ clique）」の人数と、「全員を色分けして仲の悪い人同士が隣り合わないようにする」のに必要な色の数が、常に一致します。

  • 例え: 教室で、一番多い「仲良しグループ」が 5 人なら、席替えで「隣り合う人が違う色になる」ようにするには、ちょうど 5 色あれば十分、という完璧なバランスが保たれている状態です。

• 比較可能なグラフ（Comparability Graph）：
  これは、「順位」や「上下関係」がはっきりしている社会です。A が B より偉く、B が C より偉ければ、A は C より偉い（という順序関係）が成り立つ図形です。

  • 例え: 会社の組織図や、本棚の本を「太さ順」に並べた状態。誰と誰が比較できるかが明確です。

研究の問い：
「完璧な社会（完璧なグラフ）を、できるだけ少ない数の『比較可能な社会（比較可能なグラフ）』に分割して、そのすべての『関係（辺）』をカバーするには、いくつ必要だろうか？」

---

2. 発見その 1：ほとんどの場合、2 つで十分！

著者たちは、**「ほとんどすべての完璧なグラフは、たった 2 つの比較可能なグラフに分割できる」**という驚くべき結果を見つけました。

• どんなグラフでも？
  数学の世界には「ほとんど」という言葉があります。例えば、100 人、1000 人、1 億人の人間関係のネットワークをランダムに作ったとき、その**99.99...%**は、たった 2 つの「比較可能なグループ」に分ければ整理できるのです。
• なぜ 2 つでいいの？
  多くの完璧なグラフは、実は「完全なグループ（みんなが仲良し）」と「独立したグループ（誰も仲良くない）」が組み合わさったような構造（GSP グラフ）をしていることが多く、これらは 2 つの比較可能な部分に分けやすいからです。

結論： 完璧な社会のほとんどは、2 つのルール（比較可能なルール）で片付くのです。

---

3. 発見その 2：しかし、例外も存在する（区間グラフの罠）

ところが、すべての完璧なグラフが 2 つで済むわけではありません。特に**「区間グラフ（Interval Graph）」**と呼ばれる、ある特定の種類のグラフでは、いくつあっても足りないことがありました。

• 区間グラフとは？
  直線上に「区間（例えば 1 日から 3 日まで）」を並べ、重なり合っているものを「つながっている」とみなしたグラフです。

  • 例え: 会議室の予約表。1 時間目と 2 時間目が重なる予約同士は「つながっている」とします。

• なぜ大変なのか？
  著者たちは、区間の数が $n$ 個あるとき、必要な比較可能なグラフの数は、**$n$ の対数の対数（$\log \log n$）**くらい必要になることを証明しました。

  • イメージ: 区間の数が 1 万個あっても、必要なグループ数は 4〜5 個程度で済みますが、区間が 1 億個、10 兆個と増えると、必要なグループ数もゆっくりと増え続けます。
  • 重要な点: いくら区間を増やしても、必要なグループ数は「無限大」にはなりませんが、「2 つで済む」という保証はなくなります。 巨大な区間グラフでは、2 つのルールでは整理しきれない複雑さがあるのです。

---

4. 発見その 3：小さな「3 つ」が必要なグラフ

「巨大なグラフなら 3 つ以上必要かもしれない」と思いますが、実は**「小さなグラフ」でも 3 つ必要になるケース**があることがわかりました。

• 小さな例え：
  9 列×4 行のマス目（チェス盤のようなもの）に、各マスから 1 本ずつ「ひも」をぶら下げたようなグラフ（$H_{9,4}$）を作ると、これを 2 つの比較可能なグループに分けることは不可能で、最低でも 3 つ必要になります。
  • これは、グラフが小さくても、その「絡み方」が非常に複雑で、2 つのルールでは整理しきれないことを示しています。

---

まとめ：この研究が教えてくれること

この論文は、数学的な「完璧さ」と「整理のしやすさ」の関係を解き明かしました。

1. 基本はシンプル： 世の中のほとんどある「完璧なネットワーク」は、**2 つのルール（比較可能なグループ）**で整理できます。
2. 例外は存在する： しかし、特に「区間（時間や長さ）」が絡む複雑なネットワークでは、2 つでは足りず、もっと多くのルールが必要になることがあります。
3. 小さくても複雑： 巨大なグラフだけでなく、小さなネットワークでも、3 つのルールが必要になるほど複雑な絡み合いが存在します。

一言で言うと：
「完璧に見える世界も、その中身を見つめると、2 つのルールで片付くものもあれば、もっと多くのルールが必要になる複雑な絡み合いが潜んでいる」ということが、この研究で明らかになりました。

数学は、一見単純なルールが、実は奥深い多様性を持っていることを教えてくれるのです。

技術概要

1. 問題設定と背景

• 研究対象: 完全グラフ（Perfect Graphs）の辺集合を、互いに辺を共有しない比較可能グラフ（edge-disjoint comparability subgraphs）の集合に分割する際に必要な最小個数 $p(G)$、および辺を共有してもよい被覆（cover）に必要な最小個数 $c(G)$ を調べる。
  • $p(G)$: 辺を分割する場合の最小比較可能グラフ数。
  • $c(G)$: 辺を重複させて被覆する場合の最小比較可能グラフ数。
  • 明らかに $p(G) \ge c(G)$ である。
• 背景:
  • 完全グラフは、任意の誘導部分グラフ $H$ に対して $\omega(H) = \chi(H)$（最大クリーク数＝彩色数）を満たすグラフである。
  • 比較可能グラフは、部分順序集合の可比較な要素対を辺とするグラフであり、これ自体も完全グラフの一種である。
  • Harary, Hsu, Miller の定理（Theorem A）により、任意のグラフ $G$ は $\lceil \log(\chi(G)) \rceil$ 個の二部グラフに分割できることが知られている。完全グラフでは $\chi(G)=\omega(G)$ であるため、これを用いると $p(G) \le \lceil \log(\omega(G)) \rceil$ となることが示唆される。
  • しかし、三角形を持たないグラフ（$\omega(G)=2$）でも彩色数 $\chi(G)$ が任意に大きくなる場合があり、その場合 $c(G)$ も大きくなる。一方、完全グラフではこの議論が通用しないため、「完全グラフに対して $c(G)$ は有界か？」が問われる。

2. 主要な結果と貢献

この論文は、完全グラフのクラスによって $p(G)$ や $c(G)$ の振る舞いが大きく異なることを示し、以下の主要な定理を証明している。

A. ほぼすべての完全グラフは 2 つの比較可能グラフで分割可能

定理 2: 「ほぼすべての（almost all）」完全グラフ $G$ に対して、$c(G) \le p(G) \le 2$ が成り立つ。

• 手法:
  • 「強い完全グラフ定理（Strong Perfect Graph Theorem）」と、Prömel-Steger の「一般化分割グラフ（GSP graphs）」に関する結果（Berge グラフのほとんどは GSP である）を組み合わせる。
  • GSP グラフの性質（定理 4）: GSP グラフは、完全グラフと独立集合の和、あるいはその補グラフの構造を持ち、これらは常に 2 つの比較可能グラフに分割可能であることを証明。
• 意義: 完全グラフの「典型的な」構造は非常に単純であり、2 つの比較可能グラフで十分であることを示した。

B. 特定の完全グラフクラスにおける上界

以下のクラスでは、$p(G) \le 2$ が成り立つことが証明された。

• 二部グラフの線グラフ（Theorem 5）: 二部グラフの線グラフは 2 つの比較可能グラフに分割可能。
• 単位区間グラフ（Theorem 6）: 長さ 1 の区間の交差グラフ。区間の右端点に基づいた貪欲な分割法により、2 つの比較可能グラフ（1 つは完全グラフの和、もう 1 つは二部グラフ）に分割可能。
• co-triangulated グラフ（Theorem 7）: 木の部分木の非交差グラフ（区間グラフの補グラフの一般化）。部分木の根からの距離と辞書式順序に基づく 2 つの異なる部分順序を定義し、それらの比較可能グラフの和で辺を分割可能であることを示した。

C. 区間グラフにおける任意に大きな分割数

定理 10 と 11: 区間グラフ（Interval Graphs）のクラスにおいては、$c(G)$ および $p(G)$ が任意に大きくなる可能性がある。

• 構成: $n$ 個の整数点からなる区間 $\{[i, j] \mid 1 \le i < j \le n\}$ の交差グラフ $G_n$ を考える。
• 下限（Theorem 10）: $c(G_n) \ge \frac{1}{2} \log \log n$。
  • 手法: 「 touching edges（接する区間の対）」の構造が「ダブルシフトグラフ（Double Shift Graph, $DS_n$）」と関連することを利用。$DS_n$ の彩色数が $\log \log n$ 程度であることを利用し、比較可能グラフへの分割が彩色数に制約されることを示した。
• 上限（Theorem 11）: $p(G_n) \le O((\log \log n)^2)$。
  • 手法: 区間を「内部区間」と「外部区間」に分類し、再帰的な構造（Lemma 12）を用いて分割数を評価。$p(n)$ の漸近的上界を $O((\log \log n)^2)$ まで絞り込んだ。
• 意義: 完全グラフであっても、そのクラス（特に区間グラフ）によっては比較可能グラフへの分割数が対数的に増加し、定数では抑えられないことを示した。

D. 小さな例：$p(G)=3$ を満たすグラフ

命題 15: $K_9 \square K_4$（完全二部グラフ $K_{9,4}$ の線グラフ）に各頂点から 1 本のpendant 辺（葉）を付加したグラフ $H_{9,4}$ は完全グラフであり、$p(H) = c(H) = 3$ となる。

• 手法: 行と列の完全グラフ構造、および pendant 辺の配置を分析し、2 つの比較可能グラフでは分割不可能であることを背理法で証明。
• 意義: $p(G)=3$ となる具体的な小さな完全グラフの存在を示した。

3. 結論と意義

1. パラメータの非有界性の発見: 完全グラフ全体に対して $c(G)$ が有界であるという予想は否定された。区間グラフの特定の族において、$c(G)$ は $\log \log n$ のオーダーで発散する。
2. 構造による振る舞いの差異:
   • 多くの「自然な」完全グラフ（GSP、二部グラフの線グラフ、単位区間グラフなど）は、定数（多くは 2）個の比較可能グラフで分割可能である。
   • しかし、区間グラフのより一般的な族（整数端点を持つ区間全体）では、分割数が無限大に発散する。
3. 理論的貢献:
   • 比較可能グラフへの分割数 $p(G)$ と被覆数 $c(G)$ の関係を、完全グラフの文脈で深く掘り下げた。
   • 区間グラフの複雑さを、シフトグラフやダブルシフトグラフの彩色数と関連付けることで、幾何的グラフ理論と順序構造理論を結びつけた。
   • $p(G)=3$ となる最小クラスの探索への道筋を示した（$K_5 \square K_5$ なども候補として言及）。

この研究は、グラフの分割問題における「完全性」と「比較可能性」の関係を解明する重要な一歩であり、特に区間グラフの構造が持つ複雑さの限界を定量的に示した点で意義深い。