d라이브러리









조합론 난제를 대수기하학 도구로 해결

지금으로부터 12년 전인 2010년 6월, 특이한 연락을 받았습니다. 서울대학교에서 미국 일리노이주립대학교 대학원으로 유학을 간 지 얼마 안 된 학생이 조합론 및 이산수학 분야의 오래된 추측을 증명했는데, 방학 때 한국 온 김에 기회가 되면 연구 내용을 발표하고 싶다는 겁니다. 서울대에서도 이미 발표했지만, 내용을 볼 때 KAIST에서도 발표하는 게 좋을 것 같다며 서울대 교수님이 KAIST 다른 교수님께 이메일을 주셨습니다. 필자는 이산수학 세미나를 운영하고 있었기 때문에 자연스럽게 그 연락을 전달받게 됐습니다. 그 유학을 간 지 얼마 안 된 학생이 바로 ‘허준이 교수’였습니다.

 

처음에는 이것을 어디까지 믿어야 할지 알 수 없었습니다. 가끔 ‘각의 3등분을 할 수 있다’거나 ‘4색 정리를 증명했다’라는 식의 엉터리 이메일을 받기도 하니까요. 그때까지 지도교수도 정해지지 않은 박사과정 학생이 조합론 분야의 오래된 미해결 문제를 해결했다고 하니 믿기가 쉽지 않았습니다. 논문도 전달받았는데 공저자도 없고, 학술지에 보내기도 전이라 추측을 푼 게 맞는 건지 확신하기가 어려웠습니다.

 

2010년 7월 9일 허 교수는 KAIST 이산수학 세미나에 와서 발표했습니다. 당시 촬영한 동영상이 유튜브(오른쪽 QR코드)에 올라와 있으니 관심 있는 분들은 한 번 보시기 바랍니다. 다시 봐도 박사 1년 차 학생이라고 믿기 힘든 강의 내용입니다. 당시 서울대 수리과학부에는 조합론을 전공하신 교수님이 없었기 때문에 이런 문제를 배울 기회가 없었을 텐데, 이제 갓 유학을 간 학생이 어떻게 이런 문제에 손을 뻗게 된 것인지부터 궁금했습니다.

 

 

박사 1년 차 때 난제 해결

 

허 교수가 박사 1년 차일 때 풀었다고 한 추측이 세 가지나 됩니다. 먼저 그래프 이론에서 나오는 채색 다항식의 계수에 관한 문제인 ‘리드의 추측(1968년)’과 이보다 조금 더 강한 추측으로, 벡터 공간의 벡터 집합이 만들어내는 ‘매트로이드(matroid)’라는 구조에서 나오는 수열에 관한 ‘로타의 추측(1971년)’과 ‘웰시의 추측(1976년)’입니다. 이때 로타의 추측과 웰시의 추측은 특수한 경우에 대해서만 증명했습니다.

 

그래프 채색 다항식의 계수에 관한 리드의 추측은 매트로이드에서 로타의 추측을 풀면 해결되는 것이라, 이 글에서는 로타의 추측 및 웰시의 추측을 설명하면서 시작하겠습니다. 매트로이드는 1935년 미국 수학자 해슬러 휘트니가 행렬의 선형독립에 관한 성질을 추상화해서 만든 수학적인 대상입니다. 따라서 로타의 추측이나 웰시의 추측의 간단한 경우는 행렬로 설명할 수 있습니다.

 

어떤 m×n 행렬이 있다고 가정하고 이 행렬의 열이 1부터 n까지의 수를 가리킨다고 합시다. 만일 {1, 2, …, n}의 부분집합 X가 있다면, 행렬에서 X에 속한 열만 뽑아서 그 열벡터를 가지고 선형결합 해 만들 수 있는 벡터 공간의 차원을 r(X)라는 함수로 써 봅시다.

 

매트로이드에서는 이것을 ‘X의 랭크’라고 부릅니다. 이때 ak를 랭크가 k이면서 원소의 개수가 짝수인 X의 개수와 랭크가 k이면서 원소의 개수가 홀수인 X의 개수의 차이라고 합시다.

 

 

1971년 미국 매사추세츠공과대학교 교수였던 진-카를로 로타는 수열 |a0|, |a1|, |a2|는 한 번 감소하기 시작하면 계속 감소한다는 추측을 제시합니다. 영국 옥스퍼드대학교의 교수였던 도미니크 웰시는 1976년 출판한 책에서 로타의 추측보다 조금 더 강한 추측을 제기합니다. 웰시는 ai2 ≥ |ai-1| · |ai+1|이 모든 i에서 성립한다고 추측했습니다. 이런 부등식을 만족하는 수열을 ‘로그-오목’하다고 하는데, 로그-오목이면서 양수인 수열은 한 번 감소하기 시작하면 계속 감소하기 때문에 로타의 추측보다 더 강한 추측이었습니다.

 

허준이 교수의 2010년 세미나

 

허준이 교수는 혼자 쓴 2010년 논문에서 로타의 추측과 웰시의 추측이 행렬에서 참이라는 것을 증명했습니다. 특히 실수를 사용해 표현된 행렬뿐만 아니라, ‘표수가 0인 체’ 위에서 표현된 행렬에서도 참이라는 것을 보였지요. 우리가 중고등학교에서 배우는 실수, 복소수 등의 대부분 수체계는 표수가 0인 체입니다.

 

그런데 이 추측을 증명하면서 조합론의 방법론은 쓰지 않았습니다. 그러니 세미나를 다 들어도 그 결과가 중요하고 흥미로운 것은 잘 알겠는데, 증명의 과정은 대수기하학 이야기가 대부분이라 대수기하학을 공부하지 않은 필자는 이해하기는 어려웠습니다. 허 교수는 대수기하학 분야를 공부하면서 알게 된 내용을 그래프 이론에 접목하면 어떻게 될까 생각해 보다가 추측해 풀었다고 합니다.

 

두 분야 중간에 서서 양쪽 언어를 동시에 구사하면서 대수기하 분야의 연구 결과와 아이디어를 활용해 조합론 분야의 문제를 해결한 것입니다. 이때 쓴 허 교수의 논문은 2012년 권위 있는 수학 학술지 중 하나인 <;미국수학회지>;에 출판됐습니다.

 

허 교수가 이러한 문제를 생각하게 된 것은 석사 과정 시절 서울대에 몇 년간 계셨던 필즈상을 수상한 일본 수학자 히로나카 헤이스케 미국 하버드대학교 명예교수로부터 배운 것을 가지고 그래프에서 나타나는 현상을 관찰하다가 알게 된 것이라고 합니다.

 

2010년 12월에 허 교수는 박사과정 입시에 지원했다가 떨어졌던 미국 미시간대학교 초청으로 세미나 발표를 갔습니다. 2017년 <;콴타 매거진>;에는 허 교수가 방문하기 전에 미시간대 수학과 시니어 교수가 그 대학 박사 후 연구원에게 ‘유명해지기 전 허준이 교수의 세미나 들었다는 것을 30년 후에 자랑할 수 있을 테니 꼭 세미나 들어보라’라고 했다는 이야기도 소개돼 있습니다.

 

그 후 2011년 허 교수는 미시간대 대학원으로 학교를 옮기게 되었고 웬만한 박사 후 연구원보다 좋은 연구를 하는 대학원생 신분으로 지냈습니다. 신분만 대학원생일뿐 이미 그때부터 여러 국제학회 및 워크숍에 초청 강연자나 기조 강연자로 강연했습니다.

 

좋은 동료 연구자와 함께 로타의 추측 해결

 

허 교수는 2010년 세미나에서는 ‘로타의 추측과 웰시의 추측이 표수가 0이 아닌 체 위에서 표현된 행렬에서는 거짓일 거로 추측한다’고 말했습니다.

 

하지만 당시 미국 텍사스대학교 오스틴에서 박사 후 연구원으로 있던 에릭 카츠 미국 오하이오주립대학교 교수가 인터넷에서 논문을 읽고 연락해 몇 달간 공동연구를 하게 됐는데, 이때 표수가 0이 아닌 체 위에서 표현된 행렬에서도 같은 추측을 증명합니다. 1년 전만 해도 거짓이라고 여겼던 추측이 참임을 보인 것입니다. 허 교수는 2011년 7월에 다시 KAIST에 와서 새로운 결과를 발표했습니다.

 

한동안 허 교수는 로타의 추측과 웰시의 추측을 행렬뿐만 아니라 행렬을 추상화하는 매트로이드 전체에서 증명하려고 노력하고 있었습니다. 행렬로 표현되는 경우에는 기존 대수기하학의 이론을 적용하기가 더 편리했는데, 행렬로 표현되지 않는 일반적인 매트로이드에서도 똑같은 것을 하려면 대수기하학 이론을 바로 적용할 수가 없었습니다. 아예 대수기하학의 어려운 이론을 조합적인 상황에 맞게 비슷하게 새로 만들어 나가야 했습니다.

 

이 문제를 풀기 위해 노력할 때 고등연구소를 방문했던 카림 아디프라지토 이스라엘 예루살렘 히브리대학교 교수와 교류하면서 힘을 합치게 되었습니다. 결국 2015년에 허 교수는 아디프라지토 교수, 카츠 교수와 함께 로타의 추측 및 웰시의 추측 전체를 증명한 논문을 공개합니다. 매트로이드에서 문제를 해결한 것이지요. 여기에 더해 ‘메이슨의 추측’도 해결합니다. 이 논문은 2018년 수학계 최고 학술지 중 하나인 <;수학연보>;에 실렸습니다.

 

 

메이슨의 추측은 1972년 존 메이슨이 행렬에서 랭크가 k인 부분행렬을 만들어내는 열의 집합 X의 수를 ak라 할 때, 수열 a0, a1, …이 로그-오목이라고 추측한 것입니다. 아울러 더 일반적으로 매트로이드에서도 같은 것이 성립한다고 추측했지요.

 

매트로이드에서 만들어낼 수 있는 수열이 매우 다양하기 때문에 이 추측도 매우 다양한 결과를 한꺼번에 주었습니다. 예를 들면 그래프가 주어져 있을 때 선이 k개이면서 회로가 없는 부분 그래프의 개수를 센 수열이 로그-오목이라서 한 번 감소하기 시작하면 계속 감소한다는 사실을 바로 유도할 수 있게 되었지요.

 

그 후에도 허 교수는 대수기하학의 이론이 조합수학에서 어떻게 대응할지 상상하며 좋은 추측을 만들고 증명해 나가는 작업을 진행하면서 ‘조합적 호지 이론’이라는 새로운 분야를 개척하고 다른 연구자들을 이끌고 있습니다. 앞으로도 좋은 연구를 하기를 기대합니다.

 

2022년 08월 수학동아 정보

  • 엄상일(기초과학연구원 이산수학그룹 CI & KAIST 수리과학과 교수)
  • 진행

    조가현 기자 편집장
  • 일러스트

    정윤미
  • 디자인

    최서원

🎓️ 진로 추천

  • 수학
  • 컴퓨터공학
  • 정보·통신공학
이 기사를 읽은 분이 본
다른 인기기사는?