ランダムなネットワークは、決まった密度で塗り分けられなくなる
グラフ(点どうしをつながりで結んだもの)と、色の箱を用意しよう。q色による適正な彩色(proper colouring)とは、つながった2点が決して同じ色にならないように、各点にq色のうち1色を割り当てることだ。つながりが少なければ、それは簡単だ。多くなると、不可能になる。
次に、グラフをランダムにつくる。n個の点を用意し、各ペアを独立に小さな確率で結ぶ。こうすると、1つの点は平均してd個の隣接点をもつ。dが大きくなるにつれて、ランダムグラフは「ほぼ確実にq色で塗り分けられる」状態から「ほぼ確実に塗り分けられない」状態へと移る。切り替わりは正確にはどこで起きるのか。色の数qが3以上の任意の固定値であるときのこの問いが、ケンブリッジ大学のGaia Careniniによる新しい論文の主題である。
揺れ動くかもしれない切り替わり
参考文献に挙げられた1999年の論文で、AchlioptasとFriedgutは、この転移が鋭い(sharp)ことを証明した。どの大きさnについても、ある臨界平均次数d_q(n)が存在し、それをわずかに下回ればグラフはほぼ確実に塗り分けられ、わずかに上回ればほぼ確実に塗り分けられない。切り替わりが起きる幅は、限りなくゼロに縮んでいく。
しかし、そこには抜け穴が残っていた。グラフが大きくなるにつれて臨界値そのものが振動することを妨げるものは、何もなかったのだ。ある大きさのグラフではある場所にあり、より大きなグラフではわずかに別の場所にあって、決して落ち着かない、という可能性である。Achlioptas–Friedgutの収束予想は、そうはならないと述べる。各qについてただ1つの定数d_qが存在し、それより下ではランダムグラフは塗り分けられ、それより上では塗り分けられないというのだ。
物理学者たちの予測
統計物理学は、何が起きているのかについて1つの描像をもっていた。つながりが加わるにつれて、有効な塗り分けはクラスターにまとまっていく。同じクラスター内の塗り分けは互いに似ているが、2つのクラスターどうしは多くの点で異なる。そして凝縮と呼ばれる段階で、ひと握りの大きなクラスターがすべての塗り分けのかなりの割合を占めるようになり、そのあとでようやく、塗り分けの集合が空になる。この構造が、しきい値の近くで数え上げの議論が苦戦する理由を説明する。
色の数が多い場合については、これまでの研究ですでにしきい値が狭い範囲に絞り込まれていた。それは約2q log q − log q − 2 log 2と2q log q − log q − 1のあいだにあり、qが大きくなるとその幅は2 log 2 − 1になる。しかし「狭い」は「決まっている」ではない。そして3色のような少ない色数については、問いは未解決のままだった。
先に取り組まれた双子の問題
塗り分けには双子の問題がある。充足可能性だ。ランダムな論理的制約のリストがすべて成り立つように、変数に真または偽の値を選ぶ問題である。そこでも、鋭いしきい値が存在することは知られていたが、それが落ち着くことは証明されていなかった。論文中で引用されている2026年の報告で、Careniniは、3以上のすべての制約の長さについて、転移の幅が非常に狭いことを示すことで、しきい値が落ち着くことの証明を発表した。新しい論文は、その議論を塗り分けに合わせて作り直したものだ。
一緒に凍りついたペア
証明は一連の帰着によって進む。ランダムなつながりを1本ずつ加えていき、グラフが塗り分けられなくなる瞬間をHとする。Hがランダムグラフごとにほとんど変わらないなら、つまり約n/(log n)²本のつながりの幅に収まるなら、しきい値は落ち着くはずだ。古典的な不等式によって、これは最後の塗り分け可能なグラフについての問いに変わる。そのグラフは、平均して何本の新しいランダムなつながりに耐えられるのか。
ここで鍵となる概念が登場する。凍結ペア(frozen pairs)だ。2つの点が凍結ペアをなすのは、すべての有効な塗り分けがそれらに同じ色を与えるときである。新しいつながりが致命的になるのは、まさにそれがそうしたペアを結ぶときだ。1つの点が特定の1色に凍結されることはありえない。色を入れ替えれば、いつでも別の有効な塗り分けが得られるからだ。強制されるのは、2つの点のあいだの関係である。Careniniは、つながりが加わるにつれてこうした凍結したクラスがどのように成長するかを、1本のつながりや1つの点をまるごと削除して、再び現れる選択肢を調べることで追跡する。その評価から、最後の塗り分け可能なグラフは長くは生き延びられないことがわかる。これによって幅が十分に狭まり、予想が証明される。
まだわからないこと
この定理は、すべてのq ≥ 3についてしきい値d_qが存在すると述べる。しかし、それがどこにあるかは述べない。論文は、3色の場合でさえ、その値を示していない。この論文は単著のプレプリントで、査読を受けていない。論文の最後には、その数学的議論のいずれも大規模言語モデルによって生成されたものではないという短い声明がある。
