ハイパーグラフが50年来の問題の解決策を明らかにする

1850年、数学者トーマス・ペントン・カークマンは、英国国教会の牧師としての主な職務を果たしていないときには、「女子生徒問題」について次のように説明しました。「学校で15人の若い女性が7日間連続して3人並んで歩きます。2人が2人並んで歩かないように、毎日彼女たちを配置する必要があります。」

現代の数学者にとって、この種の問題はハイパーグラフ、つまり3つ以上のグループに集まったノードの集合として想像するのが最も適切です。15人の女子生徒がノードであり、「3人横並び」の各グループは、3つのノードを3本の線、つまり辺で結んだ三角形と考えることができます。

カークマンの問題は、基本的に、すべての女子生徒を繋ぐ三角形の配置が存在するかどうかを問うものですが、2つの三角形が辺を共有しないという制約が追加されています。辺を共有すると、2人の女子生徒が複数回一緒に歩かなければなりません。この制約により、各女子生徒は1週間毎日2人の新しい友達と歩くことになり、すべてのペアが必ず1回ずつ一緒に歩くことになります。

この問題やそれに似た問題は、カークマンが疑問を提起して以来、ほぼ2世紀にわたって数学者を悩ませてきた。1973年、伝説の数学者ポール・エルデシュが同様の問題を提起した。彼は、一見相容れない2つの特性を持つハイパーグラフを構築できるかどうかを問うた。第1に、すべてのノードのペアは、女子生徒の場合のように、ちょうど1つの三角形で接続されていなければならない。この特性により、グラフは三角形で密になる。第2の要件は、三角形を非常に正確な方法で広げることを強制する（具体的には、三角形の小さなグループには、三角形の数より少なくとも3つ多いノードが必要である）。「全体的には密なオブジェクトがあるのに、密な部分がないという、わずかに矛盾した動作が発生する」とカリフォルニア工科大学の数学者デビッド・コンロンは述べた。

今年1月、4人の数学者が50ページに及ぶ複雑な証明で、十分な数のノードがあれば、そのようなハイパーグラフを構築することは常に可能であることを証明しました。「これを実現するために彼らがどれほどの技術的努力を費やしたかは驚くべきものでした」と、バーミンガム大学の数学者アラン・ロー氏は述べています。コンロン氏も同意見で、「本当に素晴らしい成果です」と述べています。

研究チームは、三角形をランダムに選択するプロセスから始め、それを彼らのニーズに合わせて細心の注意を払って設計することで、エルデシュの厳しい要求を満たすシステムを構築した。「証明に必要な複雑な修正の数は、実に驚くほど多い」とコンロン氏は述べた。

彼らの戦略は、個々の三角形からハイパーグラフを注意深く構築することでした。例えば、15人の女子生徒を想像してみてください。それぞれの三角形の間に線を引いてください。

ここでの目標は、これらの線の上に三角形を描き、その三角形が2つの要件を満たすようにすることです。1つ目は、2つの三角形が1つの辺を共有しないことです。（この要件を満たすシステムはシュタイナー三重システムと呼ばれます。）2つ目は、三角形の小さなサブセットごとに、十分な数のノードが使用されるようにすることです。

研究者たちがこれを行った方法は、おそらく類推によって最もよく理解されるでしょう。

エッジで三角形を作る代わりに、レゴブロックで家を建てるとしましょう。最初に作る数棟は、構造補強や精巧な装飾を施した豪華なものになります。完成したら、脇に置いておきましょう。それらは「吸収材」、つまり構造化された備蓄庫のような役割を果たします。

残ったブロックで建物を作り始めましょう。あまり計画性はなくても構いません。レゴが減ってくると、余ったブロックや構造的に不安定な家が出てくるかもしれません。しかし、吸収体建物は過剰に作られ、補強されているので、あちこちからブロックを取り出して使っても、大惨事を招くことはありません。

シュタイナー三重項システムの場合、三角形を作ろうとします。この場合、吸収体は慎重に選ばれた辺の集合です。システムの残りの部分を三角形にまとめることができない場合は、吸収体につながる辺の一部を使用できます。そして、それが終わったら、吸収体自体を三角形に分解します。

吸収は常にうまくいくとは限りません。しかし、数学者たちはこのプロセスを改良し、障害を回避する新しい方法を見つけてきました。例えば、「反復吸収」と呼ばれる強力な変種では、辺を入れ子になった集合の列に分割し、それぞれの辺が次に大きな集合の吸収体として機能するようにします。

「ここ10年ほどで劇的な進歩がありました」とコンロン氏は語った。「ある種の芸術形式ですが、今ではまさに高尚な芸術の域にまで達しています。」

エルデシュの問題は、反復吸収を用いても難解だった。「なぜこの問題が未解決だったのかは、すぐに明らかになりました」と、この問題を解決した4人の研究者の一人、メータブ・ソーニーは述べた。ソーニーと同じくマサチューセッツ工科大学の大学院生であるアシュウィン・サー、ハーバード大学数理科学応用センターのポスドク研究員マイケル・シムキン、そしてオーストリア科学技術研究所の数学者マシュー・クワンも、この問題を解決した。「非常に興味深く、非常に難しい技術的課題がありました」

例えば、反復吸収の他の応用では、シュタイナー三重体系の場合は三角形で、他の問題の場合は他の構造で、集合を覆い終えたら、その集合は処理済みとみなして忘れ去ることができます。しかし、エルデシュの条件により、4人の数学者はそうすることができませんでした。問題のある三角形のクラスターには、複数の吸収集合のノードが容易に含まれてしまう可能性があるからです。

「500ステップ前に選んだ三角形について、どう考えるかを何らかの方法で思い出す必要がある」とソーニー氏は語った。

4人が最終的に辿り着いたのは、三角形を慎重に選べば、あらゆる細かい点まで把握する必要がなくなるということでした。「100個の三角形からなる小さな集合を考え、その集合が正しい確率で選ばれることを保証する方が賢明です」とソーニー氏は言います。

新しい論文の著者たちは、この手法がこの一つの問題を超えて拡張できると楽観視しています。彼らは既に、数独パズルを簡略化したようなラテン方陣に関する問題にこの戦略を適用しています。

クワン氏によると、さらに吸収法が最終的に解決する可能性のある問題がいくつかあるという。「組合せ論、特に設計理論には多くの問題があり、そこではランダムプロセスが非常に強力なツールとなります。」そのような問題の一つであるライザー＝ブルアルディ＝スタイン予想もラテン方陣に関するもので、1960年代から解決が待たれてきた。

チリ大学数理モデリングセンター副所長のマヤ・スタイン氏は、吸収法がこの問題を克服するにはさらなる発展が必要かもしれないが、導入以来、大きな進歩を遂げてきたと述べている。「こうした手法がどのように進化していくのかを見るのは本当に素晴らしいことです。」

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、 シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。