1850년에 토마스 페닝턴 커크먼영국 국교회의 교구장으로서 자신의 주된 책임을 다하지 않았을 때 수학자였던 그는 자신의 "여고생 문제"를 다음과 같이 설명했습니다. 날마다 두어 두 번 나란히 걷지 못하게 하라.”
현대 수학자에게 이러한 종류의 문제는 세 개 이상의 그룹으로 수집된 노드 집합인 하이퍼그래프로 가장 잘 상상됩니다. 15명의 여학생은 노드이며, "세 개의 나란히"의 각 그룹은 세 개의 노드를 연결하는 세 개의 선 또는 모서리가 있는 삼각형으로 생각할 수 있습니다.
Kirkman의 문제는 기본적으로 모든 여학생을 서로 연결하는 이러한 삼각형의 배열이 있는지 묻지만 두 삼각형이 가장자리를 공유하지 않는다는 추가 제한이 있습니다. 가장자리 공유는 두 여학생이 한 번 이상 함께 걸어야 함을 의미합니다. 이 제한 사항은 각 소녀가 일주일 동안 매일 두 명의 새로운 친구와 함께 걷는다는 것을 의미하므로 가능한 모든 쌍이 정확히 한 번 모이게 됩니다.
이 문제와 이와 유사한 다른 문제는 Kirkman이 질문을 제기한 이래 거의 1973세기 동안 수학자들을 현혹했습니다. XNUMX년에 전설적인 수학자 Paul Erdős도 비슷한 문제를 제기했습니다. 그는 양립할 수 없는 것처럼 보이는 두 속성을 가진 하이퍼그래프를 작성할 수 있는지 물었습니다. 첫째, 모든 노드 쌍은 여학생과 마찬가지로 정확히 하나의 삼각형으로 연결되어야 합니다. 이 속성은 그래프를 삼각형으로 조밀하게 만듭니다. 두 번째 요구 사항은 삼각형이 매우 정확한 방식으로 퍼져야 한다는 것입니다. (특히, 삼각형의 작은 그룹에는 삼각형보다 노드가 XNUMX개 이상 더 있어야 합니다.) "조밀한 부분이 없는 조밀한 전체 개체가 있는 이 약간 모순적인 동작이 있습니다."라고 말했습니다. 데이비드 콘론, 캘리포니아 공과 대학의 수학자.
올해 XNUMX월에는 복잡한 50페이지 증명, 네 명의 수학자들은 노드가 충분하다면 이러한 하이퍼그래프를 만드는 것이 항상 가능하다는 것을 증명했습니다. "[그들이] 통과한 기술의 양은 단지 이것을 얻기 위해 굉장했습니다."라고 말했습니다. 앨런 로, 버밍엄 대학의 수학자. Conlon은 "정말 인상적인 작품입니다."라고 동의했습니다.
연구팀은 무작위로 삼각형을 선택하고 필요에 따라 극도의 주의를 기울여 설계함으로써 Erdős의 악마 같은 요구 사항을 충족시키는 시스템을 구축했습니다. Conlon은 "증명에 들어가는 어려운 수정의 수는 실제로 엄청난 것입니다."라고 말했습니다.
그들의 전략은 개별 삼각형에서 하이퍼그래프를 조심스럽게 만드는 것이었습니다. 예를 들어, 15명의 여학생을 상상해 보십시오. 각 쌍 사이에 선을 그립니다.
여기서 목표는 삼각형이 두 가지 요구 사항을 충족하도록 이러한 선 위에 삼각형을 추적하는 것입니다. 첫째, 두 삼각형이 모서리를 공유하지 않습니다. (이 요구 사항을 충족하는 시스템을 슈타이너 삼중 시스템이라고 합니다.) 두 번째로, 삼각형의 모든 작은 하위 집합이 충분히 많은 수의 노드를 활용하는지 확인합니다.
연구자들이 이것을 한 방식은 아마도 유추로 가장 잘 이해될 것입니다.
모서리로 삼각형을 만드는 대신 레고 벽돌로 집을 짓는다고 가정해 보겠습니다. 당신이 만드는 처음 몇 개의 건물은 구조적 보강과 정교한 장식으로 화려합니다. 이 작업이 끝나면 따로 보관하십시오. 그들은 일종의 구조화된 비축물인 "흡수기"의 역할을 할 것입니다.
이제 많은 계획 없이 진행하면서 남은 벽돌로 건물을 짓기 시작합니다. 레고 공급이 줄어들면 길잃은 벽돌이나 구조적으로 불건전한 집이 생길 수 있습니다. 그러나 흡수 건물은 너무 과도하고 강화되어 있기 때문에 여기저기서 벽돌을 뽑아 재앙을 구하지 않고 사용할 수 있습니다.
슈타이너 삼중 시스템의 경우 삼각형을 만들려고 합니다. 이 경우 흡수 장치는 신중하게 선택한 모서리 모음입니다. 시스템의 나머지 부분을 삼각형으로 분류할 수 없는 경우 흡수 장치로 이어지는 가장자리 중 일부를 사용할 수 있습니다. 그런 다음, 완료되면 흡수체 자체를 삼각형으로 나눕니다.
흡수가 항상 작동하는 것은 아닙니다. 그러나 수학자들은 이 과정을 만지작거리며 장애물을 피하는 새로운 방법을 찾았습니다. 예를 들어, 반복 흡수라고 하는 강력한 변형은 가장자리를 중첩된 집합 시퀀스로 분할하여 각 집합이 다음으로 큰 집합의 흡수 역할을 하도록 합니다.
Conlon은 “지난 XNUMX여 년 동안 엄청난 개선이 있었습니다. "그것은 일종의 예술 형식이지만, 그들은 이 시점에서 실제로 그것을 고급 예술 수준으로 끌어 올렸습니다."
에르되쉬의 문제는 반복 흡수에도 까다로웠습니다. "왜 이 문제가 해결되지 않았는지 꽤 빨리 분명해졌습니다."라고 말했습니다. 메타압 소니, 이를 해결한 XNUMX명의 연구원 중 한 명과 함께 애쉬윈 사, Sawhney와 함께 Massachusetts Institute of Technology의 대학원생입니다. 마이클 심킨, 하버드 대학교 수리 과학 및 응용 센터의 박사후 연구원; 그리고 매튜 콴, 오스트리아 과학 기술 연구소의 수학자. "꽤 흥미롭고 꽤 어려운 기술 작업이 있었습니다."
예를 들어, 반복 흡수의 다른 응용 프로그램에서 삼각형, Steiner 삼중 시스템 또는 다른 문제에 대한 다른 구조로 한 세트를 덮고 나면 처리된 것으로 간주하고 잊어버릴 수 있습니다. 그러나 에르되쉬의 조건은 네 명의 수학자들이 그렇게 하는 것을 막았습니다. 문제가 있는 삼각형 클러스터는 여러 흡수체 세트의 노드를 쉽게 포함할 수 있습니다.
"500걸음 전에 선택한 삼각형은 어떻게든 그것에 대해 생각하는 방법을 기억해야 합니다."라고 Sawhney가 말했습니다.
네 명이 결국 알아낸 것은 삼각형을 신중하게 선택하면 모든 작은 것을 추적해야 할 필요성을 피할 수 있다는 것입니다. Sawhney는 "100개의 작은 삼각형 집합에 대해 생각하고 삼각형 집합이 올바른 확률로 선택되도록 보장하는 것이 더 좋습니다."라고 말했습니다.
새로운 논문의 저자들은 그들의 기술이 이 한 가지 문제를 넘어 확장될 수 있다고 낙관하고 있습니다. 그들은 가지고있다 이미 전략을 적용했습니다 에 대한 문제에 라틴 사각형, 스도쿠 퍼즐의 단순화와 같습니다.
그 외에도 궁극적으로 흡수 방법에 영향을 줄 수 있는 몇 가지 질문이 있다고 Kwan은 말했습니다. "조합론, 특히 무작위 프로세스가 정말 강력한 도구인 디자인 이론에서는 문제가 너무 많습니다." 그러한 문제 중 하나인 Ryser-Brualdi-Stein 추측은 라틴 제곱에 관한 것이며 1960년대부터 해결책을 기다리고 있습니다.
흡수가 그 문제를 해결하기 전에 더 많은 개발이 필요할 수 있지만 30년 전에 시작된 이래로 먼 길을 왔습니다. 마야 스타인, 칠레 대학 수학적 모델링 센터 부소장. "이러한 방법이 어떻게 진화하는지 보는 것은 정말 멋진 일입니다."
