4'00" 읽기
수십 년 동안 추구해 온 램지(Ramsey) 문제 r(4,t)에 대한 해결책을 찾았다.

수학: "파티" 문제(Party Problem) 해결
수십 년 동안 추구해 온 램지(Ramsey) 문제 r(4,t)에 대한 해결책을 찾았다.

거의 100년 만에 드디어 해결되었나요? 수학자들은 수십 년 동안 열려 있던 소위 램지 정리 중 하나인 수학 문제에 대한 해결책을 찾았음에 틀림없다. 예를 들어, 특정 숫자를 미리 알 고 있음으로 파티에 몇 명이 참석해야 하는지 예측하는 데 사용할 수 있다. 수학적인 용어로 말하면 선과 점의 네트워크 내에서 특정 법칙을 예측하는 것이다. 연구원들은 이제 이 문제의 다른 변형에도 도움이 될 수 있는 문제 r(4,t)에 대한 해결 방법을 찾았다. 

▲ 이 추상적인 점과 선 패턴은 조합 문제 r(4,5)에 해당하는 그래프다. 서로 연결된 점이 4개 이상 있어야 하고, 연결되지 않은 점이 5개 있어야 한다. © Jacques Verstraete / UC 샌디에고

선과 점으로 구성된 수학적 그래프는 결코 단순한 조합론의 추상적인 형태가 아니며 매우 실용적인 용도로 사용된다. 이러한 노드 네트워크는 예를 들어 경로, 물류 컴퓨터 코드 또는 컨테이너 채우기를 계산하는 데 사용될 수 있다. 유명한 여행하는 세일즈맨 문제도 조합 그래프와 관련이 있다.

파티에서의 파벌 형성

이 수학적 접근 방식의 특별한 변형이 램지(Ramsey)-이론이다. 영국 수학자 프랭크 램지(Frank Ramsey)가 제시한 이 정리는 그래프 내에 항상 특정 형태의 질서 또는 "파벌 형성"이 있다고 가정했다. 예를 들어 두 점 사이를 연결하는 선이 없는 점(t) 또는 점들의 형태로 모두 선을 통해 서로 직접 연결되어 있다. 문제는 특정 규모의 네트워크에 그러한 파벌의 변종이 얼마나 많이 나타날 수 있는지다.

복잡하게 들리는 것을 파티에서 설명될 수 있다. 램지(Ramsey) 정리 r(3,3)은 최소 3명의 구성원으로 구성된 두 개의 서로 다른 파벌을 만들기 위해 파티에 몇 명의 사람을 초대해야 하는지 묻는다. 한사람은 관련된 모든 사람이 이미 서로를 알고 있고 다른 한사람은 손님에게 낯선 사람이다. 숫자가 작은 경우 그래프의 모서리를 색칠하면 이 문제에 대한 해결책을 찾을 수 있다. 1930년대에 r(3,3)의 해는 6이라고 알려졌다.

샌디에고 캘리포니아 대학의 쟈크 버스레이트(Jacques Verstraete)는 "어떤 상황이나 어떤 6명을 선택하는지는 중요하지 않다"고 설명한다. 수학적으로 말하면 적어도 세 사람이 한 그룹 또는 다른 그룹에 속하게 된다는 것이 보장된다.

r(4,t)의 해는?

하지만 더 큰 숫자는 어떨까? 지금까지 수학자들은 이 문제에 대해 최대 r(4.5)까지의 램지Ramsey 수만 찾았으며, 그 이상은 대략적인 추정만 가능하다. 이러한 미해결 Ramsey 문제 중 하나는 r(4,t)로 유명한 헝가리 수학자 Paul Erdös는 1930년대에 이 문제를 풀지 못했다. 이는 서로 아는 사람이 최소한 4명, 서로 모르는 임의의 불특정한 사람이 무한정 수 있으려면 숫자 r이 얼마나 높아야 하는지에 대한 질문을 제기한다.

▲ Paul Erdös는 조합론에서 해결되지 않은 문제 중 r(4,t)를 나열했다. © UC 샌디에고

Verstraete는 “많은 사람이 r(4,t)에 대해 고민해왔다. 이는 90년 넘게 공개된 문제였다”고 설명했다. "새로운 아이디어가 없으면 더 발전할 수 없다"고 Verstraete는 몇 년 전에 정확히 그렇게 생각했다. 그는 소위 의사 난수 그래프를 사용하여 다음을 수행할 수 있다는 것을 발견했다. 찾고 있는 Ramsey 번호의 범위를 좁혀보세요. 2019년에 그는 r(3,t)를 풀 수 있었다.

문제를 해결했다?!

Verstraete는 이제 브뤼셀 자유대학교의 동료인 Sam Mattheus와 함께 다음 단계를 밟았다. 유사(類似) 난수 그래프와 유한 기하학을 결합함으로써 그들은 r(4,t)에 대한 해가 t의 세제곱 에 매우 가깝다는 것을 발견했다. 즉, 파티에 서로 아는 사람 4명이 있고 모르는 사람 t명이 있으려면 대략 t^3명이 필요하다.

Verstraete는 “이 문제를 해결하는 데 말 그대로 수년이 걸렸다”고 말했다. “우리가 막혀서 이 문제를 해결할 수 있을지 궁금해하는 순간이 많았다. 하지만 시간이 아무리 오래 걸리더라도 결코 포기해서는 안 된다.” Erdös는 한때 r(4,t)를 해독한 첫 번째 사람에게 250달러의 보너스를 제안한 적이 있다. 이제 두 연구원은 이 보너스를 받을 수 있다. 현재 조사 중이다.

(Annals of Mathematics, 2024; doi: 10.4007/annals.2024.199.2.8)

출처: 캘리포니아 대학교 – 샌디에이고

[더사이언스플러스=문광주 기자]

[저작권자ⓒ the SCIENCE plus. 무단전재-재배포 금지]