グラフ理論における非常に大きな小さな飛躍

15 月 XNUMX 日に、興味をそそるセミナーの発表が、組み合わせ論、つまり数え方の数学的研究の分野を騒がせました。 XNUMX 人の共同研究者は、翌日に調整された講演を行う予定でした。 ジュリアン・サハスラブデ 英国ケンブリッジの数学者に演説する一方で、 サイモン・グリフィス リオデジャネイロでニュースを共有し、 マルセロカンポス サンパウロで。 1996 つの講演はすべて、「エルデシュの古い問題に関する最近の進歩」に言及する、同じタイトルと不可解な XNUMX 文の要約を使用していました。 一方、XNUMX 年に亡くなったハンガリーの数学者、パウル エルデシュは、 数百の問題 彼のキャリアの中で、コンビナトリストは、トリオが話そうとしていた特定の問題をすぐに察知しました。 ラムジー数と呼ばれるものについての噂が渦巻いており、これはすべての数学で計算するのが最も難しい量の XNUMX つです。

ラムゼイ数は、膨大な範囲のシステムで避けられないパターンを探すラムゼイ理論と呼ばれる分野全体を生み出しました。

たとえば、すべての整数を多数のバケットに分散しようとしていて、どのバケットにも等間隔の数値のシーケンスを配置しないようにしたいとします。 ラムジー理論は、失敗することを示しています (無限に多くのバケットがない限り)。 この理論は、数えることができるほとんどすべてのものに適用できます。 スイス連邦工科大学チューリッヒ校の数学者であるベニー・スダコフ氏は、「完全に混沌としたシステムを作成することはできない」ということを中心的な教訓としています。

ラムジー数は、特定のパターンが必然的に発生する前に、パラダイム的な例がどれだけ大きくなければならないかを定量化します。 しかし、その中心性にもかかわらず、誰もラムゼー数を計算できませんでした. 最も単純なインスタンス. 彼らができる最善のことは、それが何であるかについて限界（または境界）を見つけることです. それでも、XNUMX世紀近く前にエルデシュと協力者によって最初に確立された上限は、ほとんど動かなかった.

その後、15 月 XNUMX 日のセミナーとその夜遅くに掲載された論文で、研究者はラムジー数の上限を指数関数的に改善したと発表しました。

「私は床に落ちました」と言いました ユヴァル・ウィグダーソン新しい結果について聞いたテルアビブ大学の数学者。 「私は文字通りXNUMX分からXNUMX時間震えていました。」

パーティーライン

ラムゼイ理論は、最も一般的に整数またはグラフについて質問します。 このコンテキストでのグラフは、ノードと呼ばれる点の集まりを指し、エッジと呼ばれる線で接続され、長さやラムゼー数の場合のように色などのプロパティを持つことができます。

完全なグラフは、複雑であると同時に単純でもあります。すべてのノードが他のすべてのノードに接続されています。 ラムゼー数は、特定の構造を持たせるために完全なグラフに含まれる必要があるノードの数を表します。 完全なグラフのエッジには、赤または青の 1930 つの色のいずれかが割り当てられているとします。 また、ノードのグループを同じ色のエッジで接続しないようにエッジに色を付けようとしているとします。 XNUMX 年、フランク ラムジーは、グラフが十分に大きい場合、数学者が単色クリークと呼ぶもの (共通のエッジがすべて赤またはすべて青のいずれかであるノードのグループ) の作成を避けることができなくなることを証明しました。

単色のクリークが強制的に出現する前に、グラフは正確にどのくらいの大きさでなければなりませんか? 答えは、クリークのサイズによって異なります。 Ramsey は、現在 Ramsey 数と呼ばれる数が存在することを示しました。これは、エッジがどのように色付けされていても、特定のサイズの単色クリークが存在する必要があるノードの最小数を表します。

しかし、ラムジー数の大きさを特定するのは困難です。 ラムジー数が存在することを示してから 1935 年後の XNUMX 年に、エルデシュとジョージ セーケレスは、与えられたサイズのクリークに対してラムジー数がどれだけ大きいかについて、新しい、より厳密な上限を提供しました。 しかしそれ以来、数学者はエルデシュとセーケレスの計算をほとんど改善できていません。

これが何を意味するかをより直感的に理解するために、ノードがパーティーのゲストを表す古典的な例を考えてみましょう。 XNUMX 人のゲストの間の縁は、会ったことがある場合は赤、会ったことがない場合は青に色付けします。 好きな派閥の規模を選ぶことができます — パーティーに十分な数の人を招待すると、お互いをよく知っている人々のグループ (言葉の複数の意味での派閥) を招待するか、これまで会ったことがありません。

「グラフでできる最も単純なものは、単色のクリークです」と彼は言いました。 マリア・チュドノフスキー、プリンストン大学の数学者。 「すべての巨大なグラフの中で、それらの大きなグラフを見つけることができるのは、ちょっと驚くべきことです。 まったく不明です。」

最初の数個のラムジー数は比較的簡単に計算できます。 サイズ 2 のクリーク (数学者にとっては R(2)) を不可避的に保持しなければならない最小のグラフのサイズを知りたいとします。 2 つのノードを持つ完全なグラフは、エッジで接続された XNUMX つのノードにすぎず、そのエッジは赤か青のいずれかでなければならないため、R(XNUMX) は XNUMX です。より一般的には、R(k)、またはラムゼー数 kは、グラフがサイズのクリークを含むことを避けることができないノードの最小数です k.

サイズ 3 のクリーク (R(3)) のラムジー数が 6 であることを示すのはそれほど難しくありません (図を参照)。 しかし、R(1955) が 4 に固定されたのは 18 年のことでした。R(5) は不明のままです。少なくとも 43 であり、48 以下です。この問題について、カリフォルニア工科大学のデビッド・コンロン氏は次のように述べています。 43 個のノードを持つ完全なグラフでの色分けの数を考えてみましょう。 「903 個のエッジがあります。 それぞれに 2 つの方法で色を付けることができます」と彼は説明しました。 「だからあなたはXNUMXを得る⁹⁰³、これはまさに天文学的に大きいです。」

クリークのサイズが大きくなるにつれて、ラムゼー数を突き止める作業はますます難しくなります。 Erdős は、数学的に要求の厳しいエイリアンとの全面戦争は、やろうとするよりも簡単だろうと皮肉った。 R(6)を計算する、これは 102 から 165 の間のどこかです。不確実性の範囲は急速に拡大します。 Stanisław Radziszowski によって編集された見積もり、R(10) の最小値は 798、最大値は 23,556 です。 しかし、数学者の目標は、ラムゼー数の 10 をはるかに超えています。彼らは、R(k)、さらに - または特に - とき k 非常に大きいです。

「この問題について少しでも考えたことのない組み合わせ論の専門家を私は知りません」と Wigderson 氏は語った。 「この問題は、本当に特別だと思います。」

裁判所での命令

フランク・ラムゼイは折衷的で輝かしい人物でしたが、26 歳で亡くなりました。 彼が亡くなるわずか数週間前、 ロンドン数学会の議事録 公表 紙 その中で彼はラムジー数を導入しました。 その作品はグラフに関するものではなく、数学的論理の問題に関するものでした。 Ramsey は、特定の条件を満たすステートメントは、少なくとも場合によっては真でなければならないことを証明しました。 それらの条件の XNUMX つは、ステートメントをテストするシナリオの大規模な「宇宙」が存在することでした。この結果への足がかりとして、ラムジーはラムジー数が有限であることを示しました。

XNUMX 年後、Erdős と Szekeres は、 k 4未満^k. そしてそれから12年後、 エルデシュが示した 約 $latex sqrt{2}^k$ より大きいこと。 それを行うために、彼は、ランダムに色付けされたエッジを持つグラフに単色のクリークが含まれる可能性を計算しました。 この「確率的」手法は、グラフ理論に大きな影響を与えました。 また、R(k) 指数関数的に成長する 2 つのゴールポストの間: $latex sqrt{4}^k$ と $latex XNUMX^k$。

数十年が経過するにつれて、多くの数学者がラムゼー数の可能な値の間のギャップを狭めようとしました。 一部は成功した: 1975 年、ジョエル・スペンサー 下限をXNUMX倍に. そして一連の論文 コンロン, アンドリュー・トマソン および アシュウィンサー 上限を押し下げた 4 年までに約 $latex 2^{log(k)^2020}$ 倍になります。しかし、ラムジー数の境界の大きさと比較すると、これらの調整は小さかったです。 対照的に、Erdős と Szekeres の式 R(k）<4^k 指数関数的に改善され、急速に成長します。 k 大きくなります。

「それはちょっとしたかわいい質問のように思えます」と言いました ロブ・モリスリオデジャネイロにあるブラジルの純粋応用数学研究所 IMPA の数学者で、Campos、Griffiths、Sahasrabudhe と共同で新しい結果を作成しました。 「感謝するのは少し微妙です。 しかし、人々は本当にそれを気にかけています。」 これはおそらく控えめな表現です。 「彼らが1936年にそれを証明していたら、人々はこう言ったでしょう、OK、それで大したことは何ですか?」 メンフィス大学でモリスとサハスラブデの博士号顧問を務めていたベラ・ボロバスは、次のように述べています。 「それ以来、これが非常に大きな問題であることが証明されました。長年にわたり、ラムゼイ問題のさまざまな変種について数千の論文が書かれてきたからです。」 として リアナ・イェプレミャン、エモリー大学の数学者は、「ラムゼー数は、組み合わせ論と確率と幾何学の間の架け橋を作成します」と述べました。

ゲーム理論

 2018 年 XNUMX 月、Sahasrabudhe は IMPA の Morris の下で博士研究員を務めました。 XNUMX 人は、近くの教皇庁カトリック大学で教えているグリフィスと新しいプロジェクトを開始したいと考えていました。 コンロンの論文 彼らの注目を集めました。 この論文は、ラムゼー数を指数関数的に改善するための可能な戦略を概説しています。 グリフィス、モリス、サハスラブデはアイデアを試し始めました。

「最初は本当にわくわくしました」と Sahasrabudhe 氏は回想します。 彼らが議論のスケッチを描くのに、約 XNUMX か月しかかからなかった、と彼は言いました。

彼らの計画は、$latex R(k) < 4^k$ という Erdős と Szekeres の元の証明で使用されたアイデアを基に構築することでした。 ラムジー数が最大で $latex 4^k$ であることを証明するには、$latex 4^k$ ノードの完全なグラフでゲームをプレイすることを想像してください。 ゲームにはXNUMX人のプレーヤーがいます。 まず、対戦相手は各エッジを赤または青に色付けします。 k ノード。

対戦相手がカラーリングを終えたら、単色の派閥を探すのがあなたの仕事です。 見つけたら勝ちです。

このゲームに勝つには、簡単な戦略に従うことができます。 ノードを XNUMX つのバケットに分類することを (比喩的に) 考えると役立ちます。 一方のバケットのノードは青色のクリークを形成し、もう一方のバケットのノードは赤色のクリークを形成します。 一部のノードは削除され、二度と聞こえなくなります。 最初は両方のバケットが空で、すべてのノードがいずれかのバケットに入る候補です。

気に入ったノードから始めます。 次に、接続エッジを見てください。 半分以上のエッジが赤い場合は、すべての青いエッジとそれらが接続されているノードを削除します。 次に、元の選択を「赤」のバケツに入れます。 このノードの赤いエッジはすべてまだ健在で、バケツの内側からグラフの残りの部分にしがみついています。 エッジの半分以上が青色の場合、同様に赤色のエッジとノードを削除し、青色のバケツに入れます。

ノードがなくなるまで繰り返します。 (グラフが完成したので、任意の時点で残っているすべてのノードは、いずれかのバケットに配置されるまで、両方のバケットに接続されます。)

終わったら、バケツの中を見てください。 青色の隣接ノードが除去された後にのみノードが赤色のバケットに入ったため、赤色のバケット内のすべてのノードが赤色のエッジで接続され、赤色のクリークが形成されます。 同様に、青いバケツは青いクリークを形成します。 元のグラフに少なくとも $latex 4^k$ ノードがある場合、これらのバケットの XNUMX つに少なくとも k ノード、元のグラフで単色クリークを保証します。

この議論は巧妙で洗練されていますが、実際には XNUMX つしか必要としないにもかかわらず、青と赤の XNUMX つの派閥を構築する必要があります。 常に赤字にする方が効率的だ、とコンロン氏は説明した。 この戦略では、各ステップでノードを選択し、その青いエッジを消去して、赤いバケツに投げ込みます。 赤いバケツはすぐにいっぱいになり、 k 半分の時間でノード。

しかし、あなたの戦略はどのような赤青のカラーリングでも機能する必要があり、赤いエッジがたくさんあるノードを常に見つけることができるかどうかを知ることは困難です. したがって、Conlon の提案に従うと、赤いエッジがほとんど付いていないノードに遭遇するリスクがあります。 これにより、グラフの大部分を一度に削除せざるを得なくなり、ノードがなくなる前にクリークを構築するのに苦労することになります。 Conlon の提案を実行するために、Griffiths、Morris、および Sahasrabudhe は、このリスクが回避可能であることを証明する必要がありました。

オープンブック試験

Griffiths、Morris、および Sahasrabudhe は、ゲームプレイを更新する際に、やや遠回りのルートをたどりました。 赤と青のバケツにノードを放り込んで単色の派閥を直接構築するのではなく、最初に赤い本と呼ばれる構造を構築することに焦点を当てました。

グラフ理論では、本は 2018 つの部分で構成されています。「背骨」と呼ばれる単色のクリークと、「ページ」と呼ばれる XNUMX つ目の別個のノードのクラスターです。 赤い本では、背骨をページにリンクするエッジと同様に、背骨内のノードを接続するすべてのエッジが赤です。 ただし、ページ内のノードを接続するエッジは、任意の色の組み合わせにすることができます。 Conlon は XNUMX 年の論文で、本のページ内に赤いクリークを見つけることができれば、それを背表紙と組み合わせて、より大きな赤いクリークを得ることができると指摘していました。 これにより、大きな赤いクリークの検索を XNUMX つの簡単な検索に分解できます。 まず、赤い本を探します。 次に、本のページで派閥を探します。

グリフィス、モリス、サハスラブデは、赤派の代わりに赤本を構築するように、ゲームに勝つアルゴリズムを調整したいと考えていました。 この計画は、プロジェクト開始からわずか数週間で決着しましたが、実際に機能させるには何年もかかります。 彼らは、すべての赤いエッジを失うという脅威を食い止める必要がありました。

2021 年にプロジェクトに参加したカンポス氏は、「私たちは非常に長い間立ち往生していました。

今年の XNUMX 月、XNUMX 人の数学者は問題の別のバージョンに切り替えることに同意しました。 そのバージョンはより複雑に聞こえますが、簡単であることが判明しました。

ずっと、チームはラムジー数 R(k）、「対角」ラムジー数としても知られています。 サイズ R(k） 含まれている必要があります k ノードはすべて同じ色のエッジで接続されていますが、その色が赤か青かは問題ではありません。 一方、「非対角」ラムジー数 R(k, l) グラフがどのくらいの大きさでなければならないかを測定します。 k ノード、または青いクリーク l ノード。 対角線の問題をハッキングし続ける代わりに、グループは非対角線のバージョンを試すことにしました。 これは啓示的であることが証明されました。

「長い間、押したすべてのドアがボルトで閉まっているか、少なくとも通過するのがかなり難しいように感じていました」とグリフィスは言いました. 「そして、その変化の後、すべてのドアが開いているように感じました. どういうわけか、すべてが機能しているように見えました。」 非対角バージョンでは、特定のプロトコルに従って一連の青いエッジを一度に削除する方法を発見しました。これにより、赤いエッジの密度が増加し、非対角ラムジー数の制限が改善されました。 「密度増分」引数と呼ばれるこの方法は、以前は問題を解決するために使用されていました。 組み合わせ論における他の重要な問題、ラムゼー数問題では使用されていませんでした。

次に、1935 人の数学者は、非対角のラムゼー数の新しい境界を使用して、対角の結果への道を切り開きました。 XNUMX 月の初めまでに、彼らはついにラムゼイ数の限界を指数関数的に引き下げました。これは、数学者が XNUMX 世紀近くにわたって求めてきた成果です。 そして彼らは、エルデシュとセーケレスが XNUMX 年に提示したのと同じ議論を現代化することによってそれを行った。

イプシロン、イプシロン

16月XNUMX日の会談の後、出席者は噂を確認し始めました。 Sahasrabudhe の講演の写真は、電話やプライベート メッセージを通じて広まりました。 漠然としているが示唆に富んだ投稿 数学者ギル・カライのブログで。 Campos、Griffiths、Sahasrabudhe、および Morris は、$latex R(k) < 3.993^k$ を示したと主張しました。 その夜、XNUMX人の作家 彼らの論文をオンラインに投稿した、数学者が自分で新しい証明を確認できるようにします。

「私たちの多くは、本質的に、私たちの生涯でこのような改善が見られるとは予想していなかったと思います. マティヤ・ブシッチ、プリンストン大学および高等研究所の数学者。 「本当に素晴らしい結果だと思います。」

多くの専門家は、指数関数的な障壁が取り除かれれば、さらなる進歩がすぐに続くことを期待しています。 新しい論文の著者は、不必要な詳細で議論を曇らせることを避けるために、意図的にその方法を限界まで押し上げませんでした。 「私にはわからないので、この方法が実際にどこまで進むのか非常に興味があります」と Campos 氏は言います。

「これはまったく独創的で、まったく素晴らしい証拠であり、真のブレークスルーです。 だから今、水門が開かれることを期待しています」とボロバスは言いました。 「私は、3.993年後には改善の可能性についての議論になると確信しています。 3.9 を 3.4 に改善できますか? たぶん3まで？ で、XNUMXは？」

新しいプルーフは 56 ページあり、すべての詳細が組み合わせ論コミュニティによって完全に検証されるまでには数週間かかります。 しかし、同僚は楽観的です。 「この作家グループは、とても真面目な人たちです。 そして、彼らは非常に技術的なことが本当に得意な人たちです」と Wigderson 氏は言います。

協力者に関しては、Griffiths 氏も同意見です。 「素晴らしい人々と仕事ができるのは特権ですよね？ そして、それが私が非常に感謝していることだと思います」と彼は言いました. 「彼らが私に任せていたら、詳細を正しく理解するのにさらに XNUMX 年かかったかもしれません。」