2015년 봄에 KAIST 수리과학과 졸업생인 MIT의 이중범 박사가 램지이론에 관한 Burr와 Erdős의 1973년 추측을 해결한 논문을 인터넷에 공개하여 놀라게 했었습니다. 이중범 박사는 9월에 KAIST 수리과학과 콜로퀴엄에서 그 결과를 알기쉽게 강연해주었는데요, 그 내용을 소개해볼까 합니다.
데이비드 콘론 교수를 소개한 글에서도 램지 이론이 조금 소개되었습니다. 가장 간단한 경우로 6명이 있으면 그 중 어떤 3명은 서로 아는 사이거나, 어떤 3명은 서로 모르는 사이라는 결과가 있지요. 이 상황을 그래프 언어로 표현하면 꼭지점 6개짜리 완전그래프 $K_6$의 각 선을 빨강이나 파랑으로 색칠하면 항상 빨강색 $K_3$가 부분그래프로 있거나 파랑색 $K_3$가 부분그래프로 있다고 이야기할 수 있습니다.
이제 어떤 (작은) 그래프 $H$에 대해 $r(H)$를 $K_n$의 각 선을 빨강이나 파랑으로 칠하면 반드시 빨강색 $H$가 $K_n$의 부분그래프이거나 파랑색 $H$가 $K_n$의 부분그래프로 있을 $n$의 최소값이라고 합시다. 즉, 앞의 이야기에 의하면 $r(K_3)\le 6$이라는 뜻이죠. 실제로도 $r(K_3)=6$입니다.
$H$가 $K_3$처럼 완전그래프인 경우에는 그 값의 증가율을 구하는게 콘론 교수 소개글에서도 언급된 것처럼 아주 어려운 문제로 남아있습니다. 그럼 $H$에 선이 많이 없는 경우는 어떨까요.
어떤 경우를 선이 많이 없는 경우라고 할까요? $H$의 각 꼭지점에 연결된 선의 수가 몇 개 이하라고 하는 것도 가능하겠지요. 조금 더 확장해서 아래와 같은 개념을 생각해봅시다. $H$의 꼭지점의 수가 $h$개일 때 각 꼭지점에 번호를 1부터 $h$까지 잘 붙였더니, 각각의 꼭지점에서 그것보다 번호가 작은 쪽으로 이어진 선의 수가 $d$개 이하라면 그 그래프 $H$를 $d$-degenerate이라고 합니다. 즉, 사람들을 줄을 세워서 자기보다 앞에 서있는 사람들 중에 자기가 아는 사람이 항상 $d$명 이하가 되게 할 수 있으면 그 사람들로 만든 그래프는 $d$-degenerate인 것이지요. 자기보다 뒤에 서있는 사람 중에 아는 사람이 얼마나 많은지는 그 사람은 신경쓰지 않아도 되니까 중간에 서있는 사람이 아는 사람수는 $d$보다 훨씬 많을 수도 있습니다.
1973년 Burr와 Erdős는 $H$가 꼭지점이 $n$개이면서 $d$-degenerate인 경우는 램지수$r(H)$의 증가율이 낮지 않겠냐 생각해서 \[ r(H)\le f(d) n\]가 되게 하는 $d$에 관한 함수 $f$가 있지 않겠냐 추측을 했습니다. 이걸 Erdős-Burr 추측이라고 합니다. 이 추측에서는 과연 $n^2$이나 $2^n$이 아닌 $n$으로 $r(H)$ 값을 잡을 수 있겠느냐 하는 것이 중요한 것이지요.
그간 많은 수학자들이 이 문제를 해결해보려고 시도를 했습니다. $d$-degenerate이 아니라 $H$의 각 꼭지점에 연결된 선이 $d$개 이하인 더 쉬운 경우로 만들어서는 1983년에 이미 증명이 되었습니다. $d$-degenerate인 경우에 대해서는 2004년 논문에서 일리노이대학의 Kostochka 교수와 에머리 대학의 Rödl 교수가 \[r(H)\le f(d)n^2\]이라는 것을 증명하였고 이 후 Kostochka 교수와 이중범 박사의 박사지도교수였던 ETH의 Benny Sudakov 교수가 \[ r(H)\le f(d) \cdot n \cdot n^{\frac{1}{(\log n)^{1/(2d+1)}}} \]이라는 것을 증명했습니다. 나중에 Sudakov 교수가 당시 지도대학원생이고 현재 스탠포드대학에 있는 Fox 교수와 2009년에 \[ r(H)\le f(d) \cdot n\cdot n^{\frac{1}{\sqrt{\log n}}}\]까지 증명한 결과를 발표하여 앞의 결과를 개선했었습니다.
2015 봄 이중범 박사는 적당한 상수 $c$에 대해 \[ r(H)\le 2^{d2^{c(d+1)}} n\]이 성립한다고 증명을 써서 arXiv에 공개하였습니다. 즉, $f(d)=2^{d2^{c(d+1)}}$으로 잡으면 된다는 것을 처음으로 밝혀서 Burr와 Erdős의 추측을 해결한 것이지요. 축하합니다.
