[주말N수학] 4색 문제의 확장판 '하트비거의 추측'

2019.12.14 06:00
일러스트 김윤재
일러스트 김윤재

여러분은 안 풀리는 문제를 풀 때 어떻게 하나요? 수학자는 여러 각도로 문제를 생각해봅니다. 때로는 문제를 더 어렵게 바꿔보는데요, 그게 오히려 문제를 쉽게 해결하게 만들기도 하고 새로운 연구 주제를 탄생시키기 때문입니다. 이번 호에 소개할 ‘하트비거의 추측’ 역시 4색 문제를 어렵게 만들다 나왔습니다.

 

그래프 이론에서 가장 유명한 문제를 꼽자면 단연 ‘4색 문제’입니다. 4색 문제는 평면에 그린 지도에서 이웃한 나라의 색을 다르게 칠할 때 나라가 아무리 많아도 4색만 있으면 된다는 걸 증명하는 문제입니다. 


1852년 영국의 대학생이던 프랜시스 구드리가 처음 질문한 이래로 많은 수학자가 도전했고, 1970년대에 미국 일리노이대학교의 두 교수 케네스 아펠과 볼프강 하켄이 해결했습니다. 


하지만 아직 컴퓨터를 사용한 증명만 있어서 컴퓨터를 쓰지 않은 증명을 고민하는 수학자가 많습니다. 4색 문제처럼 어려운 문제를 풀기 위해서 수학자는 다양한 방법으로 고민합니다. 특히 원래 문제를 변형해 더 어렵고 추상적인 문제로 만들어서 생각하는 것을 즐깁니다. 군더더기를 제외하고 문제의 핵심만 남겨 일반화해 더 어려운 상황을 만들면 그 덕분에 문제가 해결되는 경우가 있기 때문이죠. 많은 경우 이런 과정을 거치다가 새로운 수학 연구 주제가 생깁니다.

 


4색 문제 풀다 탄생한 하트비거의 추측


4색 문제가 풀리기 전인 1943년 스위스의 수학자 휴고 하트비거 역시 4색 문제를 어떻게 하면 더 일반화할 수 있을지 고민했습니다. 그 과정에서 ‘하트비거의 추측’도 나왔죠. 이번 호에서는 하트비거의 추측을 먼저 설명하고, 이 추측에 어떤 새로운 소식이 있는지 전하고자 합니다.
4색 문제는 그래프에 관한 문제로 바꿀 수 있습니다. 그래프란 꼭짓점과 두 꼭짓점을 잇는 선으로 구성된 수학적 대상입니다. 꼭짓점의 집합 V와 V의 원소 두 개로 구성한 선을 모아놓은 집합 E의 순서쌍 (V, E)로 정의합니다. 


지도의 각 나라마다 꼭짓점을 그리고, 두 나라가 국경을 맞대고 있으면 두 꼭짓점 사이에 선을 연결해서 그래프를 그릴 수 있습니다. 이때 선을 잘 그리면 서로 다른 두 선이 서로 교차하지 않게 지도에 나타낼 수 있습니다. 이처럼 서로 다른 두 선이 교차하지 않도록 평면에 그릴 수 있는 그래프를 ‘평면 그래프’라고 부릅니다.


이제 4색 문제를 그래프의 언어로 바꿔봅시다. 원래는 나라에 색칠했지만, 이제는 그래프의 꼭짓점에 색칠합니다. 이웃한 나라는 다른 색이므로, 선으로 연결한 두 꼭짓점도 다른 색이어야 합니다. 이렇게 바꾸면 이 문제는 그래프의 꼭짓점을 칠하는 채색 문제가 됩니다. 선으로 연결한 두 꼭짓점끼리는 다른 색이 되도록 색을 칠할 때 필요한 색의 수의 최솟값을 그 그래프의 ‘채색수’라고 부릅니다. 

 

 

하트비거의 추측을 풀자면 자연스럽게 평면 그래프의 성질에 대해 생각해야 합니다. 꼭짓점이 n개고, 그 n개 꼭짓점의 사이에 모든 가능한 선 \frac{n(2-1)}{2}개가 다 있는 그래프를 ‘완전그래프’라고 하고 K_{n}이라고 부릅니다. 그림을 그려보면 K_{3}, K_{4}까지는 교차점 없이 쉽게 그릴 수 있지만, K_{5}부터는 평면에 교차점 없이 그리기가 어렵습니다. 실제로 5개의 꼭짓점과 10개의 선으로 이뤄진 K_{5}는 평면 그래프가 아님이 수학적으로 증명돼 있습니다. 또그래프 일부에 K_{5}가 있다면 전체 그래프가 평면 그래프일 수 없다는 사실을 쉽게 알 수 있습니다. 


어떤 그래프가 평면 그래프인지 아닌지를 쉽게 알 수 있는 방법이 있습니다. 선을 ‘축약’해 평면 그래프의 성질을 유지하면서 좀 더 간단한 형태의 그래프로 만드는 것입니다.

 

① 선을 지운다. 평면 그래프에서 선 하나를 빼도 여전히 평면에 교차점 없이 그릴 수 있다.

② 선을 ‘축약’한다. 선으로 연결된 두 꼭짓점을 하나로 합치는 작업으로, 선을 고무줄이라고 상상하고 선의 길이를 점점 줄여서 0이 됐을 때 두 꼭짓점이 합쳐진 새 그래프를 상상하면 쉽다. 
③ 선이 연결돼 있지 않은 꼭짓점을 지운다. 

 

 

어떤 그래프 G에서 위 작업을 거쳐 다른 그래프 H가 얻어지면 ‘H는 G의 마이너’라고 합니다. 마이너 정의를 이렇게 한 덕분에 평면 그래프의 마이너는 항상 평면 그래프임을 쉽게 알 수 있죠. K_{5}는 평면 그래프가 아니므로, K_{5}마이너가 있다면 평면 그래프가 될 수 없습니다. 여기서 하트비거는 다음과 같은 추측을 만들었습니다.

 

 

1943년 제기된 이 추측은 아직 완전히 미해결입니다. 이 추측에서 t가 4 이하일 때는 매우 쉽게 증명됩니다. t=5일 때는 평면 그래프를 모두 포함하므로 4색 문제 역시 포함합니다. 더욱이 1937년 독일의 수학자 클라우스 와그너가 박사 졸업 논문에서 4색 문제가 참이면 K_{5} 마이너가 없는 그래프의 채색수는 4 이하라는 것을 증명해 t=5일 때 하트비거의 추측을 푸는 것은 4색 문제를 푸는 것과 같습니다.


t=6일 때는 한동안 미해결이었다가 1993년에 닐 로버트슨, 폴 시모어, 로빈 토마스 이렇게 세 명의 수학자가 4색 문제가 참이면 t=6인 경우도 성립한다는 것을 증명합니다. 하지만 t가 7 이상일 때는 아직 아무도 답을 알지 못합니다. 그래서 하트비거의 추측은 그래프 이론 분야에서 가장 어려운 미해결 문제 중 하나로 잘 알려져 있습니다.


필자 역시 이 문제와 관련한 연구를 필자의 대학원생인 강동엽 학생과 김재훈 KAIST 수리과학과 교수, 그리고 폴 시모어 미국 프린스턴대학교 교수와 그의 대학원생이던 캐서린 에드워즈 박사와 함께 진행해, 2015년 논문을 출판했습니다. 논문에서 K_{t} 마이너가 없는 그래프의 꼭짓점 각각을 t-1개 색으로 잘 칠하면 각각의 꼭짓점에 연결된 같은 색의 꼭짓점 수가 어떤 함수 f(t) 이하가 되게 하는 함수 f(t)가 있다는 것을 증명했죠. f(t)=0이라면 하트비거의 추측을 푼 것이니 매우 좋겠지만, 저희가 증명한 f(t)는 t^{2}logt에 비례하는 수준이었습니다 


한편 K_{t} 마이너가 없는 그래프의 채색수가 t에 관한 어떤 함숫값 이하인지 증명하는 연구가 있습니다. 1980년대에 K_{t} 마이너가 없는 그래프의 채색수는 항상 ct\sqrt{logt} 이하가 되는 상수 c가 있다는 연구 결과가 있었지만 30년이 다 돼가는 지금도 이 결과를 크게 개선한 결과가 없었습니다.


참에 더 가까워진 하트비거의 추측

 

 

그런데 지난 10월 기초과학연구원 이산수학그룹을 방문한 쑹쯔샤 미국 센트럴플로리다대학교 교수로부터 놀라운 소식을 들었습니다. 9월에 쑹 교수가 세르게이 노린 캐나다 맥길대학교 교수와 함께 연구해 30년 다 돼가는 결과를 개선했다는 겁니다. 이 연구 결과를 담은 논문은 10월 21일 인터넷 논문 공개사이트인 아카이브에 공개됐습니다.

 

이 논문에서는 K_{t}마이너가 없는 그래프의 채색수가 항상 ct(logt)^{0.354}이하가 되는 상수 c가 있다는 것을 증명했습니다. 제곱근은 0.5제곱과 같으므로 이 결과는 0.5를 0.354로 낮추는 데 처음으로 성공한 겁니다. 


그동안 몇몇 학자는 하트비거의 추측이 틀린 것이 아닌지, 애초에 ct(logt)^{}가 최적인 것이 아니냐고 추측하기도 했는데, 이번 연구 결과가 이런 억측을 불식시킨 거죠. 


그런데 11월 4일 아카이브를 보던 쑹 교수는 깜짝 놀랐습니다. 그새 0.354를 0.25로 낮춘 연구가 올라왔기 때문입니다. 루크 포슬 캐나다 워털루대학교 교수는 노린 교수와 쑹 교수의 연구 결과를 읽고, 논문에 사용된 기술 하나를 개선해 이 같은 결과를 얻었습니다. 결국 세 수학자는 두 논문을 합쳐서 하나로 만들기로 합의했습니다. 


다음으로 도전해야 할 주제로는 logt를 아예 없애서 ct 이하라는 것을 증명하는 겁니다. 이 역시 여러 수학자가 ‘이거라도 풀어보자’며 1990년대부터 추측으로 제기했던 문제인데 아직 실마리조차 없는 상태입니다. 이번 새로운 결과에 사용된 방법을 토대로 새로운 돌파구가 열리지 않을까 기대해봅니다.  

 

 

참고자료

세르게이 노린, 쑹쯔샤 ‘Breaking the degeneracy barrier for coloring graphs with no Kt minor’, 영문 위키백과 ‘하트비거 추측’
 

※필자소개

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

 

관련기사

수학동아 12월호 [엄상일 교수의 따끈따끈한 수학] 4색 문제의 확장판!  하트비거의 추측

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

댓글 0

작성하기

    의견쓰기 폼
    0/150