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

동아사이언스

[주말N수학] 실현 가능한 수를 찾아라

통합검색

[주말N수학] 실현 가능한 수를 찾아라

2019.07.13 06:00
2014 서울 세계수학자대회 때 모습으로, 유리수 지수 추측을 연구한 김재훈 박사와 이준경 박사가 나란히 옆에 앉아 강연을 듣고 있다. ICM 2014
2014 서울 세계수학자대회 때, 유리수 지수 추측을 연구한 김재훈 박사와 이준경 박사가 나란히 앉아 강연을 듣고 있다. ICM 2014

제약 조건이 있는 상황에서 구하고자 하는 대상이 최대 또는 최소가 되는 경우를 따지는 수학분야를 ‘극단조합론’이라고 부릅니다. 이번에 소개할 연구는 극단조합론의 시초가 된 문제에서 출발합니다. 2018년부터 올해까지 여러 수학자 그룹에서 결과를 내고 있는데요, 그중에는 한국인 수학자도 여럿 있습니다.

 

1907년 네덜란드 수학자 빌럼 만털은 우리말로 ‘수학 연습문제(Wiskundige Opgaven)’라는 이 름의 네덜란드 수학 잡지에 다음과 같은 문제와 그 풀이를 공개했습니다.

 

 

만털이 만든 이 문제의 답은 \frac{\ n^2 }{\ 4} , 즉 \frac{\ n^2 }{\ 4} 보다 크지 않은 최대의 자연수입니다. 이 정리대로 점과 선분을 그리는 방법은 찾기 쉽습니다. 편의상 n이 짝수인 경우만 생각해 보기로 하지요. n개의 점 중 딱 절반인 \frac{n}{2}개의 점을 골라서 빨간색으로 칠하고 나머지 점들은 파란색으로 칠합니다.

 

 

이때 빨간점에서 파란점으로 이을 수 있는 선분은 모두 그리고 다른 선분은 그리지 않기로 합니다. 그러면 총  \frac{\ n^2 }{\ 4}개의 선분이 그려 지는데, 어느 세 점을 잡더라도 그중 색이 같은 두 점이 있어 원하는 조건을 만족합니다.

 

튜란의 정리는 극단조합론의 시초

 

헝가리의 수학자 팔 튜란은 만털의 정리를 확장합니다. 튜란은 3개 점 대신 '어떤 t+1개 점 중에 서로 선분으로 이어지지 않은 두 점이 반드시 있도록 그리려면 선분을 최대 몇 개까지 그릴 수 있는지' 물었습니다. 답을 찾으려면 점을 거의 똑같은 개수로 나눠서 t가지 색으로 색칠한 뒤 색이 다른 것끼리만 선분으로 이어야 합니다. 그래야 선분을 최대한 많이 그릴 수 있지요.

 

1941년 증명된 이 정리를 현재 ‘튜란의 정리’라고 부릅니다. 이 정리는 오늘날 ‘극단조합론’이라 고 부르는 분야의 시초가 됩니다. 극단조합론이란 제약 조건이 있는 상황에서 구하고자 하는 대 상이 최대 또는 최소가 되는 경우를 찾는 조합론의 한 분야입니다. 

 

사실 만털의 정리와 튜란의 정리는 꼭짓점과 선으로 이뤄진 그래프로 이해하면 깔끔합니다. 그래프는 꼭짓점의 집합과 두 꼭짓점을 잇는 선의 집합으로 표현됩니다. 두 꼭짓점이 선으로 연결돼 있으면 그 두 꼭짓점은 이웃한다고 말합니다. 여기서는 두 꼭짓점을 잇는 선이 하나만 있다고 가정합시다.

 

꼭짓점은 k개며, 이 k개 꼭짓점이 서로서로 다 선으로 연결된 그래프를 특별히 K_{k}라고 씁시다. 그러면 만털의 정리는 다음과 같이 쓸 수 있습니다.

 

 

이제 이 정리를 더 일반화를 해봅시다. 총 n개 의 꼭짓점을 가진 그래프 중 특정 그래프 H가 없는 것의 선의 개수의 최댓값을 ex(n, H)라고 씁시다. 그러면 만털의 정리는 ex(n, K_{3})=\left [ \frac{\ n^{^{2}} }{\ 4} \right ]이 되지요. 튜란의 정리는ex(n, K_{t+1})을 구하는 겁니다. 헝가리 수학자 에르되시 팔과 미클로시 시모노비치, 영국 수학자 아서 스톤은 n이 무한히 커질 때 ex(n, H)가 어떤 식일지를 밝혔습니다. 다음과 같은 식을 증명한 겁니다

 

 

예를 들어 H=K₃이라면, 이  x^\left \left ( {K_{3}} \right ) \right =3 이 되고 에르되시-스톤-시모노비치 정리에 의해

ex(n,K_{3})=\left ( \frac{1}{2}+o(1) \right ) \frac{n^{2}}{2}이 됩니다. 이 값이 \left [ \frac{n^{2}}{4} \right ] 과 같도록 o(1) 자리에 0으로 수렴하는 함수를 집어넣을 수 있는데요. 그러면 이 식이 만털의 정리가 알려주는 ex(n,K_{3})의 증가속도를 정확하게 말해 줍니다. 특히 \chi ^\left ( {H} \right ) >2인 경우에는 1-\frac{1}{ \chi ^(H)-1}이 0 이 아니라서 에르되시-스톤-시모노비치 정리는 ex(n, H) 값이 대략 n²에 비례하게 증가합니다. 

 

그렇다면 ^{\chi \left ( H \right )}=2인 경우는 어떨까요? 이 경우에는 에르되시-스톤-시모노비치 정리를 쓰면 ex(n, H)는 n²보다는 느리게 증가한다는 사실밖에 모릅니다. 그래서 ^{\chi \left ( H \right )}=2인 경우에 ex(n,H)가 n의 몇 제곱과 비슷하게 증가하는지 알아내려고 여러 수학자가 오랫동안 노력하고 있습니다.

 

한편 에르되시와 시모노비치는 1 이상 2 이하인 유리수 중 아무거나 잡아 r이라고 할 때, ex(n, H) 가 대략 n^{r}에 비례해 증가하는 그래프 H가 반드시 있는지 물었습니다. 만약 그런 H가 있는 r을 ‘실현 가능하다’고 부릅시다.  \frac{ex(n, H)}{n^{r}} 가 n이 무한히 커질 때 0이 아닌 값으로 수렴하게 되는 그래프 H가 있으면 그 r을 실현 가능하다고 할 수 있지요.

 

r을 ‘튜란 지수’라고 부르기도 합니다. 즉 에르되시와 시모노비치의 유리수 지수 추측은 1과 2 사이의 모든 유리수가 실현 가능하다는 겁니다.

 

지난해 보리스 부흐 미국 카네기멜론대 교수와 데이빗 콘론 영국 옥스퍼드대 교수는 1과 2 사이 모든 유리수 r에 대해 그래프 여러 개를 잘 잡으면, 그 그래프를 동시에 갖지 않는 꼭짓점 n개인 그래프의 선 개수가  n^{r}에 비례하게 최댓값을 만들 수 있다는 것을 증명했습니다. 이 결과는 유럽수학회에서 발행하는 저명한 학술지에 실렸습니다. 하지만 그래프 하나만 갖지 않으면서도 그게 가능한지는 여전히 해결되지 않은 문제였습니다.

 

KAIST 출신 수학자들의 활약

 

지난해 여름까지 알려진 실현 가능한 수들을 다 모아봐도 촘촘하게 모여있는 곳은 1과 2뿐이었습니다. 유리수 지수 추측이 옳다면 1과 2 사이의 실현 가능한 수 주변에는 다른 실현 가능한 수가 조밀하게 있어야 합니다. 따라서 서로 다른 실현 가능한 수로 만든 수열의 극한값으로 나올 수 있는 수는 무한히 많아야 하지요.

 

 

지난해 11월 제 박사과정 학생인 강동엽 학생과 함께 영국 워릭대에 있는 김재훈 박사와 류홍 박사는 바로 이 사실을 처음으로 증명했습니다. 인터넷 논문 공개 사이트인 아카이브에 올린 논문에서 이 세 명은  2-\frac{a}{am+1}꼴과 2-\frac{a}{am-1}꼴 유리수는 모두 실현 가능하다는 것을 증명했지요. 이제 m은 고정하고  a를 무한대로 보내면, 2-\frac{1}{m}이 서로 다른 실현 가능한 수로 만든 수열의 극한값이 된다는 것을 보일 수 있게 됐습니다.

 

올 3월에는 콘론 교수와 그의 제자이자 현재 독일 함부르크대 연구원인 이준경 박사, 영국 케임브리지대 박사과정연구원인 올리버 잰저가 더 많은 실현 가능한 수를 찾아냈습니다. 아카이브에 올라온 이들의 논문을 보면 \frac{3}{2}-\frac{1}{2m} 꼴과  1+\frac{1}{am+1}꼴도 실현 가능하다는 것을 밝혔습니다. 이를 이용하면 1+\frac{1}{m}도 서로 다른 실현 가능한 수로 만든 수열의 극한값이 된다는 것을 보 일 수 있지요. 즉 실현 가능한 수가 촘촘히 모인 또 다른 곳을 무한 개 찾아낸 것입니다.

 

5월에는 장 교수와 위추 홍콩중문대 교수가 아카이브에 올린 논문에서 m>1일 때,  1+\frac{2}{3m}  꼴과 1+\frac{3}{4m} 꼴의 유리수도 모두 실현 가능하다는 것을 증명합니다. 6월 10일에는 다시 잰저가 이 결과를 확장하는 새로운 논문을 아카이브에 올렸습니다.

 

어떤 수 r이 실현 가능한지 보이려면 일단 그 수가 튀어나오게 될 그래프 H를 찾아야 하고, 그 뒤 왜 선의 개수가 n^{r}보다 빨리 증가할 수 없는지 증명해야 합니다. 한편으로는 n^{r}개 정도의 선을 잘 넣은 H가 없는 꼭짓점 n개짜리 그래프를 찾아내야 하지요. 이 과정이 그리 만만하지는 않습니다.

 

이번 글에 등장한 세 명의 한국인 수학자는 모두 KAIST 수리과학과를 졸업했습니다. 김재훈 박사는 학부를 졸업하고 미국으로 유학을 갔고, 이준경 박사는 학사와 석사 졸업 후 영국으로 유학을 갔으며, 강동엽 학생은 학부부터 석박사 모두 KAIST에서 마치고 2020년에 박사후연구원으로 영국에 갈 예정입니다. 김 박사는 이번 여름에 KAIST 수리과학과 교수로 되돌아옵니다. 앞으로도 훌륭한 연구 성과를 거두기를 기대합니다.

 

참고자료

데이빗 콘론, 올리버 잰저, 이준경 ‘More on the extremal number of subdivisions’, 강동엽, 김재훈, 류홍 ‘On the rational Turán exponents conjecture’, 타오 장, 위추 ‘Turan numbers of bipartite subdivisions’

 

관련기사

수학동아 7월호 [엄상일 교수의 따끈따끈한 수학]실현 가능한 수를 찾아라! 유리수 지수 추측

 

※필자소개

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

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

댓글 0

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