편집자주: 서울에서 열릴 2014 세계수학자대회(ICM)를 기념하여, 조합수학 분야의 기조강연자 및 초청강연자들을 소개하는 글을 준비하였습니다. 이번 글은 2014년 8월 15일 오후 3시에 강연할 옥스포드 대학 데이비드 콘론(David Conlon) 교수에 대해, 그의 첫 박사과정 지도학생인 이준경 학생이 소개하는 글을 싣습니다.

1982년 태어난 콘론 교수는 아일랜드 출신으로, 필즈 메달 수상자인 Timothy Gowers 교수의 지도를 받고 캠브리지 대학에서 박사를  받았습니다. 콘론 교수의 전문 분야는 극단 조합론(extremal combinatorics)의 중심이라 할 수 있는 램지 이론입니다.

램지 이론

‘램지 이론’이라고 하면 가장 먼저 떠오르면서 실제로도 제일 중요한 것이 학부 이산수학 과목에서도 접할 수 있는 ‘램지 수’ 라 할 수 있습니다. $N$명의 사람들이 있으면 항상 서로 친구관계인 $k$명이 있거나 서로 친구관계가 아닌 $t$명의 사람이 있을 최소의 $N$ 값을 램지 수 $R(k,t)$라 합니다.  대표적인 예로 6명의 사람이 있으면, 이 중에서는 항상 서로 모두 페이스북 친구인 3명이 있거나 서로 모두 친구가 아닌 3명이 있게 되지만, 5명의 경우 이런 사실이 성립하지 않을 수도 있습니다. 따라서 $R(3,3)=6$인 것이죠. 이러한 수가 항상 존재한다는 정리가 바로 램지 정리입니다.

아직도 $R(6,6)$의 정확한 값도 모를 정도로 램지 수를 완전하게 계산해 내는 데에는 한계가 많기 때문에 지금까지의 연구는 주로 $R(3,t), R(4,t),\cdots$와 같이 두 변수 중 하나의 값을 고정시키거나, $R(k,k)$와 같이 $k=t$인 경우에 주목해 왔습니다. 특히 $\lim_{k\rightarrow\infty}R(k,k)^{1/k}$이 존재하는가 라는 문제는 20세기의 전설적인 수학자 에르되시(Erdős)가 100달러를 상금으로 걸어놓은 조합론의 가장 중요한 미해결 난제 중 하나입니다.

현재까지 전자의 $R(3,t)$ 케이스가 현재 상계와 하계가 4배밖에 차이가 나지 않을 정도로 연구가 진척된 반면(여기에 대해서는 다음에 더 자세히 다뤄 보도록 하겠습니다) 후자, 즉 대각 램지 수(diagonal Ramsey Number)라 불리는 $R(t,t)$의 경우 연구 결과가 많지 않았습니다. 에르되시(Erdős)와 세케레시(Szekeres)가 1935년 처음으로 $R(k,k)\leq \binom{2k-2}{k-1}$임을 보였고, 그 뒤 반세기가 더 지난 87년에서야 이번 2014년 ICM 기조강연자이기도 한 Vojtěch Rödl 교수가 $$\lim_{k\rightarrow\infty}\frac{R(k,k)}{\binom{2k-2}{k-1}}=0$$임을 보였습니다 (이 결과들은 사실 $R(k,t)$의 경우에 대해서도 일반화가 가능합니다.) 그리고 같은 해 Thomason 교수가 이 상계를 개선해서 어떤 양의 상수 $A$에 대해 $$R(k,k)\leq k^{-1/2+A/\sqrt{\log k}}\binom{2k-2}{k-1}$$임을 증명했습니다. 그리고 다시 20여년이 지나서야 콘론 교수가 $$R(k,k)\leq k^{-C\frac{\log k}{\log\log k}}\binom{2k-2}{k-1}$$라는 결과를 얻었고, 지금까지 이 상계가 최선의 결과입니다. 이 결과는 처음으로 아무리 큰 상수 $A$를 가지고 와도 점근적으로 $R(k,k)<k^{-A}\binom{2k-2}{k-1}$임을 보인 것으로, 수학 분야의 최고 학술지라 할 수 있는 Annals of Mathematics에 실렸습니다. (논문링크) 참고로 하계의 경우 Spencer의 1975년 결과가 아직도 깨지지 않고 있고, 상계와 그 간극이 작지 않습니다.

옮김 정리

콘론 교수의 최근 연구 중 주목받는 것은 Gowers 교수와 함께 한 옮김 정리(Transference Principle)에 관한 연구입니다. 이 결과는 ‘소수 안에는 모든 (유한한) 길이의 등차수열이 있다’는 그린-타오 정리의 그래프 버전이라고 할 수 있습니다.

그린-타오 정리의 핵심이 되는 부분은 ‘자연수 안에서 양의 밀도를 갖는 수열 안에는 모든 유한한 길이의 등차수열이 있다’는 Szemerédi의 정리의 가정을 소수로 ‘옮겨(transfer)’ 오는 것인데, 그린-타오 정리가 처음 증명된 이후 Gowers, 그리고 Reingold-Trevisan-Tulsiani-Vadhan 그룹 등에 의해 이 부분의 더 단순한 증명을 찾는 연구가 계속되었습니다. Conlon 교수와  Gowers 교수는 이 옮김 정리의 그래프 이론 버전을 개발해서 랜덤 그래프 이론의 여러 가지 문제들을 한꺼번에 해결하는 결과를 얻었습니다. 비슷한 결과가 Schacht에 의해서도 독립적으로 증명되었고, 후속 연구를 했던 Samotij까지 네 명의 연구자가 모두 함께 또 하나의 논문을 내기도 했습니다. 이 증명은 함수해석학의 한-바나흐 정리를 기반으로 하고 있어 놀랍기도 하거니와, 해석학이 조합론에 얼마나 광범위하게 쓰일 수 있는지를 보여 주는 하나의 예가 되었습니다.

또한 콘론 교수는 이 경험을 바탕으로 최근 Fox, Zhao 와 함께 그린-타오 정리의 증명을 간단히 하는 연구를 계속 진행했고, 그 결과 원래 60페이지가 넘던 증명을 25페이지까지 줄이기도 했습니다.

콘론 교수는 앞으로도 여러 가지 램지 이론, 조합적 정수론, 랜덤 그래프 이론을 연결시키는 극단 조합론의 여러가지 문제들을 연구할 계획입니다. 콘론 교수가 이번 ICM에서 어떤 내용의 발표를 할지는 http://people.maths.ox.ac.uk/~conlond/ICMPaper.pdf 에서 미리 확인할 수 있는데, 지금까지 연구 결과를 잘 정리함과 동시에 앞으로 이 분야의 연구가 나아갈 방향도 제시하는 좋은 논문입니다. 관련 분야에 전문적인 관심이 있는 독자들에게 일독을 권합니다.

평면 상에 교차점 없이 그릴 수 있는 그래프를 평면그래프라 한다. 모든 평면그래프는 이웃한 꼭지점이 서로 다른 색이 되도록 4개 이하의 색으로 잘 칠할 수 있다는 정리를 4색정리라고 하는데, 그래프이론에서 4색정리만큼 잘 알려지고 많은 사람들의 관심을 받은 문제는 없다고 해도 과언이 아니다. 이제 4색정리는 증명이 되었지만, 또 어떤 문제들이 남아있을까?

어떤 그래프 H가 그래프 G의 마이너라 함은, G에서 일부 변과 꼭지점을 지운 후 몇몇 변은 양 끝점을 한 점으로 합치는 ‘축약'(contraction) 연산을 해서 H가 얻어진다는 뜻이다. 어떤 그래프 G가 평면그래프라면 변 하나 잡아서 축약해도 여전히 평면에 교차점 없이 그릴 수 있기 때문에 평면그래프의 모든 마이너는 역시 평면그래프이다.

꼭지점 n개가 서로 다 이어진 그래프를 완전그래프라 부르고 K_n이라 한다. 하트비거는

“K_t+1이 마이너로 없는 모든 그래프는 이웃한 꼭지점은 다른 색이 되게 t개의 색으로 칠할 수 있다“

고 추측하였다. 휴고 하트비거(Hugo Hadwiger)가 1943년에 만든 추측이라서 하트비거의 추측(Hadwiger’s conjecture)이라고 부른다.

K₅는 평면그래프가 아니기 때문에 평면그래프는 K₅ 마이너를 가질 수 없고 따라서 t=4일때 하트비거의 추측이 참이라면 벌써 4색 정리가 증명된다. 사실, 4색정리를 이용하면 t=4일때 하트비거의 추측 역시 증명할 수 있어서 t=4인 경우 이 추측은 4색정리와 동치이다.

t=2일때는 K₃ 마이너가 없는 그래프는 항상 수형도 여러 개로 구성된 그래프이므로 2개 색으로 쉽게 칠할 수 있다. t=3일때는 K₄ 마이너가 없는 경우인데, 이때는 series-parallel 그래프라는 그래프가 되어 역시 손쉽게 3개 색으로 칠할 수 있다.

한편 t=5인 경우는 어려운 문제인데, 1993년에 Robertson, Seymour, Thomas 세 명의 교수가 출판한 논문에서 t=5인 경우 최소 크기의 반례에서는 한 꼭지점을 잘 지우면 평면그래프가 된다는 것을 증명하였고 따라서 사색정리에 의해 t=5인 경우도 하트비거의 추측이 참이라는 것을 증명하였다.

이 추측은 t>5인 경우는 여전히 완전히 미해결인 상태로 남아있다.

이제 하트비거 추측을 약하게 만든 새로운 문제를 생각해보자. 하트비거의 추측이 맞다면 K_t+1마이너가 없는 그래프의 꼭지점 집합을 항상 t개의 꼭지점 집합 X₁,X₂, .., X_t로 잘 나눠서 각 X₁,…,X_t 안에는 변이 하나도 포함되지 않게 할 수 있다. 그러면 혹시 잘 나눠서 각 X_i 안에서 각 꼭지점은 X_i 안에서는 f(t)개 이하의 이웃만 갖게 할 수 있을까? 만일 f(t)=0이라면 원래의 하트비거의 추측과 같다.

최근 필자가 KAIST 강동엽 학생, UIUC에서 박사학위 받고 잠깐 KAIST 와 있는 김재훈 박사, 그리고 프린스턴 대학 Seymour 교수 및 Edwards 학생과 함께 쓴 연구논문(arxiv에 올린 논문)에서  앞에서 언급한 하트비거의 추측의 약한 형태에 대해 연구를 하였는데, 위 조건을 만족하는 f(t)라는 함수가 존재한다는 것을 1페이지짜리 증명을 통해 풀었다. 여기서 흥미롭게도 이 약한 문제에서조차 t개가 아닌 t-1개로는 나눌 수 없다는 것 또한 증명할 수 있었다.

…, -2, 0, 2, 4, 6, 8, 10, … (짝수)
…, -3, 0, 3, 6, 9, 12, 15, … (3의 배수)
…, -3, 1, 5, 9, 13, 17, … (4의 배수+1)
…, -5, 3, 11, 19, 27, 35, … (8의 배수+3)
…, -5, 7, 19, 31, 43, … (12의 배수+7)
…, -1, 23, 45, 68, … (24의 배수+23)

어떤 수 $n$을 24로 나눈 나머지를 생각해보면 모든 정수는 위 등차수열 중 적어도 하나에는 반드시 포함됨을 알 수 있다. 유명한 수학자 에르되시( Erdős)는 1950년 논문에서 임의의 $N$에 대해, 공차가 $N$ 이상인 등차수열만 써도 이런 식으로 모든 정수 집합을 덮을 수 있지 않겠냐고 적었다. 하지만 이 문제는 지난 수십년 간 풀리지 않았었고, 에르되시는 1980년 논문에서 본인이 1934년에 이 문제를 생각했다며 증명이나 반증에 $500을 준다고 했다. 에르되시는 1913년 태어났으니 1934년이면 21살일 때가 되겠다.

예를 들어 N=3인 경우 아래처럼 등차수열들을 구성하면 공차는 서로 다르면서 전체 정수 집합을 덮을 수 있다.

3의 배수, 4의 배수, 5의 배수, 6의 배수+1, 8의 배수+1, 10의 배수+2, 12의 배수+11, 15의 배수+1, 20의 배수+14, 24의 배수+5, 30의 배수+8, 40의 배수+6, 60의 배수+58, 120의 배수+26.

1968년엔 Churchhouse가 N=9인 방법을 찾고, 1971년에는 Krukenberg가 박사논문에서 N=18인 방법을 기술했으며, S. L. G. Choi가 1971년에 N=20인 방법을 찾았다. 1981년 Morikawa는 N=24까지 올리고 2009년엔 Gibson은 대규모 컴퓨터 계산을 통해 N=25인 방법을 찾았으며, 같은 해 Nielson이 N=40인 방법에 대한 논문을 출판했다. 이 문제에 대한 Nielson의 설명을 아래 동영상에서 볼 수 있다.

2013년  옥스포드대학의 Bob Hough 박사는 에르되시의 위 추측은 거짓이고, 만일 공차가 서로 다른 등차수열로 정수 집합을 덮을 수 있다면 그 중 적어도 하나의 등차수열의 공차는 $10^{18}$보다 클 수 없음을 증명하였다. 이로써 무려 63년만에 에르되시의 미해결 문제 하나가 해결된 셈이다. 증명은 확률론적 방법을 쓰는데, Lovasz Local Lemma를 응용한다고 한다. (arxiv에 올라온 논문)

(이 분야 논문이 있는 캐나다 밴쿠버의 British Columbia 대학 교수로 70년대 주로 활동한 S.L.G. Choi라는 분이 한국인일까요? 아닐 것 같긴 합니다만.)