On Alternating 6-Cycles in Edge-Coloured Graphs

想像してみてください。あなたは、全員が赤または青のシャツを着ている、大規模なパーティーにいます。さらに、このパーティーにいるすべてのペアが握手を交わしており、その一つひとつの握手が「赤の握手」か「青の握手」のいずれかであると想像してください。この混沌とした、色彩豊かなつながりの網は、数学者たちが「エッジ彩色グラフ（edge-colored graph）」と呼ぶものです。ここで問いとなるのは、もしこの網の中に特定のパターン、例えば、6人の人々による円（サイクル）で、握手の色が赤・青・赤・青・赤・青と交互に変わるものを見つけようとした場合、そのようなパターンを最大でいくつ見つけることができるか、ということです。

これは単なるパーティーのゲームではありません。これは「極値組合せ論（extremal combinatorics）」と呼ばれる数学の一分野です。それは、大きなシステムにおけるパターンの絶対的な限界を探求する学問です。それは例えば、「壁を築くためにレンガを配置する最も効率的な方法は何か？」や「紙を最大で何回折り畳めるか？」と問うようなものです。この場合、「レンガ」は握手であり、「壁」はグラフの構造です。数学者がこれを重視するのは、これらの限界を理解することが、コンピュータネットワークから社会構造に至るまで、あらゆるものにおける秩序と混沌がどのように相互作用しているかを理解する助けになるからです。時には、最も「ランダム」に見える配置こそが、特定のパターンを最も多く生み出すことがあり、また、非常に特定の、組織化された構造が勝者となることもあります。どちらがそうなのかを見極めることは、宇宙的なパズルを解くようなものです。

この短くも鋭いノートの中で、二人の数学者、ハオ・チェン（Hao Chen）とジョナサン・A・ノエル（Jonathan A. Noel）は、このパズルの特定の部分に取り組んでいます。彼らは、すべての握手が赤または青にランダムに彩色されている巨大で完全接続されたパーティーにおいて、そのランダムな混沌が、それらの交互に変化する6人組の円（alternating 6-cyclesと呼ばれる）を最大化するための最善の方法であるかどうかを知りたかったのです。

長い間、これは未解決の問題でした。彼らは他の形状（交互のパスや、長さが4の倍数であるサイクルなど）については答えを知っていましたが、6周期（6-cycle）の場合は、手強い謎のままでした。著者らは、「フラグ・代数（flag algebras）」と呼ばれる強力な数学的ツールを用いて、このコードを解読しました。フラグ代数を、数学者がグラフの極めて小さな断片にズームインし、その中のパターンを数え、その小さなカウントを用いて、巨大なグラフ全体がどのような姿をしているかを推論することを可能にする、超強力な顕微鏡だと考えてください。それは、材料のわずかなスプーン一杯分を味わい、その比率に基づいて巨大なスープの味を推測しようとするようなものです。

この論文は決定的な結果を証明しています：これら交互の6周期の最大数は、色が完全にランダムに選ばれたときに実際に達成されます。

ここが結論です：もしあなたが巨大なクリーク（全員が全員とつながっているグループ）を持ち、すべての握手の色を決めるためにコインを投げて赤か青かを決めるようにランダムに彩色すれば、あなたは他のいかなる巧妙で計画的な彩色スキームよりも多くの交互の6周期を得ることになります。このようなランダムグラフにおけるこれらのサイクルの密度は、正確に $(1/2)^6$、つまり $1/64$ です。

著者らは単に推測したのではなく、厳密な証明を提供しました。彼らは、小さな6人のグループ（具体的には、二部グラフである $K_{3,3}$）が彩色されるあらゆる方法を調べることで、問題を分解しました。この小さなグループの辺を赤と青で彩色する方法は512通りあります。回転や反転を無視して、これら512通りの可能性を26のユニークな「形」にグループ化することで、彼らは巨大な方程式系を構築することができました。

彼らは、「フラグ（flags）」と呼ばれる、2つの特別な「ルート（根）」を持つ小さなグラフを用いた巧妙なトリックを導入しました。これらのフラグがどのように組み合わさるかを分析することで、彼らは巨大な8×8の数値行列を構築しました。この行列は数学的なセーフティネットとして機能します。それは「正定値（positive semi-definite）」であり、これは、あなたが巨大なグラフの中でどのように色を配置しようとも、数学が交互の6周期の数が一定の天井を超えないように強制することを意味します。計算を行った結果、その天井は正確に $(1/2)^6$ であることが分かりました。

したがって、この論文は、バシット（Basit）とその仲間たちによって提起されたより大きな問題の最初のケースを解決しました。これは、この特定の形状については、自然界は秩序よりもランダム性を好むことを裏付けています。著者らはまた、彼らの手法は今回のケースには非常に優れているものの、より大きく複雑な形状に対しては、パターンの数が組合せ爆発的に増大するため、重すぎる可能性があることも指摘しています。しかし、彼らの研究は、他の同様の形状（長さが10、14などのサイクル）についても、ランダムな彩色がチャンピオンである可能性が高いことを強く示唆しています。

興味深いことに、この論文は、別の研究グループが同様の手法を用いて独立して同じ結論に達したことに言及しています。しかし、チェンとノエルにとって、その道のりは、赤と青の海のような混沌の中でも、最も「ランダム」な配置が、これらの特定のループを作り出すために最も生産的であることを示すことでした。それは、時として、パターンを構築する最善の方法は、ただダイスを振らせることであるということを思い出させてくれます。