15월 XNUMX일, 흥미로운 세미나 발표는 계산의 수학적 연구인 조합론 분야를 통해 소문을 퍼뜨렸습니다. 세 명의 공동 작업자가 다음 날 조율된 대화를 할 계획이었습니다. 줄리안 사하스라부데 영국 케임브리지의 수학자에게 연설하는 동안 사이먼 그리피스 리우데자네이루에서 뉴스를 공유하고 마르셀로 캄포스 상파울루에서. 세 강연 모두 동일한 제목과 "Erdős의 오래된 문제에 대한 최근 진행 상황"을 언급하는 수수께끼 같은 두 문장의 초록을 사용했습니다. 1996년에 사망한 헝가리 수학자 Paul Erdős는 수백 가지 문제 그의 경력 동안 조합가들은 트리오가 이야기할 특정 문제를 재빨리 예측했습니다. 모든 수학에서 계산하기 가장 어려운 양 중 하나인 램지 수(Ramsey number)라는 것에 대한 소문이 돌았습니다.

램지 수는 램지 이론이라는 전체 분야를 탄생시켰습니다. 이 이론은 방대한 범위의 시스템에서 피할 수 없는 패턴을 찾습니다.

예를 들어, 모든 정수를 여러 버킷에 분산시키려고 하고 어떤 버킷에도 균일한 간격의 숫자 시퀀스를 배치하지 않으려고 한다고 가정해 보겠습니다. Ramsey 이론은 실패할 것임을 보여줍니다(버킷이 무한히 많은 경우가 아니면). 이 이론은 당신이 셀 수 있는 대부분의 것에 적용될 수 있습니다. 취리히 스위스 연방공과대학의 수학자 베니 수다코프는 "완전히 혼돈스러운 시스템을 만들 수는 없다"고 말했다.

Ramsey 수는 특정 패턴이 필연적으로 발생하기 전에 패러다임 사례가 얼마나 커야 하는지를 정량화합니다. 그러나 그것의 중심성에도 불구하고 아무도 램지 수를 계산할 수 없었습니다. 가장 간단한 인스턴스. 그들이 할 수 있었던 최선은 그것이 무엇인지에 대한 한계(또는 범위)를 찾는 것입니다. 그럼에도 불구하고 거의 XNUMX년 전에 Erdős와 공동 작업자가 처음 설정한 상한선은 거의 움직이지 않았습니다.

그런 다음 16월 XNUMX일 세미나와 그날 저녁에 게시된 논문에서 연구원들은 Ramsey 수의 상한을 기하급수적으로 개선했다고 발표했습니다.

"나는 바닥에 있었다"고 말했다 유발 위그더슨, 텔아비브 대학의 수학자, 새로운 결과에 대해 듣고. "말 그대로 XNUMX분에서 XNUMX시간 동안 떨고 있었어요."

파티 라인

Ramsey 이론은 가장 일반적으로 정수 또는 그래프에 대한 질문을 합니다. 이 맥락에서 그래프는 가장자리라는 선으로 연결된 노드라고 하는 점의 집합을 의미하며, 길이 또는 램지 수의 경우처럼 색상과 같은 속성을 가질 수 있습니다.

완전한 그래프는 복잡하면서도 단순합니다. 모든 노드는 다른 모든 노드에 연결됩니다. Ramsey 수는 전체 그래프가 특정 구조를 갖도록 강제하기 위해 포함해야 하는 노드 수를 설명합니다. 완전한 그래프의 가장자리에 빨간색 또는 파란색의 두 가지 색상 중 하나가 지정되었다고 가정해 보겠습니다. 그리고 노드 그룹을 같은 색의 가장자리와 연결하지 않는 방식으로 가장자리에 색을 지정하려고 한다고 가정해 보겠습니다. 1930년 Frank Ramsey는 그래프가 충분히 크면 수학자들이 공통 모서리가 모두 빨간색이거나 파란색인 노드 그룹인 단색 파벌(monochromatic clique)이라고 부르는 것을 만드는 것을 피할 수 없게 된다는 것을 증명했습니다.

단색 파벌이 강제로 나타나기 전에 그래프가 정확히 얼마나 커야 합니까? 대답은 파벌의 크기에 달려 있습니다. Ramsey는 가장자리의 색상에 관계없이 주어진 크기의 단색 클릭이 존재해야 하는 노드의 최소 수를 나타내는 현재 Ramsey 수라고 하는 숫자가 있음을 보여주었습니다.

그러나 Ramsey 수의 크기는 고정하기 어렵습니다. Ramsey가 존재한다는 것을 밝힌 지 1935년 후인 XNUMX년에 Erdős와 George Szekeres는 주어진 크기의 파벌에 대해 Ramsey 수가 얼마나 큰지에 대한 새롭고 더 엄격한 상한선을 제공했습니다. 그러나 그 이후로 수학자들은 Erdős와 Szekeres의 계산을 거의 향상시킬 수 없었습니다.

이것이 무엇을 의미하는지 더 잘 이해하려면 노드가 파티의 손님을 나타내는 고전적인 예를 고려하십시오. 이전에 만난 적이 있으면 두 손님 사이의 가장자리를 빨간색으로, 만난 적이 없으면 파란색으로 칠하십시오. 원하는 파벌 크기를 선택할 수 있습니다. 파티에 충분한 사람들을 초대하면 서로를 모두 아는 사람들의 그룹(단어의 여러 의미에서 파벌)을 초대하거나 전에 만난 적이 없습니다.

"그래프에서 가질 수 있는 가장 단순한 것은 단색 파벌입니다."라고 말했습니다. 마리아 추드 노프 스키, 프린스턴 대학의 수학자. “모든 거대한 그래프에서 그 중 큰 그래프를 찾을 수 있다는 것은 놀라운 일입니다. 완전히 명확하지 않습니다.”

처음 몇 개의 Ramsey 수는 비교적 계산이 간단합니다. 어쩔 수 없이 크기 2 또는 수학자에게 R(2)의 파벌을 유지해야 하는 가장 작은 그래프의 크기를 알고 싶다고 가정해 보겠습니다. 두 개의 노드가 있는 완전한 그래프는 가장자리로 연결된 두 개의 노드일 뿐이고 해당 가장자리는 빨간색 또는 파란색이어야 하므로 R(2)는 XNUMX입니다. 보다 일반적으로 R(k), 또는 램지 수 k, 그래프가 크기의 파벌을 포함하는 것을 피할 수 없는 최소 노드 수입니다. k.

크기가 3인 파벌에 대한 Ramsey 수 또는 R(3)이 6임을 보여주는 것은 그리 어렵지 않습니다(그래픽 참조). 그러나 1955년이 되어서야 R(4)가 18로 고정되었습니다. R(5)는 아직 알려지지 않았습니다. 최소 43에서 48보다 크지 않습니다. 이 숫자는 작지만 가능한 모든 색상을 선별하는 것은 불가능합니다. "라고 California Institute of Technology의 David Conlon은 말했습니다. 43개의 노드가 있는 완전한 그래프의 색상 수를 고려하십시오. “903개의 모서리가 있습니다. 각각 두 가지 방식으로 색상을 지정할 수 있습니다.”라고 그는 설명했습니다. "그래서 당신은 2를 얻습니다⁹⁰³, 천문학적으로 큰 것입니다.”

파벌의 규모가 커질수록 램지어의 숫자를 확정하는 작업은 더욱 어려워질 뿐입니다. Erdős는 수학적으로 까다로운 외계인과 전면전을 벌이는 것이 R(6) 알아내기, 102에서 165 사이 어딘가에 있습니다. 불확실성의 범위는 빠르게 증가합니다. Stanisław Radziszowski가 집계한 추정치, R(10)은 798만큼 작고 23,556만큼 클 수 있습니다. 그러나 수학자들의 목표는 램지 수 10을 훨씬 넘어섭니다. 그들은 R(k), 심지어 — 또는 특히 — 언제 k 매우 큽니다.

Wigderson은 "나는 이 문제에 대해 조금이라도 생각하지 않은 조합론의 사람을 알지 못합니다."라고 말했습니다. "이 문제는 정말 특별하다고 생각합니다."

법원의 명령

프랭크 램지는 26세에 세상을 떠난 절충적이고 뛰어난 인물이었습니다. 그가 죽기 몇 주 전, London Mathematical Society의 회보 출판 종이 그는 Ramsey 번호를 소개했습니다. 그 작업은 그래프에 관한 것이 아니라 수학적 논리의 문제에 관한 것입니다. Ramsey는 특정 조건을 만족하는 진술이 적어도 한동안은 참이어야 한다는 것을 증명했습니다. 이러한 조건 중 하나는 진술을 테스트할 시나리오의 큰 "우주"가 있다는 것입니다. 이 결과의 디딤돌로 Ramsey는 Ramsey 수가 유한함을 보여주었습니다.

XNUMX년 후 Erdős와 Szekeres는 Ramsey 수가 다음과 같다는 것을 보여주었습니다. k 4 미만^k. 그리고 그로부터 12년 후, 에르되시가 보여주었다 $latex sqrt{2}^k$보다 큽니다. 이를 위해 그는 무작위로 색상이 지정된 가장자리가 있는 그래프에 단색 파벌이 포함될 가능성을 계산했습니다. 이 "확률론적" 기법은 그래프 이론에 막대한 영향을 미쳤습니다. 또한 R(k) 기하급수적으로 성장하는 두 골대 사이: $latex sqrt{2}^k$ 및 $latex 4^k$.

수십 년이 흐르면서 수많은 수학자들이 램지 수의 가능한 값 사이의 간격을 좁히려고 시도했습니다. 일부 성공: 1975년 Joel Spencer 하한선 두배. 그리고 일련의 논문 콘론, 앤드류 토마슨 과 애쉬윈 사 상한선을 낮췄다 4년까지 약 $latex 2^{log(k)^2020}$의 인수로 증가합니다. 그러나 Ramsey 수의 경계 크기와 비교할 때 이러한 조정은 작았습니다. 대조적으로, Erdős 및 Szekeres의 공식 R(k) <4^k 기하급수적으로 향상되어 빠르게 성장할 것입니다. k 더 커집니다.

"그냥 귀엽고 작은 질문인 것 같다"고 말했다. 롭 모리스Campos, Griffiths 및 Sahasrabudhe와 함께 새로운 결과를 공동 저술한 리우데자네이루에 있는 브라질 순수 및 응용 수학 연구소 IMPA의 수학자. “감사하기에는 약간 미묘합니다. 하지만 사람들은 정말 그것에 관심이 있습니다.” 이것은 아마도 과소 평가 일 것입니다. "그들이 1936년에 그것을 증명했다면 사람들은 이렇게 말했을 것입니다. 멤피스 대학교에서 Morris와 Sahasrabudhe의 박사 고문이었던 Béla Bollobás는 말했습니다. "그 이후로 Ramsey 문제의 다양한 변형에 대해 수년에 걸쳐 수천 건의 논문이 작성되었기 때문에 이것이 매우 큰 문제라는 것이 입증되었습니다." 처럼 리아나 예프레미안에모리 대학의 수학자인 에모리 박사는 "램지 수는 조합론과 확률 및 기하학 사이의 다리를 만듭니다."라고 말했습니다.

게임 이론

 2018년 XNUMX월, Sahasrabudhe는 IMPA에서 Morris의 박사후 연구원이었습니다. 두 사람은 인근 교황청 가톨릭 대학교에서 가르치는 그리피스와 함께 새로운 프로젝트를 시작하기를 바랐습니다. Conlon의 논문 그들의 관심을 끌었습니다. 이 논문은 Ramsey 수를 기하급수적으로 개선할 수 있는 가능한 전략을 설명했습니다. Griffiths, Morris 및 Sahasrabudhe는 아이디어를 가지고 놀기 시작했습니다.

Sahasrabudhe는 “처음에는 정말 흥미진진했습니다. 그들의 주장을 스케치하는 데 약 한 달 밖에 걸리지 않았다고 그는 말했습니다.

그들의 계획은 $latex R(k) < 4^k$라는 Erdős와 Szekeres의 원래 증명에 사용된 아이디어를 기반으로 구축하는 것이었습니다. Ramsey 수가 최대 $latex 4^k$임을 증명하기 위해 $latex 4^k$ 노드가 있는 완전한 그래프에서 게임을 한다고 상상해 보십시오. 게임에는 두 명의 플레이어가 있습니다. 첫째, 상대방은 각 가장자리를 빨간색 또는 파란색으로 색칠하여 단색 파벌을 만들지 않도록 가장자리를 색칠합니다. k 노드.

상대방이 색칠을 마치면 단색 파벌을 찾는 것이 당신의 임무입니다. 하나를 찾으면 이깁니다.

이 게임에서 이기려면 간단한 전략을 따를 수 있습니다. 노드를 두 개의 버킷으로 분류하는 것에 대해 (은유적으로) 생각하는 데 도움이 됩니다. 한 버킷의 노드는 파란색 파벌을 형성하고 다른 버킷의 노드는 빨간색 파벌을 형성합니다. 일부 노드는 삭제되어 다시는 들리지 않습니다. 처음에는 두 버킷이 모두 비어 있고 모든 노드는 어느 한 버킷에 들어갈 후보입니다.

마음에 드는 노드로 시작하세요. 그런 다음 연결 가장자리를 살펴보십시오. 에지의 절반 이상이 빨간색이면 모든 파란색 에지와 연결된 노드를 삭제합니다. 그런 다음 원래 선택 항목을 "빨간색" 버킷에 넣습니다. 이 노드의 모든 빨간색 가장자리는 여전히 살아 있고 양동이 내부에서 그래프의 나머지 부분에 달라붙어 있습니다. 가장자리의 절반 이상이 파란색인 경우 유사하게 빨간색 가장자리와 노드를 삭제하고 파란색 버킷에 넣습니다.

남은 노드가 없을 때까지 반복합니다. (그래프가 완성되었으므로 어느 시점에서나 남아 있는 모든 노드는 버킷 중 하나에 배치될 때까지 두 버킷에 연결됩니다.)

완료되면 양동이 내부를 살펴보십시오. 노드는 파란색 이웃이 제거된 후에만 빨간색 버킷으로 이동했기 때문에 빨간색 버킷의 모든 노드는 빨간색 가장자리로 연결되어 빨간색 파벌을 형성합니다. 마찬가지로 파란색 양동이는 파란색 파벌을 형성합니다. 원본 그래프에 $latex 4^k$ 노드 이상이 있는 경우 이러한 버킷 중 하나에 최소한 $latex XNUMX^k$ 노드가 있어야 함을 증명할 수 있습니다. k 노드, 원본 그래프에서 단색 클릭을 보장합니다.

이 주장은 영리하고 우아하지만 실제로는 하나만 필요함에도 불구하고 파란색과 빨간색의 두 파벌을 구축하게 합니다. 항상 빨간색으로 표시하는 것이 더 효율적일 것이라고 Conlon은 설명했습니다. 이 전략에서는 각 단계에서 노드를 선택하고 파란색 가장자리를 지우고 빨간색 버킷에 던집니다. 그러면 빨간색 양동이가 빠르게 채워지고 빨간색 파벌을 모을 것입니다. k 절반의 시간에 노드.

그러나 전략은 모든 빨강-파랑 색상에 대해 작동해야 하며 빨간색 가장자리가 많은 노드를 항상 찾을 수 있는지 여부를 알기 어렵습니다. 따라서 Conlon의 제안을 따르면 빨간색 가장자리가 거의 연결되지 않은 노드에 도달할 위험이 있습니다. 그러면 그래프의 상당 부분을 한 번에 삭제해야 하므로 노드가 부족해지기 전에 파벌을 구축하기 위해 허둥지둥하게 됩니다. Conlon의 제안을 실행하기 위해 Griffiths, Morris 및 Sahasrabudhe는 이 위험을 피할 수 있음을 증명해야 했습니다.

오픈북 시험

게임 플레이를 업데이트하면서 Griffiths, Morris 및 Sahasrabudhe는 약간 더 우회적인 경로를 따랐습니다. 빨간색과 파란색 버킷에 노드를 던져 직접 단색 파벌을 구축하는 대신 먼저 빨간색 책이라는 구조를 구축하는 데 집중했습니다.

그래프 이론에서 책은 두 부분으로 구성됩니다. "척추"라고 하는 단색 파벌과 "페이지"라고 하는 두 번째 별개의 노드 클러스터가 있습니다. 빨간색 책에서 책등 내의 노드를 연결하는 모든 가장자리는 책등을 페이지에 연결하는 가장자리와 마찬가지로 빨간색입니다. 그러나 페이지 내에서 노드를 연결하는 가장자리는 색상 조합이 될 수 있습니다. Conlon은 2018년 논문에서 책의 페이지 내에서 빨간색 파벌을 찾을 수 있다면 책등과 결합하여 더 큰 빨간색 파벌을 얻을 수 있다고 언급했습니다. 이를 통해 큰 빨간색 파벌에 대한 검색을 두 개의 더 쉬운 검색으로 분해할 수 있습니다. 먼저 빨간 책을 찾으십시오. 그런 다음 책 페이지에서 파벌을 찾으십시오.

Griffiths, Morris 및 Sahasrabudhe는 게임 승리 알고리즘을 조정하여 빨간색 파벌 대신 빨간색 책을 만들려고 했습니다. 그들은 프로젝트 시작 몇 주 만에 이 계획을 정했지만 제대로 작동하려면 몇 년이 걸릴 것입니다. 그들은 여전히 ​​빨간 가장자리를 모두 잃을 위험을 피해야했습니다.

2021년에 프로젝트에 합류한 Campos는 "우리는 아주 오랫동안 갇혀 있었습니다."라고 말했습니다.

올해 XNUMX월, 네 명의 수학자들은 문제의 다른 버전으로 전환하기로 합의했습니다. 그 버전은 더 복잡하게 들리지만 더 쉬운 것으로 판명되었습니다.

계속해서 팀은 Ramsey 번호 R(k), "대각선" Ramsey 수라고도 합니다. 크기 R(k) 포함해야 함 k 노드는 모두 같은 색상의 가장자리로 연결되어 있지만 해당 색상이 빨간색인지 파란색인지는 중요하지 않습니다. 반면에 "비대각선" Ramsey 수 R(k, l)는 그래프가 k 노드 또는 파란색 파벌 l 노드. 대각선 문제를 계속 해킹하는 대신, 그룹은 비대각선 버전을 시도하기로 결정했습니다. 이것은 계시적인 것으로 판명되었습니다.

Griffiths는 "오랫동안 당신이 밀어 넣은 모든 문이 볼트로 잠겨 있거나 적어도 통과하기가 꽤 어려운 것처럼 느껴졌습니다."라고 말했습니다. “그리고 그 변화 후에 모든 문이 열린 것처럼 느껴졌습니다. 어쨌든 모든 것이 제대로 작동하는 것 같았습니다.” 비대각선 버전에서 그들은 특정 프로토콜에 따라 한 번에 많은 파란색 가장자리를 삭제하는 방법을 찾았습니다. 그러면 빨간색 가장자리의 밀도가 증가하고 비대각선 Ramsey 수에 대한 경계가 개선되었습니다. "밀도 증분" 인수라고 하는 이 방법은 이전에 다음을 해결하는 데 사용되었습니다. 조합론의 다른 중요한 문제, 그러나 Ramsey 수 문제에는 사용되지 않았습니다.

그런 다음 네 명의 수학자들은 대각선을 벗어난 Ramsey 수에 대한 새로운 범위를 사용하여 대각선 결과를 위한 길을 닦았습니다. 1935월 초에 그들은 마침내 Ramsey 수의 한계를 기하급수적 요인으로 낮췄습니다. 수학자들이 거의 XNUMX세기 동안 추구해 온 성과였습니다. 그리고 그들은 Erdős와 Szekeres가 XNUMX년에 내놓은 것과 같은 주장을 현대화함으로써 그것을 했습니다.

엡실론, 엡실론

16월 XNUMX일 회담 이후 참석자들은 루머를 확인하기 시작했다. Sahasrabudhe의 연설 사진은 전화 통화와 개인 메시지를 통해 유포되었습니다. 모호하지만 암시적인 게시물 수학자 Gil Kalai의 블로그에서. Campos, Griffiths, Sahasrabudhe 및 Morris는 $latex R(k) < 3.993^k$를 보여주었다고 주장했습니다. 그날 밤 네 명의 작가는 자신의 논문을 온라인에 게시, 수학자들이 스스로 새로운 증명을 볼 수 있도록 합니다.

"나는 우리 중 많은 사람들이 본질적으로 우리 삶에서 그러한 개선을 기대하지 않았다고 생각합니다."라고 말했습니다. 마티야 부치치, Princeton University 및 Institute for Advanced Study의 수학자. “완전히 놀라운 결과라고 생각합니다.”

많은 전문가들은 기하급수적인 장벽이 무너지면서 더 많은 진전이 빠르게 뒤따를 것으로 기대하고 있습니다. 새 논문의 저자는 불필요한 세부 사항으로 주장이 흐려지는 것을 피하기 위해 의도적으로 자신의 방법을 한계까지 밀어붙이지 않았습니다. Campos는 "나는 전혀 모르기 때문에 방법이 실제로 얼마나 멀리 갈 수 있는지에 매우 관심이 있습니다."라고 말했습니다.

“완전히 독창적이고 절대적으로 놀라운 증거이며 진정한 돌파구입니다. 이제 수문이 열릴 것으로 기대합니다.”라고 Bollobás는 말했습니다. “저는 3.993년 후에 가능한 개선에 대한 논쟁이 있을 것이라고 확신합니다. 3.9을 3.4로 향상시킬 수 있습니까? 아마 3? 그리고 XNUMX은요?”

새로운 증명은 56페이지에 이르며 조합 커뮤니티에서 모든 세부 사항을 완전히 확인하는 데 몇 주가 걸릴 것입니다. 그러나 동료들은 낙관적입니다. “이 저자 그룹은 매우 진지한 사람들입니다. 그리고 그들은 매우 기술적인 일에 정말 정말 능숙한 사람들입니다.”라고 Wigderson이 말했습니다.

공동 작업자에 관해서는 Griffiths도 동의합니다. “훌륭한 사람들과 함께 일하는 것은 특권이죠, 그렇죠? 그리고 그것이 내가 매우 감사하게 생각하는 것입니다.”라고 그는 말했습니다. "만약 그들이 나에게 그것을 맡겼다면, 나는 세부 사항을 제대로 이해하는 데 또 XNUMX년이 걸렸을 것입니다."