김정한 샌드위치 추측 20년 만에 증명 — 그래프 이론 뜻과 랜덤 그래프 총정리

📐 수학 이야기

김정한·부반하가 2004년 제기한 랜덤 그래프 샌드위치 추측이 완전히 증명됐다고 퀀타 매거진이 9월 18일 전했다. 정점과 간선으로 관계를 다루는 그래프 이론의 뜻과 기본 용어, 에르되시-레니 랜덤 그래프와 정규 그래프, 증명의 아이디어까지 정리했다.

퀀타 매거진은 9월 18일, 워릭대학교의 리처드 몽고메리와 나탈리 비헤이그, 다니엘 일코비치가 2004년 김정한(현 고등과학원)과 부반하가 제기한 샌드위치 추측을 완전히 증명했다고 보도했다. 이 추측은 분석하기 어려운 랜덤 정규 그래프를 다루기 쉬운 두 랜덤 그래프 사이에 끼워 넣을 수 있다는 주장으로, 그래프 이론에서 수십 년 쌓인 결과를 한꺼번에 옮겨 쓸 수 있게 하는 다리다.

무슨 일이 있었나 — 퀀타 매거진 9월 18일 보도와 증명의 주인공

증명 논문 제목은 "김-부 샌드위치 추측의 증명"이다. 워릭대 리처드 몽고메리 교수와 당시 박사후연구원 나탈리 비헤이그, 박사과정생 다니엘 일코비치가 썼고, 2025년 10월 아카이브(arXiv)에 올라온 뒤 이달 퀀타 매거진의 보도로 널리 알려졌다. 추측을 제기한 김정한은 당시 마이크로소프트 연구소 소속이었고 지금은 고등과학원(KIAS) 교수이며, 공동 제안자 부반하는 현재 홍콩대학교에 있다.

텔아비브대의 미하엘 크리벨레비치는 이 추측이 자연스러워서 아직 증명되지 않은 것이 오히려 성가셨다며 안도감을 표했고, 히브리대의 길 칼라이는 이 정리를 여러 정리를 한 번에 낳는 메타 정리라고 불렀다. 지난 20년 동안 워털루대의 가오 푸를 비롯한 그래프 이론 연구자들이 샌드위치의 아래쪽 절반과 일부 조건에서의 위쪽 절반을 증명해 왔는데, 이번에 마지막 조각이 맞춰진 것이다.

그래프 이론이란? 정점·간선·차수의 기본 용어

그래프 이론의 그래프는 함수의 그래프가 아니다. 점(정점, vertex)과 점을 잇는 선(간선, edge)의 모임이다. 사람과 친구 관계, 컴퓨터와 회선, 뉴런과 시냅스가 모두 그래프다. 그래프 이론은 이 점과 선의 구조만으로 연결성, 경로, 군집 같은 성질을 다루는 수학이며, 코딩 테스트의 너비 우선 탐색과 최단 경로 알고리즘도 여기서 나왔다.

정점 $v$에 붙은 간선의 개수를 차수 $\deg(v)$라 한다. 모든 간선은 정점 두 개에 붙어 있으므로 차수를 전부 더하면 간선 수의 두 배가 되는데, 이것이 그래프 이론의 첫 정리인 악수 정리 $\sum_{v} \deg(v) = 2|E|$다. 정점 $n$개를 모두 서로 이은 완전 그래프 $K_n$의 간선 수는 $\binom{n}{2} = n(n-1)/2$이고, 모든 정점의 차수가 같은 $d$인 그래프를 $d$-정규 그래프라 부른다. 악수 정리에 따라 $nd$가 짝수여야 정규 그래프가 존재한다.

그래프 이론의 기본 대상

정점 집합 V와 간선 집합 E의 쌍 G=(V, E). 간선은 정점 두 개를 잇는다.

경로와 사이클

간선을 따라 정점을 차례로 지나는 것이 경로, 출발점으로 돌아오면 사이클. 모든 정점을 한 번씩 지나면 해밀턴 사이클.

정규 그래프

모든 정점의 차수가 같은 그래프. 간선이 서로 얽혀 있어 확률 계산이 어렵지만 실제 네트워크와 더 닮았다.

단조 성질

간선을 더해도 유지되면 증가 성질(연결성·해밀턴성), 간선을 빼도 유지되면 감소 성질(평면성·삼각형 없음).

랜덤 그래프 두 종류 — 에르되시-레니 그래프와 랜덤 정규 그래프

랜덤 그래프 이론은 1950년대 말에 태어났다. 벨 연구소의 에드거 길버트는 전화망을 이해하려고, 헝가리의 에르되시 팔과 레니 알프레드는 순수한 호기심으로 같은 모형을 만들었다. 정점 $n$개를 놓고 모든 정점 쌍마다 독립적으로 동전을 던져 확률 $p$로 간선을 긋는 것이다. 이것이 이항 랜덤 그래프 $G(n,p)$이며, 흔히 에르되시-레니 랜덤 그래프라 부른다.

$$\Pr[\{u,v\} \in E(G(n,p))] = p \ \ (\text{모든 쌍 독립}), \qquad \mathbb{E}[\deg(v)] = (n-1)p$$

간선들이 서로 독립이라 계산이 잘 되고, 그래서 랜덤 그래프 이론의 고전적 결과는 대부분 이 모형에서 나왔다. 예를 들어 해밀턴 사이클이 갑자기 나타나는 문턱값은 1980년대 초에 이미 밝혀졌다.

$$p = \frac{\ln n + \ln\ln n + c_n}{n}, \qquad c_n \to \infty \ \Rightarrow\ G(n,p)\text{는 거의 확실히 해밀턴 사이클을 가진다}$$

여기서 $\ln$은 자연로그, $c_n$은 천천히 커지는 수열이다. 반면 랜덤 $d$-정규 그래프 $G_d(n)$은 정점 $n$개짜리 $d$-정규 그래프 전체 가운데 하나를 균등하게 뽑은 것이다. 모든 정점의 차수가 $d$로 고정되니 한 간선의 존재가 다른 간선에 영향을 주고, 독립성이 깨진다. 같은 해밀턴 사이클 질문에 답하는 데 이항 그래프보다 20년이 더 걸린 이유다. 그런데 실제 네트워크는 정규 그래프에 더 가까운 경우가 많아, 수학자들은 어려운 쪽의 답을 원했다.

샌드위치 추측이란? 세 그래프의 결합으로 성질을 옮기는 법

김정한과 부반하의 아이디어는 어려운 정규 그래프를 쉬운 이항 그래프 두 장 사이에 끼우는 것으로, 그래프 이론에서 성질을 한 모형에서 다른 모형으로 옮기는 전형적인 전략이다. 정확히 말하면, 차수 $d$가 $\log n$보다 빨리 커질 때 세 그래프를 한 확률공간 위에서 함께 만들어 다음이 거의 확실히 성립하게 할 수 있다는 주장이다.

$$G(n, p_*) \subseteq G_d(n) \subseteq G(n, p^*), \qquad p_* = (1-o(1))\frac{d}{n},\ \ p^* = (1+o(1))\frac{d}{n}$$

기호 $\subseteq$는 왼쪽 그래프의 간선이 모두 오른쪽 그래프에도 들어 있다는 뜻이고, $o(1)$은 $n$이 커지면 0으로 가는 오차다. 세 그래프의 평균 차수는 모두 $d$에 가깝다. 이렇게 세 그래프를 한 번에 만드는 것을 결합(coupling)이라 하는데, 확률적 그래프 이론에서 각각은 원래 분포를 따르면서도 포함 관계가 거의 확실히 성립하도록 뽑는 기술이다.

샌드위치가 있으면 무엇이 좋은가. 간선을 더해도 유지되는 증가 성질, 이를테면 연결성이나 해밀턴 사이클의 존재는 아래쪽 빵 $G(n,p_*)$에서 증명해 두면 그 간선을 모두 품은 $G_d(n)$에도 자동으로 옮겨간다. 간선을 빼도 유지되는 감소 성질, 이를테면 삼각형이 없다거나 색칠 수가 작다는 것은 위쪽 빵 $G(n,p^*)$에서 증명하면 그 부분그래프인 $G_d(n)$에도 그대로 성립한다. 60년 넘게 쌓인 랜덤 그래프 이론의 정리들이 정규 그래프의 정리로 공짜로 바뀌는 셈이다.

증명의 아이디어 — 동전 두 개로 빵과 치즈를 동시에 굽기

그래프 이론에서 이 결합이 어려웠던 점은 이항 그래프와 정규 그래프가 원래 전혀 다른 방식으로 만들어진다는 데 있다. 하나는 동전 던지기, 다른 하나는 정규 그래프 전체에서 균등 추출이다. 세 연구자는 2023년부터 두 그래프를 간선 하나씩 동시에 쌓는 방법을 궁리했다. 치즈 한 장을 통째로 얹는 대신 잘게 간 치즈를 빵 위에 한 조각씩 올려, 매 순간 정규 그래프가 이항 그래프를 포함하도록 유지하는 방식이다. 가오 푸와 동료들이 2019년에 쓴 방법을 크게 손본 절차다.

구체적으로는 정점 쌍을 하나 고르고 첫 번째 동전을 던진다. 앞면이면 이항 그래프와 정규 그래프 양쪽에 간선을 긋는다. 뒷면이면 이항 그래프에는 긋지 않되, 정규 그래프는 차수를 $d$로 맞춰야 하므로 두 번째 동전을 던져 간선을 추가할지 정한다. 핵심은 두 번째 동전의 확률을 그래프가 자라는 동안 어떻게 바꿔야 마지막에 정확히 정규 그래프가 나오는지를 추정한 데 있다. 이렇게 아래쪽 절반을 얻은 뒤, 모든 간선이 다 있는 완전 그래프에서 출발해 간선을 하나씩 지우는 방향으로 같은 절차를 뒤집어 위쪽 절반을 얻었다.

1959년

길버트, 에르되시·레니가 각각 이항 랜덤 그래프 모형을 제안.

1980년대 초

이항 랜덤 그래프의 해밀턴 사이클 문턱값 규명. 정규 그래프에서는 20년 뒤에야 같은 답이 나옴.

2004년

김정한·부반하, 어드밴시스 인 매스매틱스에 샌드위치 결합을 발표하고 완전한 샌드위치 추측 제기.

2019년

가오 푸 등, 넓은 차수 범위에서 아래쪽 절반 증명. 위쪽 절반은 일부 조건에서만 성립.

2025년 10월 → 2026년 9월

비헤이그·일코비치·몽고메리, 추측을 완전히 증명(arXiv 2510.20765). 퀀타 매거진 9월 18일 보도.

왜 중요한가 — 해밀턴 사이클에서 네트워크 과학까지

샌드위치 추측이 정리가 되면서 그래프 이론 연구자들은 랜덤 정규 그래프의 성질을 처음부터 증명할 필요가 없어졌다. 이항 랜덤 그래프에 대해 쓰인 방대한 문헌을 그대로 정규 그래프의 정리로 바꿔 쓸 수 있고, 실제로 이 정리를 인용한 새 결과가 벌써 나오고 있다. 칼라이가 말한 대로 증명에 쓰인 기법 자체가 그래프 이론의 도구 상자를 넓혔기 때문에, 층을 번갈아 쌓은 더 복잡한 샌드위치도 다음 목표로 거론된다.

개인적으로 이 결과가 반가운 이유는 그래프 이론 수업에서 늘 따로 배우던 두 모형이 사실 한 뿌리라는 것을 보여주기 때문이다. 학부 때 이항 랜덤 그래프의 연결성 문턱값을 배우며 정규 그래프에서도 같을지 물었다가 아직 열린 문제가 많다는 답을 들었던 기억이 있다. 매우 제약된 과정과 전혀 제약되지 않은 과정이 서로를 감싸 안는다는 사실은 비헤이그의 말처럼 거의 믿기 어려울 만큼 좋은 결과이고, 그것이 참으로 밝혀졌다.

함께 읽으면 좋은 글

순열과 조합 차이, 공식과 실생활 예시 완벽 정리 퍼콜레이션 30년 난제 증명 — 퍼콜레이션 뜻과 임계 확률 총정리 유튜브 알고리즘 뜻과 원리, 추천을 결정하는 수학

참고 자료

Quanta Magazine — Mathematicians Build Long-Awaited Graph Sandwich (2026년 9월 18일) Behague, Iľkovič, Montgomery — A proof of the Kim-Vu sandwich conjecture (arXiv 2510.20765) Kim, Vu — Sandwiching random graphs: universality and small world (Advances in Mathematics, 2004) Gao, Isaev, McKay — Sandwiching random regular graphs between binomial random graphs (arXiv 1906.02886)