パークとファム、6ページの証明でカーン＝カライ予想を被覆を用いて解決

ランダムグラフは三角形やハミルトン閉路といった性質を突然獲得する。ある確率を下回るとその構造はほとんど決して現れず、それをわずかに上回るとほとんど必ず現れる。正確なしきい値の計算は困難であるため、数学者たちは計算しやすい下界である期待しきい値を用いる。2006年、ジェフ・カーンとギル・カライは、真のしきい値が期待しきい値を対数因子以上に超えることは決してないと予想した。この主張は提唱者自身にとっても強すぎるように思われ、彼らは何年も反例を探し続けたが、しきい値に関する問題をほぼ機械的に解決できることから、中心的な未解決問題となった。

この予想への受け入れられた道筋は、ミシェル・タラグランが提唱した弱い版を経由するもので、期待しきい値を分数的な変種に置き換えるものであった。カーン、ジニョン・パークらは2021年にその版を証明し、2019年のひまわり突破からの技法とスプレッドと呼ばれる概念を取り入れた。カーン自身、その同値性の証明こそが完全な予想への唯一の道だといつも考えていたと述べた。一方、パークとフイ・トゥアン・ファムは別のタラグランの問題に取り組む中で、自分たちのアイデアが見た目以上に強力であることに気づいた。

2022年3月の一晩の不眠のうちに、彼らは直接的な論法を見出した。元の予想に出発点を与えないスプレッドの代わりに、彼らは視点を変え、主張を被覆の言葉で書き換えた。すなわち、ランダム集合が対象構造をまったく含まない可能性が高いならば、その構造の族は期待しきい値への寄与が小さい小さな被覆を持つ、というものである。彼らは少しずつサンプリングしてその被覆を構成し、数え上げの議論で仕上げ、1週間後の2022年3月31日に6ページの論文を公開した。

同僚たちは驚嘆した。カライはそれを際立って単純かつ独創的と呼び、ジェイコブ・フォックスはその証明を魔術的と呼び、デイヴィッド・コンロンは想定されたロードマップを一直線に突き抜けたと述べた。この予想は抽象的な集合について述べられているため、その証明は何百もの具体的なしきい値の命題を一度に解決し、他の人々が再利用できる技法を残す。Quantaは2022年4月25日にこの結果を報じ、パークとファムはしきい値間の差が最悪の場合より小さくなるのはいつかという、より細かい問題にこの手法を適用し始めた。

被覆で再定式化し、それらを直接数え上げる

被覆は元の期待しきい値に直接作用する。対象構造の小さな被覆は重み付き平均への小さな寄与であるため、何も分数的な代替物へ弱める必要がなかった。

主張を対偶で書き換えることで、確率の保証が構成の課題に変わった。すなわち、小さな被覆を構成することであり、それは少しずつサンプリングすることで達成できた。

数え上げの議論が欠けていた一押しを提供したため、証明は分野が唯一の橋と信じていたスプレッドから分数への同値性を必要としなかった。

6ページという長さは、コミュニティ全体がその論法を一度に読み、採用できることを意味し、だからこそ年長の数学者たちはそれを単に正しいだけでなく魔術的と呼んだ。

弱い版への回り道が唯一の道だと誰もが思い込んでいるときは、その前提を疑うべきである。問題の表現方法を変えれば、直接的な攻撃を短くできることがある

2人は2022年3月31日に「A Proof of the Kahn-Kalai Conjecture」をarXivに公開した（2023年4月13日改訂）。Quanta Magazineは2022年4月25日に、ランダム構造の出現に関するエレガントな6ページの証明として報じ、その記事は2022年4月26日にHacker Newsで589ポイントと166件のコメントを集めた。その後、パークとファムはこの手法を、期待しきい値と真のしきい値の間の差が対数の最悪の場合より小さくなるのはいつかという、より細かい問題に適用した。この問題は分野が依然として個別に解明する必要があった。