100년 만에 수학 난제 ‘렘지 이론’ 새로운 해법 발견

거의 100년 만에 수학자들이 수학 난제 중 하나의 해법을 찾았다.

미국 캘리포니아 대학교 샌디에고(UC San Diego) 연구원 Jacques Verstraete와 Sam Mattheus는 수십 년 동안 수학계를 난처하게 만들었던 오랜 램지 이론(Ramsey theory) 문제인 r(4,t)에 대한 답을 찾았다.

Ramsey의 문제는 무엇일까?

수학적 용어로 그래프는 일련의 점과 해당 점 사이의 선이다. Ramsey 이론에 따르면 그래프가 충분히 크면 그래프 내에서 일종의 순서, 즉 사이에 선이 없는 점 집합이나 사이에 가능한 모든 선이 있는 점 집합(“cliques”)을 찾을 수 있다고 한다. 이는 r(s,t)로 작성된다. 여기서 s는 선이 있는 점이고 t는 선이 없는 점이다.

그래프 이론을 다루지 않는 사람들에게 가장 잘 알려진 Ramsey 문제인 r(3,3)은 때때로 “친구와 낯선 사람에 대한 정리”라고 불리며 파티를 통해 설명한다. 6명으로 구성된 그룹에서는 모두 서로를 아는 사람이 적어도 3명 있거나 서로를 모르는 사람이 3명 이상 있을 것이다. r(3,3)의 답은 6이다.

Verstraete는 “이것은 자연의 사실이자 절대적인 진실이다”며 “상황이 어떻든, 어떤 여섯 사람을 선택하든 상관없다. 서로 아는 세 사람이 있을 수도 있고, 서로 모르는 세 사람이 있을 수도 있다. 더 많은 것을 찾을 수 있을지도 모르지만, 한 파벌 또는 다른 파벌에 최소한 3명이 있을 것이라는 보장이 있다”고 말했다.

수학자들이 r(3,3) = 6이라는 것을 발견한 후에 무슨 일이 일어났을까? 당연히 연결되지 않은 점의 개수가 가변적인 r(4,4), r(5,5), r(4,t)를 알고 싶었다. r(4,4)의 해는 18이며 1930년대에 Paul Erdös와 George Szekeres가 만든 정리를 사용해 증명했다.

현재 r(5,5)는 아직 알려지지 않았다.

이렇게 간단하게 설명할 수 있는 일이 왜 그렇게 해결하기 어려웠을까? 문제는 보이는 것보다 더 복잡한 것으로 밝혀졌다. r(5,5)의 해가 40~50 사이에 있다는 것을 알고 있다고 가정해 보자. 45개 점으로 시작했다면 고려해야 할 그래프는 10,234개 이상이다.

Verstraete는 “이 숫자는 찾기가 매우 어렵기 때문에 수학자들은 추정치를 찾는다”며 “이것이 Sam과 제가 최근 작업에서 달성한 것이다. 정확한 답은 아니지만 Ramsey 수치에 대한 최선의 추정치를 어떻게 찾을 수 있을까?”라고 설명했다.

Verstraete는 UC San Diego 교수인 Fan Chung과 고 Ron Graham이 쓴 Erdös on Graphs: His Legacy of Unsolved Problems에서 문제를 처음으로 확인했다. 문제는 그것을 해결할 수 있는 첫 번째 사람에게 250달러를 제안한 Erdös의 추측이다.

Verstraete는 “많은 사람들이 r(4,t)에 대해 생각해 왔다. 이는 90년 넘게 공개된 문제였다. 하지만 그것은 내 연구의 최전선에 있던 것이 아니었다. 모두가 그것이 어렵다는 것을 알고 있고 모두가 그것을 알아내려고 노력했기 때문에 새로운 아이디어가 없으면 아무데도 도달할 가능성이 없었다”라고 말했다.

그러다가 약 4년 전 Verstraete는 Dhruv Mubayi의 일리노이-시카고 대학교 수학자와 함께 다른 Ramsey 문제를 연구하고 있었다. 그들은 유사난수 그래프(pseudorandom graphs)가 이러한 오래된 문제에 대한 현재 지식을 발전시킬 수 있다는 것을 함께 발견했다.

1937년에 Erdös는 무작위 그래프를 사용하면 Ramsey 문제에 대한 좋은 하한선을 제공할 수 있음을 발견했다. Verstraete와 Mubayi가 발견한 것은 유사난수 그래프에서 샘플링하는 것이 무작위 그래프보다 Ramsey 수에 대해 더 나은 경계를 제공하는 경우가 많다는 것이다. 이러한 한계(가능한 답의 상한 및 하한)는 그들이 할 수 있는 추정 범위를 좁혔다. 즉, 그들은 진실에 점점 가까워지고 있었다.

2019년에 Verstraete와 Mubayi는 유사난수 그래프를 사용하여 r(3,t)를 풀었다. 그러나 Verstraete는 r(4,t)를 푸는 데 도움이 될 수 있는 의사 난수 그래프를 작성하는 데 어려움을 겪었다.

그는 유한 기하학, 대수학 및 확률을 포함하여 조합론 이외의 수학의 다양한 영역을 끌어들이기 시작했다. 결국 그는 자신의 그룹에서 유한 기하학을 전공한 박사후 연구원인 매테우스(Matheus)와 힘을 합쳤다.

Verstraete는 “우리가 필요로 하는 의사 난수 그래프를 유한 기하학에서 찾을 수 있다는 것이 밝혀졌다”며 “Sam은 우리가 필요로 하는 것을 구축하는 데 도움을 줄 수 있는 완벽한 사람이었다”고 말했다.

유사난수 그래프를 마련한 후에도 여전히 몇 가지 수학 문제를 해결해야 했다. 거의 1년이 걸렸지만 결국 그들은 해결책이 있다는 것을 깨달았다. r(4,t)는 t의 3차 함수에 가깝다. 항상 서로 아는 사람 4명이 있거나 서로 모르는 사람이 1명 있는 파티를 원한다면 대략 3명이 참석해야 한다. 작은 별표(실제로는 o)가 있는 이유는 이것이 정확한 답이 아닌 추정치이기 때문이다. 그러나 t3은 정확한 답에 매우 가깝다.

이번 연구 결과는 현재 Annals of Mathematics에서 검토 중이며 출판전논문 저장소 아르시브(arXiv)에서 볼 수 있다.