전체 $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$이  충분히 크다면 위와 같은 식으로 동아리를 짜는 것이 가능하다.

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 교수로부터 이 문제를 잘 알게 되었고 그 후 다른 연구를 하면서도 이 문제에 대하여 항상 관심을 가지고 있었다고 한다.