메뉴바로가기본문바로가기

동아사이언스

[주말N수학]완벽한 파티 만드는 '램지 수'

통합검색

[주말N수학]완벽한 파티 만드는 '램지 수'

2019.01.20 11:00

 

사진 조가현 기자
풀커슨상 받은 김정한 교수. 사진 조가현 기자

파티에 손님을 초대하려고 합니다. 서로 아는 사람과 모르는 사람의 수는 어느 정도 돼야 모두가 편안하고 즐거운 분위기에서 파티를 즐길 수 있을까요. 일명 ‘파티 문제’라고 불리는 ‘램지 수’ 연구에서 새로운 결과가 나왔습니다.

 

램지 수란 서로 친구인 사람의 수를 k, 서로 모르는 사람의 수를 t라 할 때 k명 또는 t명이 반드시 있으려면 최소 몇 명이 있어야 하는지 나타낸 수로 R(k, t)로 나타냅니다. 1930년 영국 수학자 프랭크 램지가 발표한 램지 정리에 따라 언제나 답이 있지만, k와 t 값이 커지면 따져야 할 경우의 수가 많아 아직 정확한 답을 구할 뾰족한 방법을 찾지 못하고 있습니다.

 

고등과학원 김정한 교수는 램지 수에 대한 업적으로 아시아 최초로 ‘풀커슨상’을 받았습니다. 풀커슨상이란 미국수학회와 수학적 프로그래밍학회에서 3년에 한 번 이산수학 분야에서 가장 뛰어난 논문을 쓴 사람에게 주는 상입니다. 김 교수는 램지 수 R(3,t)에서 t가 커질 때 어떤 속도로 커지는지 정확히 밝힌 공로로 1997년 풀커슨상을 받았습니다.

 

앞의 문제는 램지 수의 가장 간단한 경우 중 하나로, 답은 6명입니다. 그중 한 명의 이름을 충재라고 가정하면 나머지 사람 5명 중 충재의 친구가 3명 이상이거나 충재와 친구가 아닌 사람이 3명 이상일 겁니다. 대칭성이 있으니 충재의 친구가 3명 이상인 경우만 생각해도 되겠죠? 충재의 친구 중 3명을 나래, 해인, 예진이라고 합시다. 만일 나래, 해인이가 서로 친구 사이라면 충재, 해인, 나래는 서로 친구 사이인 세 명이 됩니다(그림).

 

물론 해인과 나래가 서로 모르는 사이라고 생각해도 됩니다. 그러면 나래와 예진, 예진과 해인이도 서로 모르는 사이라서 나래, 해인, 예진이가 서로 모르는 사이가 돼 이 문제를 풀게 됩니다. 

 

일러스트 김윤재
일러스트 김윤재

김 교수의 업적 중 하나인 R(3,t)은 N명 중에는 반드시 서로 친구 사이인 3명이나 친구 사이가 아닌 t명이 있을 최소의 N값을 뜻한다. 앞에 든 예에 따르면 t=3일때 6명이면 반드시 그런 경우가 있으니 R(3,t)≤6이 됩니다. 5명일 때는 그런 일이 없을 때가 있어 R(3,t)=6입니다.
 

하지만 실제 R(3,t)가 저 속도로 증가하는지는 김정한 교수 연구 이전에는 아무도 알지 못했습니다. 1995년 김정한 교수는 반대 방향의 부등식을 증명합니다. 이 업적으로 김 교수는 1997년에 풀커슨상을 받았습니다. 몇 년 전에 미국 수학자 조엘 스펜서가 R(3,t)의 연구 역사를 소개하는 강연을 하는 것을 들었었는데, 김 교수의 결과를 소개하면서 헝가리 사람이 아니라서 놀랐다고 말하기도 했습니다. 사실 램지 수 연구는 헝가리 수학자들에 의해 활발하게 진행됐습니다. 1930년대 헝가리 수학자인 에르되시 팔과 세케레시 죄르지가 램지 수에 관련된 논문을 내면서 헝가리 수학계에 널리 알려졌거든요.

 

검증 기간만 6년, 그만큼 어렵고 중요해

 

지난 2003년 2월 이 부등식에 붙은 라는 상수를 개선한 결과가 거의 비슷한 시기에 두 연구 그룹에서 나왔습니다. 두 팀 모두 같은 결과를 냈고 그 내용은 다음과 같습니다.

 

인터넷 논문 공개 사이트인 아카이브(arXiv)에 2013년 2월 24일 톰 보먼과 피터 키바쉬는 52쪽짜리 논문을, 이어 다음날 곤찰로 피츠 폰티페로스, 사이먼 그리피스, 로버트 모리스가 쓴 118쪽짜리 논문을 공개했습니다. 

 

118쪽짜리 논문을 쓴 사이먼 그리피스가 2016년 12월 영국 랜덤 그래프 워크숍에서 자신의 연구를 소개하고 있다. ⒸMaths LSE
118쪽짜리 논문을 쓴 사이먼 그리피스가 2016년 12월 영국 랜덤 그래프 워크숍에서 자신의 연구를 소개하고 있다. Maths LSE

우연의 일치는 아닌 것 같습니다. 두 그룹이 서로의 연구결과를 알고 있었고, 증명 방법이 달라 논문을 합치지 않은 것으로 생각됩니다. 왜냐하면, 각자 논문에서 상대방의 연구 결과를 언급하고 있기 때문입니다. 

 

워낙 긴 논문이고 중요한 내용이라 검증 과정이 오래 걸렸습니다. 6년이 지난 2018년에서야 118쪽짜리 논문이 미국수학회에서 발행하는 학술지 ‘미국수학회록’의 심사를 통과했습니다. 

 

R(3,t) 값이 크다는 것을 증명하려면 서로 아는 세 명도 없으면서 서로 모르는 t명이 없는 경우를 찾아야 합니다. 실제로 손으로 그걸 직접 만들려고 하면 쉽지 않습니다. 이번 연구의 증명을 위해서는 확률을 매우 깊게 사용합니다. 그런데 단순하게 친구 사이를 결정하는 것을 확률로 한다고 해서 좋은 부등식이 나오지는 않습니다. 확률을 사용할 뿐 아니라 다른 아이디어도 잘 섞어야 비로소 좋은 부등식이 얻어집니다.

 

사실 램지 수로 생각할 수 있는 많은 수열 중에 R(3,t)만큼 증가 속도를 정확하게 알아낸 것이 거의 없을 만큼 램지 수의 연구가 어렵습니다. 그런데 거기에 붙은 상숫값을 이렇게나 많이 정밀하게 구할 수 있다는 것 또한 놀라운 일입니다. 우리가 알아낼 수 있다는 게 놀랍고, 그 한계가 어디까지인지 궁금합니다.

 

※필자소개

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

 

관련기사 : 수학동아 2019년 1월호 [엄상일 교수의 따끈따끈한 수학] 완벽한 파티 만드는 램지 수

이 기사가 괜찮으셨나요? 메일로 더 많은 기사를 받아보세요!

댓글 0

3 + 8 = 새로고침
###
    과학기술과 관련된 분야에서 소개할 만한 재미있는 이야기, 고발 소재 등이 있으면 주저하지 마시고, 알려주세요. 제보하기

    관련 태그 뉴스