구독상품안내
이중범 박사는 미국 캘리포니아대학교 로스앤젤레스 캠퍼스에서 박사학위를 받고 미국 매사추세츠공과대학교에서 3년간 연구와 강의를 했습니다. 2015년 가을부터는 미국 월스트리트의 어느 금융회사에서 일하고 있습니다.
이 박사가 푼 문제는 ‘램지 수’와 관련이 있습니다. 6명이 모이면 이중 어떤 한 사람은 3명과 서로 악수한 적이 있거나 악수한 적이 없다는 사실을 알고 계신가요? 6명 중 한 명을 뽑아서 A라고 합시다. A와 서로 악수한 사람이 3명 이상이거나 A와 서로 악수하지않은 사람이 3명 이상이겠지요. 여기서는 A와 악수한 사람이 3명 이상이라고 가정합시다.
이제 A와 악수한 어떤 세 사람을 B, C, D라고 합시다. 만약 B와 C가 악수한 사이라면 A와 B, C는 서로 악수한 사이가 됩니다. 마찬가지로 C와 D가 악수한 사이라면 A와 C, D가 악수한 사이가 되고, D와 B가 악수한 사이라면 A와 D, B가 악수한 사이가 됩니다.
만약 B와 C, C와 D, D와 B가 서로 악수한 적이 없다면, B, C, D가 서로 악수한 적이 없는 세 사람이 됩니다. 따라서 어떠한 상황에서도 서로 악수한 세 명이나 서로 악수를 하지 않은 세 명이 항상 있습니다.
외계인과 전쟁보다 더 어려운 램지 수
1930년대 영국의 수학자 프랭크 램지는 사람이 충분히 많으면 그 중에 서로 악수한 사람이 r명 있거나 서로 악수한 적이 없는 s명이 반드시 있다는 사실을 증명했습니다. 이 정리를 바로 ‘램지 정리’라고 부릅니다. 램지 정리를 만족하는 최소의 수 N을 보통 R(r,s)라고 쓰고 흔히 램지 수라고 부르지요. 앞에서 이야기한 악수 문제는 R(3,3)≤6이 되지요. 램지 수는 구하기가 매우 어렵습니다. 오래 전 헝가리 수학자 에르되시 팔은 이런 이야기를 했습니다.
만일 외계인이 지구를 침공해서 1년 이내에 R(5,5) 값을 구하지 못하면 지구를 파괴하겠다고 협박하면, 아마 전세계 천재 수학자와 컴퓨터를 다 동원해서 풀어낼 수 있을 것이다. 하지만 외계인이 R(6,6) 값을 1년 이내에 구해야 한다고 하면 그냥 외계인과 전쟁하는 것이 나을 것이다.
램지 수를 구하기가 너무 어렵다 보니 수학자들은 어떤 구체적인 값에 대한 R(r,s)를 구하기보다는 r이나 s가 증가할 때 R(r,s)가 어떤 함수와 비슷한 속도로 증가하는지에 관심을 가졌습니다.
램지 수 문제를 그래프 문제로!
램지 수에 대한 이야기로 돌아가 봅시다. 꼭짓점이 여러 개 있고, 두 꼭짓점 사이를 선으로 이어 그린대상을 ‘그래프’라고 하지요. 특히 그래프에서 서로 다른 두 꼭짓점이 모두 선으로 연결된 경우를 ‘완전그래프’라고 합니다. 여기서는 여러 사람이 있고 서로 악수한 사람 사이에 선을 그은 것이 그래프가 되지요. 램지 정리를 그래프 이론의 언어로 나타내면 다음과 같습니다.
N이 충분히 크다면, 꼭짓점이 N개인 완전그래프의 각선을 빨간색 혹은 파란색으로 아무렇게나 칠해도 빨간색 선만 가진 꼭짓점이 r개인 완전그래프 또는 파란색 선만 가진 꼭짓점이 s개인 완전 그래프를 찾을 수 있다.
1930년대 영국의 수학자 프랭크 램지는 사람이 충분히 많으면 그 중에 서로 악수한 사람이 r명 있거나 서로 악수한 적이 없는 s명이 반드시 있다는 사실을 증명했습니다. 이 정리를 바로 ‘램지 정리’라고 부릅니다. 램지 정리를 만족하는 최소의 수 N을 보통 R(r,s)라고 쓰고 흔히 램지 수라고 부르지요. 앞에서 이야기한 악수 문제는 R(3,3)≤6이 되지요. 램지 수는 구하기가 매우 어렵습니다. 오래 전 헝가리 수학자 에르되시 팔은 이런 이야기를 했습니다.
만일 외계인이 지구를 침공해서 1년 이내에 R(5,5) 값을 구하지 못하면 지구를 파괴하겠다고 협박하면, 아마 전세계 천재 수학자와 컴퓨터를 다 동원해서 풀어낼 수 있을 것이다. 하지만 외계인이 R(6,6) 값을 1년 이내에 구해야 한다고 하면 그냥 외계인과 전쟁하는 것이 나을 것이다.
램지 수를 구하기가 너무 어렵다 보니 수학자들은 어떤 구체적인 값에 대한 R(r,s)를 구하기보다는 r이나 s가 증가할 때 R(r,s)가 어떤 함수와 비슷한 속도로 증가하는지에 관심을 가졌습니다.
램지 수 문제를 그래프 문제로!
램지 수에 대한 이야기로 돌아가 봅시다. 꼭짓점이 여러 개 있고, 두 꼭짓점 사이를 선으로 이어 그린대상을 ‘그래프’라고 하지요. 특히 그래프에서 서로 다른 두 꼭짓점이 모두 선으로 연결된 경우를 ‘완전그래프’라고 합니다. 여기서는 여러 사람이 있고 서로 악수한 사람 사이에 선을 그은 것이 그래프가 되지요. 램지 정리를 그래프 이론의 언어로 나타내면 다음과 같습니다.
N이 충분히 크다면, 꼭짓점이 N개인 완전그래프의 각선을 빨간색 혹은 파란색으로 아무렇게나 칠해도 빨간색 선만 가진 꼭짓점이 r개인 완전그래프 또는 파란색 선만 가진 꼭짓점이 s개인 완전 그래프를 찾을 수 있다.
그럼 꼭 완전그래프가 아닌 다른 그래프를 찾겠다고 하면 어떨까요? 어떤 그래프 H를 하나 고정하면, 램지 정리에 의해서 N이 충분히 크면 꼭짓점이 N개인 완전그래프의 선을 빨간색 혹은 파란색으로 어떻게 칠해도 어딘가에는 빨강색으로 된 H와 똑같이 생긴 그래프가 있거나 파랑색으로 된 H와 똑같은 그래프가 있을 겁니다. 단, 완전그래프에서 H의 일부가 아닌 선은 무슨 색으로 칠해도 상관없습니다.
1973년 두 수학자 스태판 버어와 에르되시는 램지 수 문제를 이렇게 그래프 H를 찾는 문제로 바꿔서 생각했습니다. 꼭짓점이 N개인 그래프의 각 선을 어떤 두 색으로 칠하더라도 빨간색 H나 파란색 H가 반드시 생기게 될 최소의 N을 r(H)라고 정의하고 ‘그래프 램지 수’라고 불렀지요. 만일 H가 꼭짓점 s개짜리 완전그래프라면 r(H)는 R(s,s)와 똑같아지니까 조금 더 일반적인 문제가 되지요.
이중범 박사, 40년 묵은 난제 해결
버어와 에르되시는 혹시 그래프 H에 선이 많이 없다면 r(H)가 보통의 램지 수보다는 훨씬 작은 수가 되지 않을까 추측했습니다. 이게 바로 ‘에르되시-버어 추측’입니다. 그래프 H에 선에 많이 없다는 것은 어떤 의미일까요? 그래프 H의 꼭짓점마다 1, 2, 3, 4, … 처럼 번호를 매깁니다. 이때 번호를 잘 매기면 꼭짓점 x는 x보다 작은 수를 가진 꼭짓점과 연결된 상태만 따져봤을 때 연결된 선의 개수가 d개 이하라는 겁니다. 쉽게 그런 그래프 H를 ‘앞사람 d명 이하와 악수한 그래프 H’라고 부르겠습니다.
이중범 박사, 40년 묵은 난제 해결
버어와 에르되시는 혹시 그래프 H에 선이 많이 없다면 r(H)가 보통의 램지 수보다는 훨씬 작은 수가 되지 않을까 추측했습니다. 이게 바로 ‘에르되시-버어 추측’입니다. 그래프 H에 선에 많이 없다는 것은 어떤 의미일까요? 그래프 H의 꼭짓점마다 1, 2, 3, 4, … 처럼 번호를 매깁니다. 이때 번호를 잘 매기면 꼭짓점 x는 x보다 작은 수를 가진 꼭짓점과 연결된 상태만 따져봤을 때 연결된 선의 개수가 d개 이하라는 겁니다. 쉽게 그런 그래프 H를 ‘앞사람 d명 이하와 악수한 그래프 H’라고 부르겠습니다.
하지만 이것만으로는 부족합니다. 앞사람 d 명 이하와 악수한 그래프 H 중에는 어떤 꼭짓점이 d보다 훨씬 큰 수의 다른 꼭짓점과 선으로 이어져 있을 수 있거든요. 예를 들어 한 꼭짓점이 나머지 n -1개 꼭짓점과 연결된 선이 n -1개인 그래프를 생각하면, 가운데 있는 점은 무려 n-1개의 다른 꼭짓점과 연결돼 있습니다. 하지만 그 점을 1번 꼭짓점으로 정하면 이 그래프는 앞사람 d명 이하와 악수한 그래프 H가 됩니다.
그동안 에르되시-버어 추측은 부분적인 결과만 있었습니다. 하지만 이 박사가 지난 2015년 r(H)≤f(d)n을 만족하는 함수 f를 찾아내 40년 난제인 에르되시-버어 추측을 해결했습니다. 이 박사는 어떤 상수 c 가 있어서 항상
임을 보였습니다.
40년 묵은 난제를 해결한 이 박사가 수학계에 남아 계속해서 좋은 연구를 이어가 주면 좋을 텐데, 학계를 떠나 금융가에서 일하고 있어 매우 아쉽습니다.
그동안 에르되시-버어 추측은 부분적인 결과만 있었습니다. 하지만 이 박사가 지난 2015년 r(H)≤f(d)n을 만족하는 함수 f를 찾아내 40년 난제인 에르되시-버어 추측을 해결했습니다. 이 박사는 어떤 상수 c 가 있어서 항상
임을 보였습니다.40년 묵은 난제를 해결한 이 박사가 수학계에 남아 계속해서 좋은 연구를 이어가 주면 좋을 텐데, 학계를 떠나 금융가에서 일하고 있어 매우 아쉽습니다.
