d라이브러리

최근 커크먼의 여학생 문제를 확장한 50년 난제가 해결됐다는 연구 결과가 나왔습니다. 그 내용을 알아보고 연구자를 만나세요.

1973년 헝가리 수학자 에르되시 팔은 확장판 커크먼의 여학생 문제를 생각했어요. 어떤 점 2개도 동시에 여러 선에 포함되지 않도록 ‘하이퍼그래프’를 그리면서 선들이 밀집되지 않게 하이퍼그래프를 그릴 수 있는지 궁금해한 거예요.

그래프는 점과 선의 조합으로, 주어진 점을 조건에 따라 정확히 두 개씩 묶어 선으로 연결해요. 그런데 하이퍼그래프에서는 몇 개의 점을 선으로 묶느냐에 따라 서로 연결된 점의 개수가 2~n개가 가능해요. 그래서 그래프의 선도 타원이나 원, 직선 등 다양하게 나타낼 수 있어요.

예를 들어 7명(점 7개)이 있고 3명씩 한 조(선)를 이룰 때, 어떤 2명도 동시에 여러 조에 포함되지 않도록 조를 짜면 (1, 2, 3), (1, 4, 7), (1, 5, 6), (2, 4, 6) (2, 5, 7), (3, 6, 7), (3, 4, 5)가 나와요. 이를 하이퍼그래프로 나타내면 아래와 같지요.

다시 확장판 커크먼의 여학생 문제로 되돌아가 봅시다. 에르되시가 선이 밀집됐다고 말하는 건 점 m개가 있을 때 선이 m-2개 이상 그려지는 것이에요. 또 선이 m-2개 있을 때, 그 안에 점이 m개 이하로 있는 것이지요. 이 문제는 약 50년간 해결되지 않았답니다.

드디어 풀린 50년 난제

그러던 2022년 1월 매튜 콴 오스트리아 과학기술연구소 교수, 미국 매사추세츠공과대학교 수학과 대학원생인 아쉬윈 사와 메타브 소니, 마이컬 심킨 미국 하버드대학교 수리과학 및 응용센터의 박사후연구원이 확장판 커크먼의 여학생 문제를 풀어 논문 사전 등록 사이트인 ‘아카이브’에 발표했어요. ‘흡수’라는 방법을 사용해 n이 충분히 크면 점을 3개씩 한 선으로 묶을 때, 점 2개가 동시에 여러 선에 포함되지 않으면서 선이 밀집되지 않는 하이퍼그래프를 언제나 그릴 수 있다는 것을 증명한 거지요.

해결의 실마리는 바로 ‘흡수’

연구팀은 조건을 만족하는 하이퍼그래프를 그리기 위해 어느 점과도 짝을 지을 수 있는 몇 개의 점을 제외하고, 점을 연결하기 시작했어요. 그렇게 하다보니 연결이 쉽지 않은 점들만 남았고, 그 점들을 처음에 제외한 점들과 연결했습니다. 그래프 이론에서는 이를 ‘흡수’라고 부릅니다.

예를 들어 6명의 마법 동물(점)을 2마리씩 우리(선)에 담아볼게요. 이때 우리에 함께 넣으면 서로 싸우는 동물이 있어 서로 싸우지 않는 동물끼리 우리에 넣어야 해요. A는 어떤 동물과 넣어도 되고, B는 A, C와 함께 넣을 수 있어요. C는 A, B, D와 D는 A, C, E와 E는 A, D, F와 F는 A, E와 함께 넣을 수 있습니다. 흡수 전략에 따라 모든 동물과 함께 넣을 수 있는 A를 제외하고 짝을 지으면, B는 C와 짝이 되고, D는 E와 짝이 돼 F가 남아요. F를 A와 짝을 지으면 쉽게 하이퍼그래프를 그릴 수 있어요.

_ 인터뷰 

“조합론의 중요한 연구를 계속할 거예요”

안녕하세요. 아쉬윈 사예요. 2021년 스도쿠처럼 각 행과 열에 문자를 중복되지 않게 채우는 ‘라틴 방진’을 연구하다 이와 비슷한 확장판 커크먼의 여학생 문제도 도전하게 됐어요. 이 문제의 밀집 조건은 라틴 방진의 반복되는 구조와 매우 유사하거든요.

저는 조합론 분야의 여러 수학적 대상을 연구해요. 매사추세츠공과대에 입학한 뒤 우연히 ‘조합론’ 강의를 들었는데, 특정 조건을 만족하는 대상의 경우의 수를 따지는 것이 매우 흥미롭게 느껴졌거든요. 조합론 중에서 특히 그래프에 관한 연구를 좋아해요. 앞으로는 집합이 얼마나 크거나 작을 수 있는지 연구하는 ‘극단적 조합론’ 문제를 더 연구해 볼 예정입니다.