d라이브러리

에르되시가 확률적 방법론을 통해 램지 수의 하한을 찾은 이후로 약 70년 동안 수학자들은 하한을 발전시키지 못했습니다. 그런데 2020년 9월, 온라인 논문 등록 사이트 ‘아카이브’에 다색 램지 수의 하한을 크게 높인 연구 결과가 올라왔습니다. 데이비드 콘론 미국 캘리포니아공과대학교 수학과 교수님과 아사프 퍼버 어바인 캘리포니아대학교 수학과 교수님은 확률적 방법과 비확률적 방법을 혼합한 새로운 연구 방식을 도입했습니다.

콘론과 파버 교수님의 전략은 이렇습니다. 빨강, 파랑, 주황 세 가지 색을 칠한다면 빨강을 이용해 빨간 완전그래프가 생기지 않도록 칠합니다. 그리고 남은 두 가지 색은 동전 던지기를 통해 무작위로 칠합니다. 그리고 파란 혹은 주황색 완전그래프를 모두 피할 수 있는 확률을 계산하는 것이죠. 연구팀은 빨간 완전그래프가 생기지 않도록 칠하는 조건을 찾기 위해 비확률적인 수학 개념인 벡터를 활용했고 남은 두 가지 색을 칠할 때 확률적 방법론을 사용했습니다. ‘벡터’는 좌표평면의 한 점을 원점 기준으로 크기와 방향을 이용해 나타내는 방법을 말합니다.

연구팀은 그래프에 세 가지 색을 칠하는 경우에 대해서 그래프의 꼭짓점마다 서로 다른 좌푯값을 설정하고 이 값을 성분으로 갖는 벡터를 정의했습니다. 이 꼭짓점 벡터 중에서 서로 내적*한 값을 2로 나눈 나머지가 1이 나오는 꼭짓점들만 빨간 선으로 연결합니다. 이렇게 빨강으로 칠하고 남은 나머지가 0인 변은 동전 던지기를 해서 무작위로 파랑과 초록을 칠했습니다.

k개의 색으로 어떤 완전그래프의 변을 칠할 때, t 크기의 부분 완전그래프를 찾을 수 있는 최소한의 수는 R(t;k)로 나타낼 수 있는데, R(t;k)의 하한은 t의 지수함수로 쓸 수 있습니다. 연구팀은 이번 연구 결과로 3색에 대한 램지 수 R(t;3)의 하한은 약 1.732t인 3t에서 1.834t로, 4색에 대한 램지 수 R(t;4)의 하한은 2t에서 2.135t로 높였다고 밝혔습니다. 

램지 수의 하한을 구하는 연구에는 확률적 방법이 많이 쓰이지만, 연구팀은 색을 칠하는 방식에 확률적 방법과 비확률적 방법을 섞는 새로운 시도로 좋은 결과를 냈습니다. 김재훈 KAIST 수리과학과 교수님은 “이 증명은 알고 보면 매우 간단하고 자연스러운데 지난 70년간 아무도 생각해내지 못한 것”이라며 “아무도 생각하지 못한 것이지만 누군가 생각해낸 이후엔 너무나 자연스러운 것이 바로 혁신”이라고 말했습니다. 이 연구 결과는 국제학술지 ‘수학의 진보’에 게재 승인을 받았습니다.

_ 인터뷰

데이비드 콘론 미국 캘리포니아공과대학교 수학과 교수

혁신적인 방법으로 램지 수의 범위를 좁힌 콘론 교수님이 수학동아 독자들에게 연구에 얽힌 이야기를 들려드립니다.

Q 처음 램지 수에 관심을 가지게 된 계기는 언제인가요?

15살 때 국제수학올림피아드에 참가하기 위한 훈련을 받으면서 램지 정리의 가장 간단한 사례를 처음 접했어요. 그때부터 램지 수에 푹 빠지게 됐고, 수학자를 직업으로 삼고 싶다는 생각을 했죠.'

Q 이번 연구에서 어떤 점이 기억에 남나요?

조합론에서 오랫동안 쓰이던 확률적 방법의 한계를 개선하는 것이 어려웠어요. 하지만 확률적 방법에 비확률적 방법을 섞는 아이디어가 떠오르자 빠르게 논문을 작성할 수 있었죠. 보통 논문을 작성하는 데 몇 달에서 몇 년이 걸려요. 하지만 이번 연구는 처음 아이디어에서 논문 작성으로 넘어가는 데 많은 시간이 걸리지 않았어요. 앞으로 두 가지 색으로 칠하는 램지 수의 하한 또는 상한을 지수적으로 개선하는 게 저의 목표예요.

Q 램지 이론은 실생활에 어떻게 활용되나요?

램지 이론은 네트워크의 꼭짓점, 연결과 관련이 있어요. 램지 이론에 대한 많은 연구가 알고리듬을 이해하는 데 도움을 주는 등 컴퓨터 과학 분야가 발전하는 데 기여하고 있죠. 그런 의미에서 호기심을 갖고 가능한 많은 것을 배우길 바라요. 다른 분야의 아이디어가 여러분이 관심을 가지는 분야의 문제를 해결하는 데 도움을 줄 수 있답니다!

용어정리

* 내적 : 벡터를 연산하는 방식 중 하나. 두 벡터의 성분에 대응하는 좌푯값을 곱해서 모두 더한다.