2004년에 나온 그래프 이론 추측이 22년 만에 완전히 증명됐습니다. 정규 그래프를 다루기 쉬운 그래프 두 개 사이에 끼워 넣을 수 있다는 주장이고, 이름도 그대로 샌드위치 추측이에요.
증명 논문은 2025년 10월 23일 arXiv에 올라왔고, Quanta Magazine이 2026년 9월 18일 이 결과의 의미를 다시 소개하면서 수학계 밖에도 알려졌습니다.
증명 논문 제목과 초록 — 출처: arXiv:2510.20765 / Behague, Il’kovič, Montgomery
두 가지 랜덤 그래프
두 랜덤 그래프 모형 비교 — 출처: 설명용 예시 · 자가 렌더
그래프는 점(꼭짓점)과 점을 잇는 선(변)으로 이뤄진 구조입니다. 사람을 점으로, 친구 관계를 선으로 보면 소셜 네트워크가 그래프가 돼요.
[이항 랜덤 그래프 G(n, p)] 점 n개를 두고 가능한 모든 짝마다 확률 p로 따로 동전을 던져 변을 추가할지 정함
[랜덤 d-정규 그래프] 모든 점이 정확히 d개의 변을 갖는 그래프들 중에서 하나를 균등하게 고름
차이는 독립성에 있습니다. 이항 그래프는 변 하나하나가 서로 무관하게 정해져서 계산이 쉬워요. 확률론의 표준 도구가 그대로 통합니다.
반면 정규 그래프는 변 선택이 서로 독립적이지 않습니다. 어느 점에 변을 하나 놓으면 그 점에서 추가할 수 있는 남은 변의 수가 줄어서 다음 선택이 달라져요. 그래서 다루기가 훨씬 까다롭습니다. 문제는 현실의 여러 구조가 정규 그래프 쪽에 가깝다는 것이에요. 컴퓨터 네트워크나 통신망처럼 각 노드의 연결 수가 규격으로 정해진 경우가 그렇습니다.
샌드위치가 뜻하는 것
샌드위치 구조 — 출처: 설명용 예시 · 자가 렌더
Kim과 Vu가 2004년에 내놓은 추측은 이렇습니다. 변이 조금 적은 이항 그래프 하나와 조금 많은 이항 그래프 하나를 선택하면, 랜덤 d-정규 그래프가 그 두 그래프 사이의 포함 관계를 만족한다는 거예요.
| 층 | 그래프 | 변의 확률 |
|---|---|---|
| 아래 | 이항 랜덤 | (1-o(1)) × d/n |
| 가운데 | 랜덤 d-정규 | d/n에 해당 |
| 위 | 이항 랜덤 | (1+o(1)) × d/n |
여기서 끼운다는 말은 부분 그래프로 포함된다는 뜻입니다. 아래쪽 그래프가 가운데 그래프의 부분 그래프이고, 가운데 그래프가 위쪽 그래프의 부분 그래프인 상태예요. 이 일이 높은 확률로 일어나도록 세 그래프를 한꺼번에 만들 수 있다는 것이 추측의 내용입니다.
이게 왜 쓸모 있냐면, 성질을 옮길 수 있기 때문입니다. 변을 더 넣어도 유지되는 성질은 아래쪽 그래프에서 가운데 그래프에 적용할 수 있고, 변을 빼도 유지되는 성질은 위쪽 그래프에서 가운데 그래프에 적용할 수 있어요. 이항 그래프에서 증명된 결과를 정규 그래프에서 다시 증명하지 않아도 된다는 뜻입니다.
텔아비브대 미하엘 크리벨레비치(Michael Krivelevich)는 이 추측을 두고 어떤 면에서는 매우 자연스러운 주장이었고 증명되지 않은 채로 있는 것이 계속 거슬렸다고 말했습니다.
로그 조건
점의 개수를 n, 각 점의 변 개수를 d라고 할 때 d가 log n보다 빨리 커져야 한다는 것이에요. 수식으로는 d = ω(log n)으로 적습니다.
왜 이런 기준이 필요한지는 차수가 너무 작을 때를 생각하면 보입니다. 이항 그래프는 변을 독립으로 뽑기 때문에 점마다 변 개수의 차이가 커요. 평균이 3이어도 어떤 점은 0개, 어떤 점은 8개가 됩니다.
정규 그래프는 모든 점이 정확히 d개입니다. 평균이 같아도 분포가 전혀 달라요. d가 작으면 이 차이가 두드러져서 어떤 이항 그래프로도 정규 그래프와 필요한 포함 관계를 만들 수 없습니다. d가 커질수록 이항 그래프의 차수 분포가 평균 주변에 집중돼 정규 그래프와 비슷해져요. 그 기준선이 log n입니다.
22년의 경과
샌드위치 추측 22년 — 출처: arXiv·Quanta 자료 기반 자가 렌더
추측이 나온 뒤 조건을 조금씩 완화하는 연구가 이어졌습니다. Gao와 Isaev, McKay가 d가 log n의 네제곱보다 훨씬 클 때 성립함을 보였고, 이들이 제시한 결합 절차는 d가 n을 √(log n)으로 나눈 값보다 클 때까지만 분석돼 있었어요.
2025년 논문은 바로 그 절차를 끝까지 분석해 남은 구간을 증명했습니다. 저자는 워릭대의 리처드 몽고메리(Richard Montgomery)와 당시 그의 박사후연구원이던 나탈리 비헤이그(Natalie Behague), 박사과정생 다니엘 일코비치(Daniel Il’kovič) 셋입니다. 논문은 자신들이 샌드위치 추측을 완전히 증명했다고 적었어요.
증명 방식은 세 그래프를 따로 만들어 비교하는 것이 아닙니다. 변을 하나씩 더해 가면서 매 순간 포함 관계가 유지되도록 확률을 조정하는 방법을 썼어요. 각 단계에서 조건부 확률을 조정해 정규 그래프의 차수 조건을 지키면서도 아래쪽 이항 그래프를 계속 포함하게 만듭니다.
이 결과의 활용 범위
샌드위치 추측은 그 자체로 쓰이기보다 다른 증명에 활용되는 도구가 됩니다. 랜덤 정규 그래프에서 어떤 성질을 보이고 싶을 때, 대응하는 이항 그래프 결과를 찾아 적용할 수 있어요.
- 해밀턴 경로처럼 변을 더해도 유지되는 성질은 아래쪽 그래프 결과를 적용
- 색칠 수의 상한처럼 변을 빼도 유지되는 성질은 위쪽 그래프 결과를 적용
- 두 방향을 합치면 정규 그래프의 성질을 좁은 범위로 제한할 수 있음
옮길 수 있는 것은 변을 더하거나 빼는 방향이 정해진 성질뿐이고, 정확한 개수를 세는 문제는 이 방법으로 직접 해결되지 않아요. 조건인 d = ω(log n) 아래에서 어떤 성질이 성립하는지도 이 논문이 다루는 범위 밖입니다.
샌드위치 추측 정리 — 출처: 본문 정리 · 자가 렌더