올해까지 콴타 수학적 패턴 생성을 피하는 방법에 대한 연구인 Ramsey 이론의 세 가지 주요 발전을 연대순으로 기록했습니다. 그만큼 첫 번째 결과 {2, 4, 6} 또는 {21, 31, 41}과 같이 균일한 간격의 숫자 XNUMX개를 포함하지 않고 정수 집합이 얼마나 클 수 있는지에 대한 새로운 상한을 설정합니다. 그만큼 초 및 제삼 마찬가지로 모두 연결되어 있거나 서로 격리되어 있는 포인트 클러스터 없이 네트워크 크기에 새로운 경계를 설정합니다.

증명은 관련된 숫자가 무한히 커질 때 발생하는 일을 다룹니다. 역설적이게도 이것은 때때로 성가신 실제 수량을 처리하는 것보다 쉬울 수 있습니다.

예를 들어 분모가 매우 큰 분수에 대한 두 가지 질문을 생각해 보십시오. 예를 들어 1/42503312127361의 소수점 확장이 무엇인지 물어볼 수 있습니다. 또는 분모가 커짐에 따라 이 숫자가 1에 가까워지는지 물어볼 수 있습니다. 첫 번째 질문은 실제 수량에 대한 구체적인 질문이며 수량 XNUMX/n "점근적으로" 다음과 같이 변경됩니다. n 자랍니다. (점점 0에 가까워집니다.)

"이것은 모든 Ramsey 이론을 괴롭히는 문제입니다."라고 말했습니다. 윌리엄 가사크, 메릴랜드 대학의 컴퓨터 과학자. "Ramsey 이론은 점근적으로 매우 좋은 결과를 얻는 것으로 알려져 있습니다." 그러나 무한대보다 작은 숫자를 분석하려면 완전히 다른 수학적 도구 상자가 필요합니다.

Gasarch는 무차별 대입으로 해결하기에는 너무 큰 유한 숫자와 관련된 Ramsey 이론의 질문을 연구했습니다. 한 프로젝트에서 그는 올해의 첫 번째 돌파구인 유한 버전의 XNUMX월 논문을 맡았습니다. 잰더 켈리, University of Illinois, Urbana-Champaign 대학원생, 라구 메카 캘리포니아 대학교 로스앤젤레스 캠퍼스. Kelley와 Meka는 1과 N XNUMX학기 진행 또는 균일한 간격의 숫자 패턴을 피하면서 세트에 넣을 수 있습니다.

Kelley와 Meka의 결과는 N 상대적으로 작기 때문에 이 경우에 특히 유용한 범위를 제공하지 않습니다. 매우 작은 값의 경우 N, 매우 간단한 방법을 고수하는 것이 좋습니다. 만약에 N 예를 들어 5는 1과 XNUMX 사이의 가능한 모든 숫자 집합을 살펴보십시오. N, 진행이 없는 가장 큰 {1, 2, 4, 5}를 선택합니다.

그러나 서로 다른 가능한 답변의 수가 매우 빠르게 증가하고 있으며 이러한 간단한 전략을 사용하기가 너무 어렵습니다. 1에서 1 사이의 숫자로 구성된 20만 개 이상의 세트가 있습니다.⁶⁰ 1에서 200 사이의 숫자를 사용합니다. 이러한 경우에 가장 무진보 세트를 찾는 데는 효율성 개선 전략이 있더라도 엄청난 양의 컴퓨팅 성능이 필요합니다. "사물에서 많은 성능을 짜낼 수 있어야 합니다."라고 말했습니다. 제임스 글렌, Yale University의 컴퓨터 과학자. 2008년에 Gasarch, Glenn 및 클라이드 크루스칼 메릴랜드 대학교의 프로그램을 썼다 진행이 없는 가장 큰 세트를 찾기 위해 N (이전 작업에서는 187개와 150개에 대한 답을 얻었습니다.) 많은 요령에도 불구하고 프로그램을 완료하는 데 몇 달이 걸렸다고 Glenn은 말했습니다.

계산 부하를 줄이기 위해 팀은 프로그램이 막다른 검색을 수행하지 못하도록 하는 간단한 테스트를 사용하고 세트를 개별적으로 분석하는 더 작은 부분으로 분할했습니다.

Gasarch, Glenn 및 Kruskal도 몇 가지 다른 전략을 시도했습니다. 유망한 아이디어 중 하나는 임의성에 의존했습니다. 진행 없는 세트를 만드는 간단한 방법은 세트에 1을 넣은 다음 항상 산술 진행을 생성하지 않는 다음 숫자를 추가하는 것입니다. 숫자 10에 도달할 때까지 이 절차를 수행하면 {1, 2, 4, 5, 10} 집합을 얻게 됩니다. 그러나 이것은 일반적으로 최선의 전략이 아니라는 것이 밝혀졌습니다. "1부터 시작하지 않으면 어떻게 될까요?" 가사르가 말했다. "임의의 장소에서 시작하면 실제로 더 잘할 수 있습니다." 연구원들은 무작위성이 왜 그렇게 유용한지 전혀 모른다고 그는 덧붙였다.

두 개의 다른 새로운 Ramsey 이론 결과의 유한 버전을 계산하는 것은 진행이 없는 세트의 크기를 결정하는 것보다 훨씬 더 까다롭습니다. 이러한 결과는 에지라고 하는 선으로 연결된 노드로 구성된 수학적 네트워크(그래프라고 함)에 관한 것입니다. 램지 넘버 r(s, t)는 다음 그룹 중 하나를 포함하는 것을 피할 수 없게 되기 전에 그래프가 가져야 하는 최소 노드 수입니다. s 연결된 노드 또는 t 연결이 끊어진 것. Ramsey 수는 심지어 r(5, 5)는 알 수 없습니다. 43에서 48 사이입니다.

1981년에 브렌든 맥케이현재 호주 국립 대학교의 컴퓨터 과학자인 는 램지 수를 더 쉽게 계산할 수 있도록 고안된 nauty라는 소프트웨어 프로그램을 작성했습니다. Nauty는 연구원들이 서로 뒤집히거나 회전된 버전인 두 개의 그래프를 확인하는 데 시간을 낭비하지 않도록 합니다. “누군가 그 지역에 있고 nauty를 사용하지 않으면 게임이 종료됩니다. 사용해야 한다"고 말했다. 스타니스와프 라지조프스키, Rochester Institute of Technology의 수학자. 그러나 관련된 계산의 양은 거의 이해할 수 없습니다. 2013년에 Radziszowski와 얀 괴에지뵈르 증명했다 r(3, 10)은 최대 42입니다.. 벨기에 KU Leuven University의 컴퓨터 과학자인 Goedgebeur는 "제 생각에 거의 50 CPU년이 걸렸습니다."라고 말했습니다.

정확한 Ramsey 수를 계산할 수 없는 경우 예제를 사용하여 값을 좁힐 수 있습니다. 모두 연결된 45개의 노드가 없고 모두 연결이 끊긴 XNUMX개의 노드가 없는 XNUMX노드 그래프를 찾았다면 다음을 증명할 것입니다. r(5, 5)는 45보다 큽니다. Ramsey 수를 연구하는 수학자들은 Ramsey 그래프라고 하는 이러한 예를 찾는 것이 간단할 것이라고 생각했습니다. Radziszowski는 말했습니다. 하지만 그렇지 않았습니다. "멋지고 멋진 수학적 구성이 가능한 최상의 구성을 제공할 것이라는 기대가 있었고 우리는 단지 더 많은 사람들이 작업해야 합니다."라고 그는 말했습니다. "제 느낌은 점점 더 혼란스러워지고 있습니다."

임의성은 이해의 장애물이자 유용한 도구입니다. 제프리 엑수인디애나 주립 대학의 컴퓨터 과학자인 는 Ramsey 그래프를 생성하기 위해 임의 방법을 개선하는 데 수년을 보냈습니다. ~ 안에 2015 논문 수십 개의 새롭고 기록적인 Ramsey 그래프를 발표하면서 Exoo와 Milos Tatarevic은 무작위 그래프를 생성한 다음 Ramsey 그래프를 찾을 때까지 원하지 않는 클러스터의 수를 줄이는 가장자리를 삭제하거나 추가하여 점진적으로 그래프를 조정했습니다. Radziszowski는 Exoo의 기술은 무엇보다 예술이라고 말했습니다. 때로는 여러 방법을 결합하거나 어떤 종류의 그래프로 시작할지 판단해야 합니다. Radziszowski는 "많은 사람들이 시도하지만 할 수 없습니다."라고 말했습니다.

Ramsey 그래프를 생성하기 위해 개발된 기술은 언젠가는 더 광범위하게 유용할 것이라고 말했습니다. 에서 일하는 화합물을 나타내는 그래프와 같은 다른 종류의 그래프를 생성합니다. "이러한 기술을 이전하고 조정하여 다른 종류의 그래프를 보다 효율적으로 생성하는 데 도움이 될 가능성은 거의 없습니다."라고 그는 이메일에 썼습니다.

그러나 Radziszowski에게 작은 Ramsey 수를 연구하는 이유는 훨씬 간단합니다. “열렸기 때문에 답이 무엇인지 아무도 모르기 때문입니다.”라고 그는 말했습니다. “우리가 손으로 하는 사소한 경우; 조금 더 크면 컴퓨터가 필요하고 조금 더 크면 컴퓨터로도 충분하지 않습니다. 그래서 도전이 생깁니다.”