잘 짜인 동아리 (Generalized Steiner System)

전체 $n$명의 사람이 있는 학교에서 $q$명의 학생들로 구성된 동아리들이 있다고 한다. 그런데 아무렇게나 $r$명의 학생을 모아도 그 $r$명이 동시에 속한 동아리의 수는 정확히 $\lambda$로 똑같다고 한다. 과연 $n$, $q$, $r$, $\lambda$ 값이 어떤 경우에 이런 식으로 동아리들을 구성할 수 있을까?

$i\le r$인 어떤 수 $i$에 대해, 학생 $i$명의 집합 $Z$를 생각해보자. 이 집합 $Z$의 학생을 동시에 포함한 $r$명의 학생의 집합$Y$는 정확히 $\binom{n-i}{r-i}$개가 있으므로, 집합 $Z$의 학생을 동시에 포함한 동아리 $X$가 있을 때 $(X,Y)$의 순서쌍의 수는 정확히 $\lambda\binom{n-i}{r-i}$가 된다. 반대로, $Z$를 포함한 동아리 $X$에 대해 위의 조건을 만족하는 $Y$의 수는 $q-i$명에서 $r-i$명을 뽑는 수와 같으므로 $\binom{q-i}{r-i}$이다. 모든 $Z$를 포함하는 동아리에 대해 위 성질이 성립하므로 \begin{equation}\text{모든 $0\le i\le r$에 대해 $\binom{q-i}{r-i}$는 $\lambda\binom{n-i}{r-i}$의 약수}\label{eq:st} \end{equation}여야 한다.

그럼 조건 \eqref{eq:st}을 만족하는 모든 $n$, $q$, $r$, $\lambda$가 있다면 저런 식으로 동아리를 반드시 짤 수 있을까?

이 문제는 조합론 분야에서 정말 오래된 난제 중 하나이다. $r=2$일 때 이러한 식으로 동아리를 짤 수 있냐 물어보는 문제를 Steiner System이라고 하고, 일반적인 $r$에 대해서는 Generalized Steiner System이라고 한다. 이 문제는 무려 1800년대 중반까지 역사가 거슬러갈 정도로 조합수학 분야에서 정말 오래된 난제 중에 하나인데, 올해 초 이 분야 연구자들을 깜짝 놀라게 한 연구결과를 옥스포드 대학 Peter Keevash 교수가 발표하였다. (arxiv에 올라온 논문)

정리 (Keevash 2014): 모든 $n$, $q$, $r$, $\lambda$가 조건 \eqref{eq:st}을 만족하며 $n$이  충분히 크다면 위와 같은 식으로 동아리를 짜는 것이 가능하다.

Peter Keevash 교수
Peter Keevash 교수 (2003년에 Banff 워크샵 갔을때 만나서 찍었던 사진)

Steiner System에 관한 연구의 역사는 1800년대 중반 수학자들 Plücker (1835년), Kirkman (1846년), Steiner (1853년)로 거슬러 올라간다.  $r=2$인 경우에는 이 문제는 1970년대  칼텍의 Richard M. Wilson 교수가 $n$이 충분히 크면 참이라고 증명하였다.  일반적인 $r$은 아직까지 미해결로 남아있었다.

2014년 6월 미국 미니애폴리스에서 열린 SIAM Conference on Discrete Mathematics라는 학회에서는 긴급하게 “Hot Topic Session”이라는 이름으로 저녁 8시에 Peter Keevash 교수를 초청해서 이 결과에 대한 강연을 듣는 자리가 있었다. 보통 이런 학회의 초청강연자 명단은 몇 달 전에 잡히기 때문에 초청강연자로 하기에는 너무 늦은 상황이지만 결과가 매우 중요하기 때문에 이렇게 늦게 시간을 잡았다고 한다.

이 문제의 해법은 확률론적 방법을 사용하는데 Keevash 교수는 그것을 “Randomized Algebraic Construction”이라고 부른다. 앞으로 이러한 방법이 다양한 문제를 해결하는데 큰 도구가 될 것으로 생각된다.

영국 출신인 Peter Keevash 교수는 프린스턴대학에서 Benny Sudakov 교수 지도 하에 2004년에 박사학위를 받았다. 올 봄에 만났을 때, 어떻게 이 문제에 관심을 가지고 해결하게 되었냐 물어보니, 칼텍에서 박사후 연구원을 할 때 Richard M. Wilson 교수로부터 이 문제를 잘 알게 되었고 그 후 다른 연구를 하면서도 이 문제에 대하여 항상 관심을 가지고 있었다고 한다.

댓글 남기기