램지수에 관한 Burr와 Erdős의 추측

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의 추측을 해결한 것이지요. 축하합니다.

2015년 9월 KIAS 조합론 워크샵에서 강연중인 이중범 박사
2015년 9월 11일 양평에서 열린 KIAS 조합론 워크샵에서 강연중인 이중범 박사

옥스포드대학 데이비드 콘론 교수

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

David Conlon
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 에서 미리 확인할 수 있는데, 지금까지 연구 결과를 잘 정리함과 동시에 앞으로 이 분야의 연구가 나아갈 방향도 제시하는 좋은 논문입니다. 관련 분야에 전문적인 관심이 있는 독자들에게 일독을 권합니다.

하트비거(Hadwiger)의 추측과 그 특수경우

Hugo Hadwiger (Pictures from Oberwolfach Photo Collection, CC-BY-SA-2.0-de)
Hugo Hadwiger (Pictures from Oberwolfach Photo Collection, CC-BY-SA-2.0-de)

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

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

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

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

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

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

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

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

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

이제 하트비거 추측을 약하게 만든 새로운 문제를 생각해보자. 하트비거의 추측이 맞다면 Kt+1마이너가 없는 그래프의 꼭지점 집합을 항상 t개의 꼭지점 집합 X1,X2, .., Xt로 잘 나눠서 각 X1,…,Xt 안에는 변이 하나도 포함되지 않게 할 수 있다. 그러면 혹시 잘 나눠서 각 Xi 안에서 각 꼭지점은 Xi 안에서는 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살일 때가 되겠다.

수학을 사랑한 아이 책 표지
2013년에는 에르되시에 관한 그림동화책도 한글로 번역되어 출판되었다.

예를 들어 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라는 분이 한국인일까요? 아닐 것 같긴 합니다만.)

잘 짜인 동아리 (Generalized Steiner System)

전체 $n$명의 사람이 있는 학교에서 $q$명의 학생들로 구성된 동아리들이 있다고 한다. 그런데 아무렇게나 $r$명의 학생을 모아도 그 $r$명이 동시에 속한 동아리의 수는 정확히 $\lambda$로 똑같다고 한다. 과연 $n$, $q$, $r$, $\lambda$ 값이 어떤 경우에 이런 식으로 동아리들을 구성할 수 있을까?

$i\le r$인 어떤 수 $i$에 대해, 학생 $i$명의 집합 $Z$를 생각해보자. 이 집합 $Z$의 학생을 동시에 포함한 $r$명의 학생의 집합$Y$는 정확히 $\binom{n-i}{r-i}$개가 있으므로, 집합 $Z$의 학생을 동시에 포함한 동아리 $X$가 있을 때 $(X,Y)$의 순서쌍의 수는 정확히 $\lambda\binom{n-i}{r-i}$가 된다. 반대로, $Z$를 포함한 동아리 $X$에 대해 위의 조건을 만족하는 $Y$의 수는 $q-i$명에서 $r-i$명을 뽑는 수와 같으므로 $\binom{q-i}{r-i}$이다. 모든 $Z$를 포함하는 동아리에 대해 위 성질이 성립하므로 \begin{equation}\text{모든 $0\le i\le r$에 대해 $\binom{q-i}{r-i}$는 $\lambda\binom{n-i}{r-i}$의 약수}\label{eq:st} \end{equation}여야 한다.

그럼 조건 \eqref{eq:st}을 만족하는 모든 $n$, $q$, $r$, $\lambda$가 있다면 저런 식으로 동아리를 반드시 짤 수 있을까?

이 문제는 조합론 분야에서 정말 오래된 난제 중 하나이다. $r=2$일 때 이러한 식으로 동아리를 짤 수 있냐 물어보는 문제를 Steiner System이라고 하고, 일반적인 $r$에 대해서는 Generalized Steiner System이라고 한다. 이 문제는 무려 1800년대 중반까지 역사가 거슬러갈 정도로 조합수학 분야에서 정말 오래된 난제 중에 하나인데, 올해 초 이 분야 연구자들을 깜짝 놀라게 한 연구결과를 옥스포드 대학 Peter Keevash 교수가 발표하였다. (arxiv에 올라온 논문)

정리 (Keevash 2014): 모든 $n$, $q$, $r$, $\lambda$가 조건 \eqref{eq:st}을 만족하며 $n$이  충분히 크다면 위와 같은 식으로 동아리를 짜는 것이 가능하다.

Peter Keevash 교수
Peter Keevash 교수 (2003년에 Banff 워크샵 갔을때 만나서 찍었던 사진)

Steiner System에 관한 연구의 역사는 1800년대 중반 수학자들 Plücker (1835년), Kirkman (1846년), Steiner (1853년)로 거슬러 올라간다.  $r=2$인 경우에는 이 문제는 1970년대  칼텍의 Richard M. Wilson 교수가 $n$이 충분히 크면 참이라고 증명하였다.  일반적인 $r$은 아직까지 미해결로 남아있었다.

2014년 6월 미국 미니애폴리스에서 열린 SIAM Conference on Discrete Mathematics라는 학회에서는 긴급하게 “Hot Topic Session”이라는 이름으로 저녁 8시에 Peter Keevash 교수를 초청해서 이 결과에 대한 강연을 듣는 자리가 있었다. 보통 이런 학회의 초청강연자 명단은 몇 달 전에 잡히기 때문에 초청강연자로 하기에는 너무 늦은 상황이지만 결과가 매우 중요하기 때문에 이렇게 늦게 시간을 잡았다고 한다.

이 문제의 해법은 확률론적 방법을 사용하는데 Keevash 교수는 그것을 “Randomized Algebraic Construction”이라고 부른다. 앞으로 이러한 방법이 다양한 문제를 해결하는데 큰 도구가 될 것으로 생각된다.

영국 출신인 Peter Keevash 교수는 프린스턴대학에서 Benny Sudakov 교수 지도 하에 2004년에 박사학위를 받았다. 올 봄에 만났을 때, 어떻게 이 문제에 관심을 가지고 해결하게 되었냐 물어보니, 칼텍에서 박사후 연구원을 할 때 Richard M. Wilson 교수로부터 이 문제를 잘 알게 되었고 그 후 다른 연구를 하면서도 이 문제에 대하여 항상 관심을 가지고 있었다고 한다.

안녕하세요!

이산수학, 조합수학, 그래프이론 연구자들 몇 명이 모여서 흥미로운 최신 연구 결과나 미해결 문제를 한국어로 소개하는 블로그를 만들었습니다.  앞으로 많은 관심 부탁드립니다.