"수학계 난제 드디어 풀렸다" 20년 만에 완성된 '그래프 샌드위치' 추측

요약 수학계에서 20여 년간 난제로 꼽히던 '그래프 샌드위치 추측(sandwich conjecture)'이 마침내 완전히 증명되었습니다. 그래프 이론에서 점(정점)과 선(간선)으로 이뤄진 네트워크는 인간관계부터 인터넷망, 뇌 신경망까지 다양한 복잡계를 모델링하는 핵심 도구입니다. 1950년대 에드거 길버트와 에르되시-레니 등이 정립한 '랜덤 이항 그래프(random binomial graph)'는 동전 던지기처럼 독립적인 확률로 간선을 연결해 비교적 분석하기 쉽지만, 현실의 정밀한 구조를 다 담아내기엔 한계가 있었습니다. 반면 모든 정점이 동일한 수의 연결선을 갖는 '랜덤 정규 그래프(random regular graph)'는 현실 네트워크를 훨씬 정확하게 반영하지만 제약 조건이 빡빡해 분석 난도가 극도로 높았습니다. 2004년 한국계 수학자 김정한 박사(당시 마이크로소프트 리서치)와 판 하 부(Van Ha Vu) 박사는 이를 해결하기 위해 기발한 아이디어를 냈습니다. 다루기 힘든 정규 그래프(치즈)를 다루기 쉬운 두 개의 이항 그래프(식빵 양쪽) 사이에 끼워 넣는 '샌드위치' 결합 기법을 고안한 것입니다. 아래쪽 이항 그래프와 위쪽 이항 그래프로 샌드위치를 만들 수만 있다면, 분석하기 쉬운 이항 그래프의 성질들을 정규 그래프가 거저 물려받게 됩니다. 두 수학자는 충분히 큰 정규 그래프라면 언제나 이런 샌드위치를 구성할 수 있을 것이라 추측했고, 지난 20년간 부분적인 증명이 이어져 오다 2025년 세 명의 수학자가 극한의 기법을 동원해 마침내 이 추측을 최종적으로 완전히 풀어냈습니다.