구독상품안내
최근 KAIST 수리과학과 안드레아스 홀름센 교수가 홀의 결혼정리를 공간에 있는 유한개의 점에 관한 문제로 확장한 연구를 발표했습니다. 홀의 결혼정리는 언제 남녀 사이에 짝을 지어 주는 게 가능한가에 관한 정리지요. 홀름센 교수의 연구가 어떤 것인지 결혼정리부터 샅샅이 알아봅시다.
학생 6명이 직업 체험을 하러 갔습니다. 각자 체험하고 싶은 직업을 2개씩 적어 보라고 하니 다음과 같았습니다.
그런데 인원 제한 때문에 두 학생이 동시에 같은 체험을 할 수가 없습니다. 시간마저 모자라 모두 하나의 체험만 할 수가 있습니다. 학생들은 어떻게 직업 체험을 할 수 있을까요?
아무리 경우를 따져 봐도 6명이 모두 동시에 체험할 수 있는 방법이 없습니다. 왜 그럴까요? 경환, 혜인, 은영, 가현, 정아 5명의 학생들이 하고 싶어 하는 직업을 살펴보면 연기자, 연구원, 요리사, 의사 이렇게 4개뿐입니다. 5명이 4가지 체험을 하고 싶어 하기 때문에 모두가 희망하는 대로 서로 다른 체험을 할 수 없는 것이지요.
지금까지 설명한 내용을 집합으로 나타내 봅시다. 경환, 혜인, 은영, 가현, 정아가 체험하고 싶어 하는 직업의 집합을 각각 A1, A2, A3, A4, A5이라고 하면, A1∪A2∪A3∪A4∪A5={연기자, 연구원, 요리사, 의사}가 됩니다. 따라서 |A1∪A2∪A3∪A4∪A5|★＜5가 돼, 5명이 A1, A2, A3, A4, A5에서 직업을 하나씩 뽑는 것은 불가능합니다.
[|A|★ 집합 A의 크기를 말한다. 즉 집합의 원소 개수를 일컫는다.]
원하는 사람과 짝짓기
1935년 영국의 수학자 필립 홀은 이와 같은 일이 생기지 않으면 서로 다른 원소를 하나씩 뽑는 것이 언제나 가능하다는 것을 증명했습니다. 즉, |A1∪A2∪A3∪A4∪A5∪A6|≥6, |A1∪A2∪A3∪A4∪A5|≥5, |A1∪A2∪A3∪A4∪A6|≥5, …, |A1∪A2∪A3|≥3, …처럼 집합을 k개 뽑아서 만든 합집합의 원소의 개수가 k개 이상이면 여기서 서로 다른 원소를 하나씩 대표로 뽑을 수 있다는 것입니다. 다음이 바로 ‘홀의 결혼정리’입니다.
A1, A2, A3, …, An은 각각 유한집합이라고 하자. 만일 모든 1≤k≤n에 대해 집합 k개의 합집합 S가 부등식 |S|≥k를 만족하면, 각각의 Ai에서 원소 xi를 잘 뽑아서 원소 x1, x2, x3, …, xn이 서로 다르게 만들 수 있다.
왜 결혼정리라는 이름이 붙었을까요? 각 집합을 어느 여성과 결혼하면 잘 살 남성들의 집합이라고 하면 모든 여성들이 잘 살 남성과 결혼할 수 있게 짝을 지어줄 수 있기 때문입니다. 1930년대 증명된 홀의 결혼정리는 수많은 응용을 낳았고, 매우 요긴하게 쓰이고 있습니다. 홀의 결혼정리를 사용한 쉬운 연습문제로 이런 것이 있습니다.
100명의 남자와 100명의 여자가 참석한 파티에서, 남녀가 서로 인사를 나눴다. 정확히 서로 다른 10명의 이성과 인사를 나눴다고 할 때, 인사를 나눴던 사람끼리 짝을 지을 수 있음을 보이시오. 즉 짝이 된 100쌍 모두는 파티에서 인사를 나눈 적이 있도록 할 수 있음을 보이시오.
짝짓기 문제에서 점 뽑기 문제로 확장!
최근 KAIST 수리과학과에서 이산 기하★를 연구하는 안드레아스 홀름센 교수가 홀의 결혼정리를 공간에 있는 유한개의 점에 대한 문제로 확장한 연구를 발표했습니다. 멕시코의 수학자 레오나르도 마르티네스-산도발 박사, 루이스 몬테하노 박사와 함께 연구해 2016년 2월 미국수학회가 발간하는 논문집에 소개했습니다.
어떻게 결혼정리를 공간에 있는 점 문제로 확장했을까요? 예를 들어 A1, A2, A3, A4, A5, A6이 각각 평면에 있는 유한개의 점들의 집합이라고 합시다. 홀의 결혼정리의 목표는 각 집합에서 x1, x2, x3, x4, x5, x6이라는 6개의 점을 서로 겹치는 않게 잘 뽑는 것입니다. 하지만 홀름센 교수가 제기한 새로운 문제에서는 뽑은 점 x1, x2, x3, x4, x5, x6 중 어느 두 점도 서로 겹치지 않고, 어느 세 점도 같은 직선 위에 있지 않도록 점을 뽑고자 합니다. 과연 어떤 조건을 만족하면 이런 선택이 가능할까요?
평면에서 어떤 점의 집합이 어느 두 점도 서로 겹치지 않고, 어느 세 점도 같은 직선 위에 있지 않다면 그 집합의 점들이 ‘일반적인 위치에 있다’라고 말합니다. 즉 홀름센 교수의 새로운 문제는 각 집합에서 점을 하나씩 뽑아서 모은 것이 일반적인 위치에 있도록 할 수 있는지 물어보는 것입니다.
어떤 점들의 집합 X가 있을 때 φ(X)를 ‘X의 부분집합 중에서 원소가 모두 일반적인 위치에 있으며 원소의 수가 가장 많은 집합의 원소의 수’라고 합시다. 만약 각 집합에서 점을 하나씩 뽑아서 일반적인 위치에 있도록 할 수 있다면, k개의 집합을 뽑아서 합집합을 만들었을 때 그 합집합의 φ(X) 값은 반드시 k보다 크거나 같아야 겠지요. 마치 홀의 결혼정리처럼 말이죠. 과연 이 조건만 만족하면 될까요?
[이산 기하★유한개의 도형사이에서 일어나는 일에 관해 연구하는 학문.]
이산 기하에서도 홀의 결혼정리와 조건이 같을까?
사실 그렇지 않았습니다. 예를 들어 5개의 집합 A1, A2, A3, A4, A5에 각각 점이 하나씩 들어 있고, 그 점 5개가 정오각형의 꼭짓점을 이룬다고 합시다. 이때 5개 점 중 2개를 뽑으면 직선을 그릴 수 있습니다. 총 10개의 직선을 만들 수 있지요. 이 직선 위에 임의의 점 10개를 뽑아 올려 놓습니다. 단, 10개의 점은 모두 일반적인 위치에 있어야 합니다. 이들을 모아 집합 A6라고 합시다.
그러면 집합 A1, A2, A3, A4, A5, A6에서 각각 점 하나를 뽑으면 반드시 어느 세 점은 한 직선 위에 있습니다. 즉 어떻게 해도 일반적인 위치가 될 수 없습니다. 참 이상하지요? 분명 집합 A6이 없을 때는 일반적인 위치에 있는 점 5개를 뽑을 수 있었는데 말입니다. 더욱이 집합 A6는 일반적인 위치에 있는 점들만을 모아 만든 것인데 말이죠.
집합 A1, A2, A3, A4, A5, A6에서 뽑은 집합 k개의 합집합을 S라고 합시다. k개의 집합 중에 집합 A6이 없을 때는 정확히 φ(S)=k가 됩니다. 집합 A1, A2, A3, A4, A5에는 각각 점이 하나밖에 없기 때문입니다. 집합 A6이 있을 때는 φ(S)=10이 됩니다. 따라서 두 경우 모두 φ(S)≥k이 됩니다. 즉 이 경우에는 φ(S)의 값이 k 이상이긴 하지만, 집합 A1, A2, A3, A4, A5, A6에서 각각 원소 하나씩을 뽑아서 일반적인 위치에 있는 6개의 점을 만들 수 없는 것이지요. 따라서 g(k)와 같은 함수가 필요합니다. 그래서 이번에 증명된 정리는 다음과 같습니다.
A1, A2, …, An은 각각 평면 위의 유한개의 점의 집합이라고 하자. 자연수 k가 4 이하일 때 g(k)=k+2이고, 5 이상일 때는 g(k)=(2k+1)(2k+2)+1인 함수g가 있다. 만약 모든 1≤k≤n에 대해 집합 k개의 합집합 S가 φ(S)≥g(k)를 만족하면 각각의 Ai에서 원소 xi를 잘 뽑아서 뽑힌 점들 x1, x2, …, xn이 일반적인 위치가 되게 할 수 있다.
참고로 이번 논문에서는 평면에 대해서만 한 것이 아니라 일반적인 d차원 공간에 대해서도 같은 식의 정리를 증명했습니다. 이때 d=1이면 홀의 결혼정리이지요. 현재까지 이 증명은 위상수학을 이용한 것만 알려져 있습니다.
이번 정리에서 함수 g가 작을수록 더 좋은 정리가 됩니다. 아직까지 더 좋은 함수 g가 있는지는 밝혀지지 않았습니다. 여러분도 한번 시도해 보면 어떨까요? 어쩌면 세상 누구도 아직 알지 못한 것을 발견할 수도 있습니다.
