[주말N수학]그래프 꼭짓점을 서로 다른 색으로 칠할 때 최소수

2019.08.31 20:37

 

채색수가 2,3,4인 그래프
채색수가 2,3,4인 그래프

선으로 연결된 그래프의 꼭짓점을 서로 다른 색으로 칠할 때 필요한 최소수를 ‘채색수’라고 합니다. 그동안 수학자들은 꼭짓점이 n개인 그래프들의 채색수가 평균적으로 어떤 값 근처에 있는지 연구해 왔습니다. 하지만 채색수가 평균 주변에 얼마나 좁게 모여 있는지는 오랫동안 미해결 문제였습니다. 그런데 최근 영국 옥스퍼드대의 수학자가 이를 해결했다고 발표했습니다. 

 

그래프 색칠하기의 대표 문제는 ‘4색 정리’입니다. 평면에 그린 지도는 어떤 지도든 이웃한 영역을 다른 색으로 칠할 때 4개 이하의 색이면 충분히 지도를 색칠할 수 있다는 겁니다. 평면의 영역을 꼭짓점으로 나타내고, 이웃한 영역에 대응하는 두 꼭짓점 사이를 선으로 이어서 그래프를 만들면 평면에 교차점이 하나도 없는 ‘평면 그래프’가 그려집니다. 이 그래프의 꼭짓점에 색을 잘 칠하면 선으로 연결된 이웃한 꼭짓점이 서로 다른 색이 되도록 모든 꼭짓점을 4개 이하의 색으로 칠할 수 있다는 겁니다.

 

만에 하나 그래프에 교차점이 있다면 어떨까요? 꼭짓점이 n개라면 채색수는 최대 n입니다. 모든 두 꼭짓점이 서로 이웃하면 같은 색을 전혀 쓸 수 없으니 채색수가 n이 됩니다.

 

확률과 그래프이론의 결합! 무작위 그래프 


1950년대 말 헝가리 수학자 에르되시 팔과 레니 얼프레드는 처음으로 그래프이론과 확률을 결합한 연구를 시작합니다. 예를 들어 앞면이 나올 확률이 p, 뒷면이 나올 확률이 1-p인 동전이 있고 꼭짓점이 n개 있을 때, 꼭짓점 두 개의 쌍마다 동전을 던져 앞면이 나오면 그 두 꼭짓점을 선으로 이어 그린 그래프의 성질을 연구합니다. 이렇게 만든 그래프를 흔히 ‘무작위 그래프’ 또는 ‘에르되시-레니 무작위 그래프’라고 부릅니다.  


만약 동전의 앞면과 뒷면이 나올 확률이 똑같으면, 즉 p=\frac{1}{2}이면 무작위 그래프는 각각의  꼭짓점을 1, 2, …, n으로 표시한 모든 그래프에서 같은 확률로 그래프 하나를 뽑는 것과 같습니다. 그리고 꼭짓점이 n개인 그래프 대부분이 갖는 성질이 어떤 것인지 물어보는 문제와 같아집니다.
이런 무작위 그래프를 다룰 때는 정말 이상한 일이 많이 일어납니다. 비유하자면 우리가 일상적으로 생각하는 수는 보통 유리수지만, 사실 실수 중에 아무 수나 뽑는다면 확률 1로 그 수는 무리수입니다. 마찬가지로 꼭짓점 n개인 그래프도 매우 많다 보니 ‘아주 높은 확률로 무작위 그래프는 어떤 성질을 갖는다’는 겁니다. 


현재 무작위 그래프 관련 연구는 하나의 학문 분야라고 할 만큼 발전했고 수학자, 물리학자, 전산학자 등 많은 연구자가 다루고 있습니다.


현재 영국 케임브리지대에서 같이 교수로 있는 제프리 그리메트와 콜린 맥더미드는 박사과정도 영국 옥스퍼드대에서 같은 시기에 밟았습니다. 그 시절 두 사람은  p=\frac{1}{2}일 때 c를 매우 작은 양수 중 어떤 값으로 하더라도, 꼭짓점 수가 n개인 무작위 그래프의 채색수가 \frac{n}{2log_{2}n}(1-c)보다 클 확률이 n이 커질 때 1로 수렴한다는 것을 증명했습니다. 다시 말해 꼭짓점 n개인 그래프를 아무거나 하나 고르면, n이 충분히 클 때 99.99% 이상 그 그래프의 채색수는 \frac{n}{2log_{2}n}(1-c)보다는 크다는 겁니다.


1974년에 작성한 이 논문은 1975년 영국 케임브리지대에서 출판하는 수학 학술지에 실렸습니다. 하지만 채색수가 저 식보다 훨씬 더 크지 않다는 것까지 증명하지는 못했습니다. 그래서 n이 충분히 크면 대부분의 채색수가 \frac{n}{2log_{2}n}(1+c)보다 작을까’라는 질문을 논문에 적어뒀습니다.

 

무작위 그래프의 채색수


이 질문은 10여년이 지난 1987년에 헝가리 수학자이자 케임브리지대의 교수였던 볼로바스 벨라가 해결했습니다. 즉 c값이 아무리 작더라도, n만 충분히 크면 꼭짓점이 n개짜리 그래프의 99.99% 이상은 다 채색수가 \frac{n}{2log_{2}n}(1-c)\frac{n}{2log_{2}n}(1+c)사이에 있다는 것이지요. 볼로바스의 결과에 의하면 대부분의 그래프의 채색수는 2c\frac{n}{2log_{2}n}길이를 갖는 구간에 들어갑니다. 


이후에도 여러 수학자가 꼭짓점 n개인 무작위 그래프의 채색수 대부분이 모여 있는 구간을 더 정밀하게 좁히려는 연구를 진행했습니다. 2016년 영국 옥스퍼드대의 박사과정생이던 아니카 헤켈은 채색수를 훨씬 더 좁은 구간에 가두는 데 성공합니다. 즉 기존의 결과보다 그 구간의 폭을 로그함수로 한 번 더 나눈 것만큼 좁힙니다.  c를 아무리 작게 잡아도 같은 결과가 성립하므로 꼭짓점 n개 그래프 대부분의 채색수가 들어가는 구간의 길이를 함수로 쓴다면 그 함수는  \frac{n}{log{_{2}}^2{}n}보다 느리게 증가한다는 식으로 말할 수 있습니다.


그런데 사실 채색수가 포함된 구간이 구체적으로 무엇인지 증명하지 못했어도 그 구간의 폭이 매우 짧다는 것을 증명한 논문은 이미 나와 있었습니다. 1987년 엘리 샤미르와 조엘 스펜서는 꼭짓점이 n개인 그래프의 대부분의 채색수는 길이가 \sqrt{n}에 비례하는 구간 안에 들어간다는 것을 증명합니다. 이 \sqrt{n}은  \frac{n}{log{_{2}}^2{}n}보다는 훨씬 느리게 증가하는 함수입니다. 이 결과는 나중에 이스라엘의 수학자 노가 알론이 ​\frac{\sqrt{n}}{log{_{2}}n}으로 더 줄이기까지 합니다.


하지만 이때까지도 이 폭이 무한정 줄어들 수 있는지 없는지 아무도 몰랐습니다. 에르되시와 볼로바스 등 여러 이 분야 연구자들이 이게 가능한지 불가능한지 질문했습니다. 왜 이런 질문이 오랫동안 관심을 끌었는지 이해하려면 p가 다른 값일 때 나온 놀라운 결과를 살펴봐야 합니다. 

 

샤미르와 스펜서는 1987년에 p가 n에 관한 함수 p(n)이고 ε이 0보다는 크지만 아주 작은 상수라고 할 때 p(n)<\frac{1}{n}n^{\frac{1}{6}-\varepsilon }이라 이 p로 만드는 무작위 그래프의 채색수는 매우 높은 확률로 5개 중 하나라는 것을 증명합니다. 이런 식으로 채색수의 99.99% 이상이 고작 5개, 3개, 2개에 집중된 경우에 관한 연구는 여럿 나와 있었습니다. 하지만 p가 다른 값일 때 채색수가 이렇게 몇 개 값에 몰려 있지는 않다는 연구 결과가 나온 것은 이제까지 없었습니다.

 

확률 p에 따라 다른 채색수 성질


그런데 2019년 6월 말 인터넷 논문 공개 사이트인 아카이브(arXiv)에 바로 이런 결과를 처음으로 증명한 논문이 올라왔습니다. 이 논문을 쓴 사람은 바로 헤켈입니다. 2016년에 p=\frac{1}{2}일 때 무작위 그래프의 채색수가 어떤 구간에 몰려 있는지를 증명했던 바로 그 사람입니다. 


이 논문에서는 0<c<\frac{1}{4}인 경우에는 꼭짓점이 n개인 그래프의 채색수 대부분이 몰려 있는 구간을 아무리 좁게 잡더라도 그 구간의 폭이 n^{c}보다 작게 잡을 수는 없다는 것을 증명했습니다. 정확하게 말하자면, 아주 높은 확률로 꼭짓점이 n개인 무작위 그래프의 채색수가 s_{n} 이상 t_{n}이하가 되는 수열이 있다면,  t_{n}-s_{n}\geq n^{c}가 되는 n이 있다는 것을 증명했습니다. 


이 결과가 검증되려면 시간이 걸리겠지만, 맞는 것으로 확인된다면 p=\frac{1}{2}인 무작위 그래프의 채색수가 아주 좁게 몰려 있을 수는 없다는 것을 증명한 첫 논문이 되겠습니다. 


생각해보면 참 신기합니다. 그래프의 채색수는 1부터 n까지의 수가 모두 가능한데도 대부분의 채색수는 특정 값 주위에 모여 있으며, 그런데도 아주 강하게 모여 있지는 않아서 대부분의 채색수 값이 있는 구간을 잡으려면 그 폭이 어느 정도 이상은 돼야 한다는 것이니까요. 앞으로 무작위 그래프에 대해 또 어떤 흥미로운 결과가 나올 수 있을지 궁금합니다

 

참고자료

-아니카 헤켈 ‘Non-concentration of the chromatic number of a random graph’,
-아니카 헤켈 박사 홈페이지 www.maths.ox.ac.uk/people/annika.heckel

 

관련기사

수학동아 8월호 [따끈따끈한 수학] 그래프 채색수의 성질을 밝혀라!

 

※필자소개

엄상일 교수. KAIST 수학과를 졸업하고, 미국 프린스턴대에서 박사 학위를 받았다. 현재 기초과학연구원과 KAIST에서 연구와 강의를 하고 있다. 그래프이론과 이산수학, 조합적 최적화가 주요 연구 분야다. 2012년에는 젊은과학자상(대통령상)을 수상했고, 2017년에는 한국차세대과학기술한림원 회원으로 선정됐다.
 

 

메일로 더 많은 기사를 받아보세요!

댓글 0

작성하기

    의견쓰기 폼
    0/150