d라이브러리

기초과학연구원(IBS)은 세계 수준의 기초과학 연구를 위해 2011년 설립된 연구기관입니다. IBS 설립 10주년을 맞아 수학동아는 IBS 수학자들의 연구와 삶을 소개하는 시리즈 <;나의 삶, 나의 수학>;을 연재합니다. 첫 번째로 점과 선을 그려 그래프를 그리듯 전 세계의 많은 수학자와 교류하며 그린 엄상일 CI의 수학 인생 그래프를 살펴봤습니다.

Q 처음 수학에 관심이 생겼던 때를 기억하시나요?

어릴 때만 해도 사실 저는 컴퓨터를 좋아했어요. 조등학교 6학년 때 고향인 경상북도 예천에 처음으로 컴퓨터 학원이 생겨서 다니게 됐습니다. 코딩 언어를 배워 사칙연산 하는 프로그램을 만들었는데, 분수를 연산할 때는 약분하거나 분모를 같게 만드는 통분을 해야 했어요. 그래서 최대공약수를 구해야 했는데 BASIC이라는 코딩 언어에는 최대공약수를 구하는 명령어가 없었어요. 그래서 유클리드 호제법으로 최대공약수를 구하는 코드를 만들었더니 분수 계산이 빨라졌습니다. 이런 경험이 여러 번 쌓이다 보니 수학에도 자연스럽게 관심이 생겼죠.

Q 그 뒤엔 어떻게 수학자의 길을 걷게 되셨나요?

수학을 좋아하긴 했지만, 대학교를 진학할 때까지만 해도 컴퓨터를 전공하고 싶었어요. 하지만 제 마음 어딘가에 수학을 선망하는 마음이 있었던 것 같아요. KAIST는 입학 후 학과 선택을 자유롭게 할 수 있어서 여러 선배님을 만나보고 수학과로 진학하게 됐습니다. 하지만 여전히 컴퓨터를 좋아해서 컴퓨터 동아리 회장도 하고 대학교 졸업 후 컴퓨터 프로그래머로 3년간 일하기도 했습니다. 그 결과 수학과 컴퓨터 알고리듬을 모두 다룰 수 있는 수학자가 됐죠.

Q 가장 기억에 남는 연구가 있다면요?

주제가 정해진 뒤 바로 그날 해결해 논문을 쓴 연구도 기억에 남긴 하지만, 반대로 2014년부터 6년 동안 했던 연구가 가장 기억에 남습니다. 김은정 프랑스 국립과학연구센터(CNRS) 박사, 그리고 제 지도 학생이었던 정지수 KAIST 수리과학부 박사와 함께하던 연구였는데요, 회의하면서 해법을 찾았다가도, 헤어지기 직전에는 큰 오류가 나왔어요. 그럼 뿔뿔이 흩어진 채로 연구를 하다가 또 함께 모였을 때 오류를 해결했죠. 시간이 조금 지나면 또 다른 오류를 발견하는 일이 많았어요. 이 과정을 여러 번 반복하다 보니 어느샌가 결과물이 나와 있었지요. 이렇듯 수학 문제엔 희로애락이 있어요.

이 연구는 복잡하지만 잘 될 것으로 믿고 몇 년을 투자했는데, 어느 날 큰 충격에 빠졌습니다. 알고 보니 처음 이 연구를 시작하게 된 계기가 됐던 수식이 틀렸었고 그걸로는 문제가 해결되지 않는다는 것을 알게 된 것이죠. 하지만 몇 년을 한 문제에 매달린 탓일까요? 그 문제에 대한 직관이 훨씬 더 좋아져서 문제를 해결하는 다른 방법을 결국 찾아냈습니다. 결국, 50쪽과 73쪽짜리 논문 2편을 완성할 수 있었습니다.

Q 가장 힘들었던 순간은 언제였나요?

미국 프린스턴대학교에서 박사과정을 밟던 2003~2004년이에요. 연구에 진전이 없어서 힘들었죠. 과학 분야라면 어떤 실험에 실패해도 새롭게 발견된 내용으로 논문을 쓸 수 있지만, 수학은 새로운 사실을 찾고 완벽하게 증명해야 해서 힘들었습니다. 제 지도교수님이신 폴 시모어 미국 프린스턴대학교 수학과 교수님은 이 분야의 대가라 높은 눈높이를 가지고 계셔서 더욱 힘들기도 했고요. 그래서 힘든 순간이 찾아올 때마다 평소처럼 일을 계속하려고 노력했어요. 꾸준히 노력했더니 결국엔 문제가 해결됐죠.

Q IBS 합류 후에 달라진 점이 있다면요?

무엇보다 같은 수학 문제를 두고 얘기를 나눌 연구원이 많아졌다는 점입니다. 보통 대학에서 연구원을 뽑으려면 교수 개인이 연구비와 절차를 모두 준비해야 하는데, IBS에서는 도와주시는 분들이 많아 그 부담을 덜 수 있어요. 덕분에 전 세계에서 모인 10명의 훌륭한 연구원과 함께 논의하며 연구하고 있습니다.

Q 수학이란 무엇인가요?

한편으로는 맞추기 힘든 퍼즐 같지만, 나름의 아름다움도 있어요. 그래서 풀었을 때의 희열감이 크죠. 문제를 풀면서 수학자들끼리 많은 교류를 하는데 이때의 즐거움도 수학의 한 부분입니다. 함께 고민하면서 서로의 고충을 공감할 수 있죠.

독자분들은 수학이 무엇이라고 생각하나요? 정답을 구하는 것이 수학의 목적이라고 생각할 수도 있을 것 같아요. 하지만 수학 연구를 하면서 인간 지성의 한계를 시험하는 새로운 추측을 만들고 생각지도 못한 방법을 떠올려서 해결하면 그 즐거움은 이루 말할 수 없지요. 이때 발견한 새로운 방법은 다른 연구 분야에도 적용할 수 있을 뿐 아니라 분야끼리 묶어 또 다른 연구 분야를 만들어낼 수도 있어요.

Q 어떤 수학자로 기억되길 바라나요?

올해 아벨상을 수상한 로바스 라슬로 헝가리 부다페스트대학교 명예 교수가 10년 전 이런 말을 했습니다. “수학 분야가 그 응용 분야와 함께 발전하는 시기에 그 분야에서 연구할 수 있어서 매우 운이 좋았습니다. 물리학과 해석학 분야가 17세기부터 19세기까지 함께 발전한 것처럼 컴퓨터 과학과 이산수학이 완전히 함께 성장해 왔어요.”

이처럼 이산수학분야는 수학의 중심 연구 분야로 인정받은 지 얼마되지 않았지만, 컴퓨터 과학과 함께 급속하게 발전하고 있어요. 아직도 다른 수학 분야와 비교하면 역사가 짧은 만큼 좋은 연구를 해서 오래 기억되는 수학자가 되고 싶습니다.

[수학자의 연구노트] 

내 수학 인생을 바꾼 단 하나의 연구

제가 하던 수학 연구는 길게는 수년, 짧게는 수일 만에 완성되기도 했습니다. 그중 독일의 한 소도시에서 했던 연구는 하루 만에 답을 얻었습니다. 그래프 알고리듬 분야에서 유명하신 브루노 쿠르셀 프랑스 보르도컴퓨터과학연구소(LaBRI)교수님과 만났던 2004년 5월의 일입니다.

2004년 5월 25일 화요일, 아침 식사를 하는데 쿠르셀 교수님이 오시더니 수십 장의 A4 용지에 손으로 쓰신 증명을 보여주며 말했습니다. “어제 너와 논의한 내용을 다 썼으니 이따 쉬는 시간에 함께 검토해보자” 무슨 일이 있었던 것일까요?

박사 학위를 향한 마지막 한 문제

2002년 가을, 미국 프린스턴대학교에서 대학원 2년차가 됐을 때입니다. 그래프 이론과 알고리듬 모두 좋아하는 제 성향을 파악한 지도교수인 폴 시모어 미국 프린스턴대학교 수학과 교수님은 박사 학위 주제로 그래프의 ‘클리크 너비(clique-width)’가 k 이하인지 다항식 시간 안에 판별하는 알고리듬을 만들어보는 문제를 제안해 주셨습니다.

클리크 너비는 1993년 쿠르셀 교수님이 다른 두 교수님과 쓴 논문에서 처음 소개된 개념으로 그래프가 얼마나 트리 구조로 잘 분해되는지 그 정도를 보여주는 값입니다.

쿠르셀 교수님은 2000년 쿠르셀 정리를 클리크 너비에 대해 확장한 것으로 유명합니다. 어떤 문제를 ‘단항 이차 논리’라는 논리식으로 표현할 수 있다면, 클리크 너비가 작은 그래프에서는 적은 수의 색만 써서 위의 연산으로 그 그래프를 표현할 방법이 있을 때 문제가 참인지를 빠르게 판별할 수 있는 알고리듬을 만들 수 있다는 내용입니다.

하지만 쿠르셀 정리의 전제가 되는 클리크 너비가 비교적 작은 그래프에서 그 그래프를 적은 수의 색깔만 써서 연산으로 표현하는 방법을 찾는 데 문제가 있었습니다. 짧은 다항식 시간 안에 그런 걸 하는 알고리듬이 없었기 때문이죠. 따라서 남아있는 박사과정 동안, 이 알고리듬이 가능할지 알아보고 가능하다면 직접 이 알고리듬을 만들기로 했습니다. 곧 지도 교수님과 함께 클리크 너비와 똑같은 성질을 가지면서도 더 간단하게 그래프의 복잡도를 나타낼 수 있는 ‘랭크 너비(rank-width)’라는 개념을 생각해냈습니다. 이를 이용해 클리크 너비 범위에 대한 문제를 랭크 너비에 대한 문제로 바꿔 풀 수 있었습니다.

우연히 가게 된 독일 닥스툴 워크숍

그러다가 쿠르셀 교수님을 직접 뵐 기회가 생겼습니다. 그래프 이론 분야의 또 다른 수학자인 안드레아스 브란츠테트 독일 로스토크대학교 교수님의 개인 홈페이지를 보다가 2004년 5월 23일부터 1주일간 독일 닥스툴에서 워크숍이 열린다는 걸 알게 됐거든요. 하지만 초청받은 사람만 워크숍에 참석할 수 있었기 때문에 다짜고짜 브란츠테트 교수님께 이메일로 초청해줄 수 있는지 물었는데 다행히 초청장을 받을 수 있었습니다.

마침 이 시기에 여러 가지로 운이 좋았습니다. 지도교수님도 “이제 포기하고 다른 문제를 해보면 어떠냐” 권할 정도로 한참 동안 연구에 진척이 없다가 갑자기 그해 봄부터 큰 진전이 생겼거든요. 
그래프의 랭크 너비가 엉뚱하게 조합론의 매트로이드(Mathorid) 이론과 연결된다는 걸 알게 된 이후부터였습니다. 매트로이드 이론은 행렬의 성질과 그래프의 성질을 통합해서 연구할 수 있는 대상이에요. 이를 연구한 논문에 적힌 방법들을 검토하다 보니 박사과정 때 풀어야 할 문제와는 거리가 멀어 보이지만, 랭크 너비에서도 재미있는 결과를 증명할 수 있었습니다. 

그중 하나가 1991년에 제기된 제제의 추측과 관련된 내용입니다. 당시 쿠르셀 교수님이 홈페이지에 공개한 최신 논문 중에 독일 수학자 데틀레프 제제의 추측에 관한 논문이 있었습니다. 제제의 추측은 ∧,∨,∈,∀,∃ 같은 기호를 써서 표현하는 ‘단항 이차 논리’로 표현된 논리식이 어떤 그래프 집합에서 항상 참인지 아닌지 판별해주는 알고리듬이 존재하려면, 논리식이 대응된 그래프 집합의 클리크 너비가 무한히 커질 수는 없다는 것이었습니다. 문제를 나타내는 논리식의 표현력이 약하면 항상 쉽게 답변할 수 있겠지만, 표현력이 강하면 너무 많은 질문을 표현할 수 있게 돼 대답하지 못하는 문제도 표현할 수 있게 됩니다. 제제의 추측은 단항 이차 논리로 제한하면, 절묘하게도 클리크 너비가 작을 때는 답을 할 수 있고 클 때는 답을 할 수 없는 경계가 생긴다는 추측입니다. 

쿠르셀 교수님은 그래프 꼭짓점 집합을 두 부류로 잘 나눠 한 부류에서 다른 부류로 가는 선만 있는 경우라면 제제의 추측이 해결된다는 것을 증명했습니다. 마침 하던 연구에서 그런 그래프에서는 랭크 너비를 매트로이드 이론과 연관 지을 수 있다는 것을 알게 됐습니다. 그리고서 불과 며칠 후에 워크숍에서 쿠르셀 교수를 만나 이야기할 수 있게 됐습니다.

쿠르셀 교수와의 공동 연구 

닥스툴에서 열린 워크숍은 공동 연구를 하기 좋은 방식으로 이뤄졌습니다. 오전에는 최신 연구결과를 듣고 오후에는 삼삼오오 모여서 함께 연구했죠. 워크숍 첫날 오전에는 강연이 있었고 오후가 돼서야 쿠르셀 교수님을 만났습니다. 쿠르셀 교수님에게 랭크 너비와 매트로이드 이론을 연결해 어떤 결과를 증명했는지 설명하고, 그것으로 제제의 추측을 얼마나 증명할 수 있을지 한참 논의했습니다.

곧 제제의 추측에서 문제를 표현하는 논리식에 어떤 집합의 원소 개수가 홀수인지 짝수인지를 묻는 것을 허용해 표현력을 조금 더 강하게 만들면, 제제의 추측이 참임을 증명할 수 있었습니다. 즉 단항 이차 논리식에 집합의 크기가 홀수인지 짝수인지 판별하는 것까지 가능하게 허용되면, 이런 식으로 표현 가능한 문제가 주어질 때 어떤 그래프 집합에서 그 논리식이 항상 참이 되는지 대답할 수 있다면 그 그래프 집합은 랭크 너비, 클리크 너비가 작다는 것을 증명한 거죠. 게다가 그래프의 랭크 너비가 k 이하인지 판별하는 다항식 시간 알고리듬까지 얻었습니다. 논의한 지 몇 시간 만에 제제의 추측을 살짝 약하게 만든 것을 증명했을 뿐 아니라 박사과정의 연구 주제까지 해결했던 것이지요. 박사과정 연구 주제와 제제의 추측은 겉으로 보기엔 다르지만, 본질적으로 같아서 하나를 풀었더니 다른 하나도 해결할 수 있었던 겁니다.

그래서 예정에 없이 그 워크숍 마지막 날 아침에 쿠르셀 교수님과의 새로운 연구결과를 짧게 발표했습니다. 워크숍 결과보고서에는 최대 연구 성과로 저와 쿠르셀 교수님의 공동 연구가 꼽혔죠. 이후 여름 내내 논문을 완성해 투고했고 2007년 논문이 조합론저널B에 출판됐습니다. 박사 학위 논문의 은 이때의 결과 덕분이라고 볼 수 있죠. 2010년 받은 대한수학회 논문상도 마찬가지고요. 망설이지 않고 먼 거리를 떠나 다른 나라의 수학자와 했던 소통이 수많은 성과로 나타났던 중요한 경험이었습니다. 코로나19로 다른 수학자와 해외 교류가 쉽지 않은 지금도 온라인으로 만나 끊임없이 논의하는 이유입니다.