50년 묵은 난제를 해결한 한국의 젊은 수학자

1972년 한 다과회에서 수학자 에르되시 팔은 동료 라슬로 로바스, 밴스 파버와 수학 문제 하나를 떠올렸다. 그래프이론과 관련된 간단한 명제였다. 세 수학자는 쉽게 증명해 낼 거라고 생각했다. 하지만 예상과 달리 이 문제는 수십 년 동안 풀리지 않았고, 그렇게 영원한 수학계 난제로 남는 듯했다.

50여 년이 흐른 2021년, 마침내 문제가 풀렸다. 수많은 수학자가 골머리를 앓았지만, 애석하게도 풀리지 않던 수학계 묵은 난제는 젊은 한국 수학자의 손에서 해결됐다. 박사학위를 받은 지 1년이 채 되지 않은 시점에 이뤄낸 놀라운 성과였다. 문제를 제시한 수학자 라슬로 로바스는 미국 수학과학 전문잡지 ‘콴타’를 통해 “아름다운 작품과 같다”며 “연구의 진전을 보게 돼서 기쁘다”고 밝혔다.

문제를 해결한 주인공은 강동엽 IBS 극단 조합 및 확률 그룹 차세대 연구리더(Young Scientist Fellow, YSF)다. 강 연구리더는 올해 6월, YSF로 IBS 극단 조합 및 확률 그룹에 합류했다. Young Scientist Fellowship은 는 IBS 차세대 연구리더 육성 프로그램으로, IBS가 젊은 수학자와 과학자들의 우수한 연구 성과 창출을 목표로 운영하고 있다.

지난 10월, 강 연구리더는 그간의 연구 성과를 인정받아 2023년도 대한수학회 상산젊은수학자상 수상자로 선정됐다. 이 상은 박사 학위를 받은 지 5년 이내의 젊은 수학자 중 수학 분야에 업적이 뛰어난 사람에게 수여하는 상이다. 매년 세 명이 선정된다.

50년 난제를 해결한 젊은 수학자 강동엽 연구리더를 만나 연구 배경에 대해 들었다.

자기소개 부탁드립니다.

강동엽 IBS 극단 조합 및 확률 그룹 차세대 연구리더입니다. KAIST에서 전산학과 수학을 전공하고, 2020년 KAIST 수리과학과에서 박사학위를 받았습니다. 지도교수님은 현재 같은 연구단에 있는 엄상일 IBS 이산수학 그룹 CI입니다. 박사학위를 받은 뒤에는 영국 버밍엄대학교에서 3년 동안 박사후연구원으로 있었고, 현재는 IBS 극단 조합 및 확률 그룹에서 연구하고 있습니다.

소속 연구단인 극단 조합 및 확률 그룹은 어떤 곳인가요?

홍 리우 IBS 극단 및 확률 조합 그룹 CI가 이끄는 연구그룹으로 2022년 3월 출범했습니다. 수리 및 계산 과학 연구단에 설립된 네 번째 연구그룹이죠. 극단 조합 및 확률 그룹에서는 극단 조합론, 확률론적 조합론, 이산 기하학 등의 연구를 수행하고 있습니다.

강 연구리더는 어떤 연구를 하고 계시나요?

극단 조합론과 확률론적 조합론을 연구하고 있어요. 극단 조합론은 제약 조건이 있는 상황에서 조합적 매개변수의 최적값을 찾는 분야입니다. 확률론적 조합론에서는 특정한 조합적 구조와 연계된 확률 공간을 연구합니다. 언뜻 관련 없어 보이지만, 두 분야는 상호보완적인 관계입니다. 예를 들어 극단 조합론에서 쓰는 방법론을 확률론적 조합론에 적용하는 식이죠.

이 분야가 진지하게 연구된 지는 약 100년 정도 됐습니다. 대수학, 정수론과 같은 고전적인 수학 분야보다는 최근 연구 분야죠. 컴퓨터가 발달하면서 연구가 활발해졌어요. 실생활 문제를 컴퓨터로 해결할 때, 수학을 이용해야 하는 경우가 많기 때문이죠.

연구 분야가 실생활에도 관련이 있다고요?

내비게이션을 이용해 최적의 경로를 탐색하는 것이 대표적입니다. 저희 연구 분야에서 주로 다루는 대상 중 하나가 그래프인데요, 그래프는 ‘꼭짓점(node)’과 그 사이를 잇는 ‘간선(edge)’으로 이뤄진 구조를 뜻합니다. 일반적으로 네트워크라고 말하는 것이죠. 내비게이션의 경우 지점은 점으로, 도로는 간선으로 표현해 알고리즘 문제로 바꾸는 것이죠.

구조적 그래프 이론은 특정 성질을 갖는 그래프의 알고리즘 문제와 관련이 있습니다. 확률론적 조합론은 무작위 알고리즘의 설계와 관련이 깊고요. 그래서 SNS 친구 추천, 포털사이트의 검색 등의 알고리즘을 설계할 때도 이런 수학 이론이 이용됩니다.

2021년 ‘콴타 매거진’에 강 연구리더의 연구가 소개됐습니다.

‘에르되시-파버-로바스 추측’을 유한개의 경우를 제외하고 증명하는 데 성공했습니다. ‘선형 하이퍼그래프가 N개의 꼭짓점을 가지면, 그 하이퍼그래프의 겹치는 간선들을 다른 색을 가지게끔 칠하는 데 필요한 색의 개수는 N 이하다’라는 명제입니다.

여기서 하이퍼그래프는 수학적으로 각 간선이 2개 이상의 꼭짓점을 포함할 수 있게 허용한 그래프입니다. 수학에서는 비교적 간단한 명제이기 때문에 쉽게 해결될 거로 생각했어요. 하지만 50여 년 동안 풀리지 않은 난제가 됐죠.

연구 주제는 보통 어떻게 선택하나요?

저는 즉흥적으로 연구 주제를 선택하는 편입니다. 그게 잘 맞기도 하고요. 보통 연구 주제를 선택하면 오랜 시간 지속해야 하니 주제에 충분히 매력을 느끼고 흥미가 있어야 하기 때문이죠. 주로 워크숍에 가서 소개된 문제에 관심을 갖기도 하고, 공동 연구자들에게 제안이 오기도 해요. 제가 먼저 제안할 때도 있고요.

그럼 ‘에르되시-파버-로바스 추측’ 연구를 시작하게 된 계기는 무엇인가요?

영국 버밍엄대 박사후연구원으로 있을 때였어요. 다니엘라 쿤 교수님과 데릭 오스투스 교수님이 멘토였는데요, 어느 날 두 분이 이 문제를 시도해 보자고 제안하셨어요. 사실 뜬금없었죠. 워낙 긴 시간 해결되지 않은 난제였으니 농담하신다고 생각했어요. 그런데 진심이었죠.

어려움이 많았을 것 같은데요?

결론부터 말하자면, 걱정했던 것만큼의 큰 어려움은 없었습니다. 처음 교수님들은 한 논문 결과를 이용하면 된다고 생각하셨어요. 막상 문제를 풀려고 보니 교수님들께서 착각하셨던 것이었죠. 사실 이런 일은 수학자들에게 흔한 일이에요.

우연은 여기서 시작됐어요. 당시 저와 버밍엄대 동료들이 연구하던 문제가 있었는데요, 아이러니하게 그 문제에 이용한 아이디어가 에르되시-파버-로바스 추측에 적용됐어요. 마침 팀에 그래프 이론의 채색 문제를 연구하던 연구원도 있었죠. 우연의 연속으로 좋은 팀이 만들어져, 추측을 반년 만에 해결할 수 있었습니다.

50년 된 난제를 반년 만에 해결했다고요?

제 연구경력에서도 손에 꼽히는 일이었어요. 수학 문제를 해결할 때 중간에 막히는 일은 빈번하죠. 막힌 부분을 해결하는 데는 일주일, 길게는 수십 개월이 걸리기도 하죠. 그런데 이번 연구는 유독 순탄하게 진행됐어요. 중간에 막혀도, 며칠 만에 아이디어가 떠올랐죠. 오죽하면 멘토이신 교수님들도 “마법 같다”고 말하실 정도였어요.

이번 연구결과는 분야에서 어떤 의미가 있나요?

이번에 저와 동료들이 해결한 문제는 선형 하이퍼그래프 채색에 관한 추측 중 가장 간단한 예시 중 하나예요. 그래프 채색에 관한 브룩스(Brooks)의 정리나 비징(Vizing)의 정리와는 달리, 이제껏 선형 하이퍼그래프 채색과 관련된 문제에서는 정확한 결과가 나온 경우가 거의 없어요. 보통 근사적인 결과를 얻어 끝내곤 하죠. 근사치가 아닌 정확한 결과값을 냈다는 데서 의의가 있다고 생각됩니다. 앞으로 저는 제 연구 분야에서 다뤄지는 중요한 문제를 해결하고 싶은 목표가 있는데, 이번 연구결과가 그 여정의 교두보라고 생각됩니다.

연구성과 덕분일까요? 최근에는 상산젊은수학자로 선정되셨습니다.

소식을 들었을 때 정말 기뻤어요. 전혀 예상하지 못했어요. 그런데 동시에 복합적인 감정이 들었어요. 역대 수상자 목록을 보니 쟁쟁한 수학자들이 많았거든요. 제겐 과분한 상이 아닌가 싶기도 했죠. 조금 부담도 됐지만, 연구 잘하라는 의미로 받아들이고 연구에 더욱 매진할 계획입니다.

그런데 원래 꿈은 수학자가 아닌, 프로그래머였다고요?

어릴 적부터 프로그래머가 꿈이었어요. 중・고등학생 때 정보올림피아드(청소년 컴퓨터 프로그래밍 대회)를 참여했을 정도로 컴퓨터 프로그래밍을 좋아했어요. 당연히 대학도 컴퓨터과학을 다루는 전산학부 진학만을 생각했죠. KAIST 전산학부에 입학한 뒤에는 1학년 때 2학년 수업을 미리 다 들을 정도였어요. 정작 2학년 때 들을 수업이 없었죠.

그러다 친구 따라 수학과 수업을 들었어요. 엄밀한 수학을 다루는 ‘해석학’ 과목이었어요. 저는 프로그래밍 중에서도 알고리즘 설계에 관심이 있었는데, 이게 넓게 보면 수학이에요. 그래서 엄밀한 수학을 공부하면 알고리즘 설계에 도움이 될 거라고 생각했죠.

이후 완전한 수학자로 진로를 바꾸셨어요.

전산학과는 크게 컴퓨터과학과 컴퓨터 엔지니어링으로 나뉘어요. 저는 이론에 초점을 둔 컴퓨터과학에 관심이 있었죠. 알고리즘을 깊이 있게 연구하고 싶었는데, 이를 위해서 결국 수학을 더 공부해야 했습니다. 컴퓨터 알고리즘에서는 그래프 알고리즘을 다루는데, 이 그래프는 수학에서 연구하는 대상이니까요.

KAIST에서 박사 학위를 받은 뒤, 영국 버밍엄대로 가셨습니다.

김재훈 KAIST 수리과학과 교수님 영향이 있었어요. 제가 KAIST 석사과정 당시 박사후연구원들이 주최한 워크숍에서 김 교수님을 처음 뵀어요. 김 교수님은 곧 영국 버밍엄대로 박사후연구원을 가실 계획이었죠. 버밍엄대는 제 연구 분야에 정통한 연구자도 많고, 연구단도 큰 곳이에요. 그때 전 대학원생이었으니 막연히 버밍엄대에서 연구하면 좋겠다는 생각만 있었죠.

이후 2018년 영국 옥스퍼드대에서 열린 워크숍을 갔는데요, 그곳에서 홍 리우 교수님, 김 교수님과 함께 버밍엄대 교수님들을 만났습니다. 훗날 저의 멘토가 된 교수님들이었죠. 마침 버밍엄대에 박사후연구원 채용이 열렸는데, 어차피 전 박사과정이 1년 남은 상태라 염두에 두지 않았죠. 그런데 버밍엄대에서 1년을 기다리겠다는 조건을 제시하면서 지원을 제안했습니다. 더군다나 훌륭한 멘토가 많고, 연구에 몰두할 수 있는 곳이라 버밍엄대를 선택했습니다.

이후 IBS YSF로 합류했습니다. 합류 과정이 궁금해요.

버밍엄대 박사후연구원 계약 기간이 얼마 남지 않은 상황이었어요. 홍 리우 교수님께서 IBS YSF 지원을 제안해 주셨죠. 코로나19로 영국에 나간 3년 동안 한국에 들어오지 못해 향수병도 있었고요.

해외에도 YSF와 비슷한 제도가 있을 것 같은데, IBS YSF를 선택한 이유가 궁금합니다.

먼저 연구비 지원이 풍족합니다. 순수수학은 고급 실험장비가 필요하지 않지만, 해외 학회에 참석하려면 이동과 체류 비용이 필요합니다. 또 한국에서 워크숍을 열어 해외 학자나 연사를 초청하는데, 연사들의 체류 비용을 여유롭게 지원할 수 있으니, 적극적으로 워크숍을 주최할 수 있죠. 세계적으로 봐도 파격적인 조건이라고 생각합니다.

연구에만 몰두할 수 있는 환경이 조성되는 것이 장점이었습니다. 연구자들이 행정 업무를 처리를 힘들어하는데요, IBS에는 행정 업무를 비롯해 연구자들을 지원해 주는 직원들이 많아서 연구자들이 독립적으로 연구만 할 수 있는 최상의 조건이라고 생각합니다.

마지막으로 비교적 오래 연구가 가능합니다. 보통 박사후연구원의 계약기간은 2~3년 정도인데, IBS YSF 같은 경우는 3년 계약에 추가로 2년 연장계약이 가능해요. 최대 5년까지 연구를 할 수 있죠. 시간이 충분히 주어지니 연구자들이 안정적으로 연구할 수 있는 환경이 조성되는 것이죠.

해외와 비교했을 때 IBS YSF의 장점이 큰가요?

세계 다른 기관들과 비교해도 파격적인 조건이라고 생각합니다. 하지만 외국인 연구자들이 한국을 선택하는 데는 몇 가지 장애물이 있습니다. 수학 워크숍이나 학회는 주로 미국이나 유럽에서 열리기 때문에 접근성이 떨어지고요. 언어적 문제도 있죠. 그럼에도 IBS 지원과 인프라가 뛰어나서 외국인 연구자들이 유입되는 것 같습니다. 실제로 IBS에는 뛰어난 외국인 연구자가 많이 근무하고 있고요.

개인적으로는 이런 제도가 더 활성화돼야 한국 수학 발전에도 도움이 될 수 있다고 생각합니다. IBS에는 대학원생 연구자가 많은데요, 유능한 연구자들이 한국에 많이 모이면 한국 학생 연구자들이 공동연구할 기회를 얻고 더욱 실력을 쌓을 수 있기 때문이죠.

앞으로 연구 계획이 어떻게 되나요?

저와 같은 분야를 연구하는 수학자들이라면, 모두 선망하는 문제들이 있어요. ‘램지 수’에 관한 미해결 문제들이 대표적이에요. ‘에르되시-하이날(Erdős–Hajnal)의 추측’을 비롯해 수학자 에르되시 팔과 동료들이 남긴 수많은 미해결 추측들도 있죠. 언젠가는 이런 문제들을 해결하고 싶어요. 또 저와 동료들이 에르되시-파버-로하스 추측을 해결했는데, 그 다음 단계 문제도요.
아마 제 연구 분야의 문제들이 해결될수록 응용 측면에서 더욱 효율적인 무작위 알고리즘을 설계할 수 있을 거예요. 현재 알고리즘이 이용되는 분야가 매우 많은데, 계산에 걸리는 시간을 크게 줄이거나 복잡도를 낮추는 등의 기여를 할 수 있을 거라 생각됩니다.