홀 결혼 정리

3. 역사와 어원

영국의 필립 홀(Philip Hall^영어)이 쾨니그의 정리와 동치인 홀 결혼 정리를 1935년에 증명하였다.^[15]

"결혼 조건"이라는 이름은 다음과 같은 가상의 상황에서 유래했다. $n$명의 미혼 이성애자 남성과 $n$명의 미혼 이성애자 여성이 있다고 가정해 보자. 이들이 결혼 상대에 대해 다음과 같은 조건을 가지고 있다고 하자.

• 각 남성은 어떤 여성이든 결혼할 수 있다.
• 각 여성 $i=1,\backslash dots,n$은 특정 남성들의 집합 $T\_i\backslash subset\backslash \{1,\backslash dots,n\backslash \}$에 속한 남성하고만 결혼하기를 원한다.

4. 그래프 이론적 표현

홀 결혼 정리는 그래프 이론의 용어로 표현될 수 있다.

유한 이분 그래프 $G=(X\; \backslash cup\; Y,\; E)$를 생각해보자. 여기서 $X$와 $Y$는 각각 정점들의 집합이고, $E$는 $X$의 정점과 $Y$의 정점을 연결하는 간선(모서리)들의 집합이다. 이때 ''$X$-완전 매칭''(또는 ''$X$-포화 매칭'')이란, $X$에 속하는 모든 정점을 포함하는 매칭을 의미한다. 즉, 서로 겹치지 않는 간선들의 집합이면서 $X$의 모든 정점이 적어도 하나의 간선에 연결되어 있는 상태를 말한다.

$X$의 임의의 부분 집합 $W$에 대해, $N\_G(W)$는 $G$에서 $W$의 이웃 집합을 나타낸다. 이는 $W$에 속한 정점들 중 적어도 하나와 인접한 $Y$의 모든 정점들의 집합이다.

홀의 결혼 정리를 그래프 이론의 용어로 표현하면 다음과 같다: 이분 그래프 $G$에서 $X$-완전 매칭이 존재하기 위한 필요충분조건은 $X$의 모든 부분 집합 $W$에 대해 다음 홀의 조건이 성립하는 것이다:

$$|W|\; \backslash leq\; |N\_G(W)|.$$

즉, $X$에서 어떤 부분 집합 $W$를 선택하든, 그 집합에 속한 정점들의 수($|W|$)가 그 정점들과 연결된 $Y$의 이웃 정점들의 수($|N\_G(W)|$)보다 작거나 같아야 한다는 의미이다. 만약 단 하나의 부분 집합 $W$라도 이 조건을 만족하지 못하면($|W|\; >\; |N\_G(W)|$), $X$-완전 매칭은 존재할 수 없다.

이 그래프 이론적 공식은 유한 집합족 $\backslash mathcal\; F$의 고유 대표 시스템(SDR, System of Distinct Representatives)을 찾는 조합론적 문제와 동치이다. 집합족 $\backslash mathcal\; F$와 그 원소들의 합집합 $X$로 이분 그래프 $G=(\backslash mathcal\; F,\; X,\; E)$를 만들 수 있는데, 여기서 간선은 $\backslash mathcal\; F$의 각 집합과 그 집합에 속한 원소를 연결한다. 이 그래프에서 $\backslash mathcal\; F$-완전 매칭은 $\backslash mathcal\; F$의 고유 대표 시스템과 직접적으로 대응된다. 반대로, 어떤 이분 그래프 $G=(X,\; Y,\; E)$가 주어졌을 때, $X$의 각 정점 $x$에 대해 그 이웃 집합 $N\_G(\backslash \{x\backslash \})$들을 모아 집합족을 만들 수 있다. 이 집합족에 대한 고유 대표 시스템을 찾는 것은 그래프 $G$에서 $X$-완전 매칭을 찾는 것과 같다.^[16]

홀의 정리는 유한 집합뿐만 아니라 특정 조건을 만족하는 무한 집합족 및 무한 그래프에도 확장될 수 있다. 이 경우, 각 집합이 유한해야 한다는 조건은 이분 그래프 $G=(X,\; Y,\; E)$에서 $X$의 모든 정점이 유한한 차수(연결된 간선의 수)를 가져야 한다는 조건과 동등하다. $Y$의 정점 차수에는 제한이 없다.

만약 이분 그래프 $G=(X\; \backslash cup\; Y,\; E)$에서 $X$와 $Y$의 크기가 같지 않더라도 홀의 조건을 이용하여 최대 매칭의 크기를 알 수 있다. 즉, $G$에서 크기가 가장 큰 매칭이 $X$의 모든 정점을 포함할(즉, $X$-완전 매칭이 존재할) 필요충분조건은 여전히 $X$의 모든 부분 집합 $W$에 대해 $|W|\; \backslash leq\; |N\_G(W)|$가 성립하는 것이다.

홀의 정리는 이분 그래프에 대한 정리이며, 이를 임의의 일반적인 그래프로 확장한 것이 터트의 정리이다.

4. 1. 그래프 이론적 증명

• $M$을 $G$의 최대 매칭이라 하자. 가정에 의해 $M$은 $X$-완전 매칭이 아니므로, $M$에 의해 매칭되지 않은 정점 $u\; \backslash in\; X$가 존재한다.
• $u$에서 시작하는 모든 ''$M$-교대 경로''( $M$에 속하지 않는 간선과 속하는 간선을 번갈아 사용하는 경로)를 고려한다.
• 이 교대 경로들을 통해 도달할 수 있는 $X$의 정점 집합을 $W$($u$ 포함), $Y$의 정점 집합을 $Z$라고 하자.
• $M$이 최대 매칭이므로, $u$에서 시작하여 $M$에 의해 매칭되지 않은 $Y$의 정점에서 끝나는 $M$-교대 경로(즉, $M$-증가 경로)는 존재하지 않는다. 만약 존재한다면, 경로의 간선들을 바꿔 더 큰 매칭을 만들 수 있기 때문이다.
• 따라서 $Z$의 모든 정점은 $M$에 의해 $W\; \backslash setminus\; \backslash \{u\backslash \}$의 정점과 매칭되고, 반대로 $W\; \backslash setminus\; \backslash \{u\backslash \}$의 모든 정점은 $M$에 의해 $Z$의 정점과 매칭된다. 즉, $M$은 $W\; \backslash setminus\; \backslash \{u\backslash \}$와 $Z$ 사이의 전단사를 정의하므로 $|W\; \backslash setminus\; \backslash \{u\backslash \}|\; =\; |Z|$이고, $|W|\; =\; |Z|\; +\; 1$이다.
• $W$의 이웃 집합 $N\_G(W)$는 $Z$와 같다($N\_G(W)\; =\; Z$). 왜냐하면, $w\; \backslash in\; W$와 연결된 $y\; \backslash in\; Y$가 있다면, 간선 $(w,\; y)$가 $M$에 속하든 아니든 $y$는 $u$에서 시작하는 교대 경로 위에 놓이게 되어 $y\; \backslash in\; Z$이기 때문이다. 따라서 $N\_G(W)\; \backslash subseteq\; Z$이고, 정의상 $Z\; \backslash subseteq\; N\_G(W)$이므로 두 집합은 같다.
• 결론적으로 $|W|\; =\; |Z|\; +\; 1\; =\; |N\_G(W)|\; +\; 1$이므로 $|W|\; >\; |N\_G(W)|$가 되어 홀의 조건 $|W|\; \backslash leq\; |N\_G(W)|$에 모순된다.
• 따라서 처음의 가정($X$-완전 매칭이 존재하지 않는다)은 거짓이며, 홀의 조건이 만족되면 반드시 $X$-완전 매칭이 존재한다.

5. 예

(내용 없음)

5. 1. 조합적 예시

• '''결혼 문제''': $n$명의 남성과 $n$명의 여성이 있다고 가정하자. 각 여성은 자신이 결혼해도 좋다고 생각하는 남성들의 부분 집합을 가지고 있다. 각 남성은 자신과 결혼하고 싶어하는 여성과 결혼할 때 행복하다고 하자. 모든 사람이 행복하게 결혼할 수 있는지(즉, 각 여성이 자신이 선호하는 남성 중 한 명과, 각 남성이 자신을 선호하는 여성 중 한 명과 짝지어질 수 있는지)의 문제는 홀 결혼 정리로 답할 수 있다. $S\_i$를 $i$번째 여성이 결혼해도 좋다고 생각하는 남성들의 집합이라고 하자. 홀 결혼 정리에 따르면, 모든 여성이 행복하게 결혼할 수 있는 필요충분조건은 집합족 $\backslash \{S\_1,\; S\_2,\; \backslash dots,\; S\_n\backslash \}$이 결혼 조건을 만족하는 것이다. 즉, 임의의 여성 부분 집합 $I$에 대해, 그 여성들이 결혼 대상으로 생각하는 남성들의 합집합 $|\backslash bigcup\_\{i\; \backslash in\; I\}\; S\_i|$의 크기가 여성의 수 $|I|$ 이상이어야 한다.

• '''트럼프 카드''': 52장의 표준 트럼프 카드를 4장씩 13개의 묶음으로 나눈다고 하자. 홀 결혼 정리를 적용하면, 각 묶음에서 카드 한 장씩을 뽑아 에이스부터 킹까지 13개의 서로 다른 등급(rank)을 모두 갖추는 것이 항상 가능하다는 것을 보일 수 있다 (무늬는 고려하지 않음). 각 묶음을 집합으로 보고, 각 카드 등급을 원소로 보면, 각 묶음(집합)은 4개의 원소(등급)를 가진다. 13개 묶음 중 임의의 $k$개 묶음을 선택했을 때, 이 묶음들에 포함된 서로 다른 등급의 수는 최소 $k$개 이상임을 보여 결혼 조건을 만족함을 증명할 수 있다.

• '''군 이론''': 어떤 군 $G$와 그 유한 부분군 $H$가 있을 때, 홀 결혼 정리를 이용하여 $G$에서 $H$의 왼쪽 잉여류 집합과 오른쪽 잉여류 집합의 공통된 대표 원소 집합(SDR)이 존재함을 보일 수 있다.

5. 2. 무한 집합의 경우

6. 응용

홀 결혼 정리는 다양한 문제 상황에 적용될 수 있다.

"결혼 조건"이라는 이름은 다음과 같은 가상의 상황에서 유래했다. $n$명의 미혼 이성애자 남성과 $n$명의 미혼 이성애자 여성이 있다고 가정하자. 각 여성 $i$는 자신이 결혼하고자 하는 남성들의 집합 $T\_i$를 가지고 있다. 이때 복혼 없이 모든 여성이 자신이 원하는 남성 중 한 명과 결혼할 수 있는 방법이 존재하는지 알아보는 문제다. 이는 집합족 $\backslash mathcal\; T=\backslash \{T\_i\backslash \}\_\{i=1,\backslash dots,n\}$의 '''횡단'''(橫斷, transversal^영어) 또는 '''변별 대표원계'''(辨別代表元系, system of distinct representatives^영어, SDR)를 찾는 문제와 같다. 홀 결혼 정리는 이러한 결혼이 가능한 필요충분조건을 제공한다. 즉, 여성들의 어떤 부분 집합 $I$를 선택하든, 그 여성들이 결혼하고자 하는 남성들의 총 수($|\backslash bigcup\; \_\{i\; \backslash in\; I\}\; S\_i|$)가 선택된 여성의 수($|I|$)보다 크거나 같아야 한다는 것이다. 만약 이 조건이 성립하지 않으면, $I$에 속한 여성들이 결혼할 수 있는 남성의 수가 부족하다는 의미이므로 이 조건은 필요 조건임이 명백하다. 홀 결혼 정리는 이것이 충분 조건이기도 하다는 점을 밝힌다.^[16]

홀 결혼 정리는 그래프 이론에서도 중요하게 응용된다. 이분 그래프 $G=(X,Y,E)$를 생각해보자. 여기서 $X$와 $Y$는 각각 정점의 집합이고, $E$는 $X$의 정점과 $Y$의 정점을 잇는 간선(모서리)의 집합이다. ''$X$-완전 매칭''(또는 ''$X$-포화 매칭'')이란 $X$의 모든 정점을 포함하는 매칭(서로 겹치지 않는 간선의 집합)을 의미한다. 홀 결혼 정리에 따르면, $X$-완전 매칭이 존재할 필요충분조건은 $X$의 어떤 부분 집합 $W$를 선택하더라도, $W$에 속한 정점들과 연결된 $Y$의 정점들의 집합(이를 $W$의 이웃 $N\_G(W)$라고 한다)의 크기가 $W$의 크기보다 크거나 같은 것이다. 즉, 모든 $W\; \backslash subseteq\; X$에 대하여 $|W|\; \backslash leq\; |N\_G(W)|$가 성립해야 한다.

이 정리는 구체적인 문제 해결에도 사용된다. 예를 들어, 52장의 표준 카드 한 벌을 각각 4장씩 13개의 묶음으로 나누었다고 하자. 홀 결혼 정리를 이용하면, 각 묶음에서 카드를 하나씩 선택하여, 선택된 13장의 카드에 각 숫자(에이스, 2, ..., 킹)가 정확히 하나씩 포함되도록 할 수 있음을 보일 수 있다. 이는 묶음을 한쪽 정점 집합($X$), 숫자를 다른 쪽 정점 집합($Y$)으로 하는 이분 그래프를 구성하고 결혼 조건을 확인하여 증명할 수 있다. 더 나아가, 모든 정규 이분 그래프는 완전 매칭을 가진다는 사실도 홀 결혼 정리로부터 유도될 수 있다.

더 추상적인 수학 분야에서도 응용된다. 군 $G$와 그 부분군 $H$가 유한 지수를 가질 때, 홀 결혼 정리를 사용하여 $G$에서 $H$의 왼쪽 잉여류와 오른쪽 잉여류 모두에 대한 횡단(즉, 각 잉여류에서 대표 원소를 하나씩 고른 집합)이 되는 집합 $T$가 존재함을 보일 수 있다.

또한, $r\; \backslash times\; n$ 크기의 라틴 직사각형이 주어졌을 때 (

홀 결혼 조건은 분수 매칭과도 관련이 있다. 이분 그래프 $G\; =\; (X\; \backslash cup\; Y,\; E)$에서 다음 세 조건은 동치이다:^[13]

• $G$는 $X$-완전 매칭을 갖는다.
• $G$는 $X$-완전 분수 매칭을 갖는다. (분수 매칭은 각 간선에 0 이상의 가중치를 할당하여 각 정점에 연결된 간선들의 가중치 합이 최대 1이 되도록 하는 것이며, $X$-완전 분수 매칭은 $X$의 모든 정점에서 가중치 합이 정확히 1이 되는 경우다.)
• $G$는 홀 결혼 조건을 만족한다.

• '''예시 1:''' 집합족 $\backslash mathcal\{S\}\; =\; \backslash \{S\_1,\; S\_2,\; S\_3\backslash \}$가 다음과 같이 주어졌다고 하자.
• * $S\_1\; =\; \backslash \{1,\; 2,\; 3\backslash \}$
• * $S\_2\; =\; \backslash \{1,\; 4,\; 5\backslash \}$
• * $S\_3\; =\; \backslash \{3,\; 5\backslash \}$

• '''예시 2:''' 집합족 $\backslash mathcal\{S\}\; =\; \backslash \{S\_1,\; S\_2,\; S\_3,\; S\_4\backslash \}$가 다음과 같이 주어졌다고 하자.
• * $S\_1\; =\; \backslash \{2,\; 3,\; 4,\; 5\backslash \}$
• * $S\_2\; =\; \backslash \{4,\; 5\backslash \}$
• * $S\_3\; =\; \backslash \{5\backslash \}$
• * $S\_4\; =\; \backslash \{4\backslash \}$

7. 논리적으로 동등한 정리

홀 결혼 정리는 조합론에서 매우 강력한 여러 정리들과 논리적으로 연결되어 있다. 이 정리들은 서로 밀접하게 관련되어 있어, 한 정리를 이용해 다른 정리를 증명하는 것이 기본적인 원리에서 직접 증명하는 것보다 간단한 경우가 많다. 홀의 정리와 동등하거나 관련된 주요 정리들은 다음과 같다.

• 쾨니그-에게르바리 정리 (1931, 데네스 쾨니그, 예뇌 에게르바리)
• 쾨니그의 정리
• 멩거의 정리 (1927)
• 최대 유량 최소 컷 정리 (Ford–Fulkerson 알고리즘)
• 비르크호프-폰 노이만 정리 (1946)
• 딜워스의 정리

8. 일반화

홀 결혼 정리는 무한 집합의 경우 성립하지 않는다. 예를 들어,

:$T=\backslash \{\backslash mathbb\; N\backslash \}\backslash cup\backslash \{\backslash \{n\backslash \}\backslash colon\; n\backslash in\backslash mathbb\; N\backslash \}\backslash \}$

이라고 하자. 이는 결혼 조건을 만족시키지만, 횡단이 존재하지 않는다.

• 일반 그래프(반드시 이분 그래프일 필요는 없음)에서 완전 매칭의 특징은 튜트 정리에 의해 제공된다.
• 이분 초그래프에 대한 홀 정리의 일반화는 다양한 초그래프에 대한 홀 유형 정리에 의해 제공된다.

9. 추가 설명

집합족 $\backslash mathcal\; T$의 모든 원소가 유한 집합이라고 가정한다. '''홀 결혼 정리'''는 다음 두 조건이 서로 동치임을 나타내는 정리이다.^[16]

• '''결혼 조건'''(marriage condition^영어): 집합족 $\backslash mathcal\; T$의 모든 부분 집합 $\backslash mathcal\; U$에 대하여, $\backslash textstyle|\backslash mathcal\; U|\backslash le\backslash left|\backslash bigcup\backslash mathcal\; U\backslash right|$ 이 성립한다. 이는 어떤 부분 집합족 $\backslash mathcal\; U$를 선택하더라도, 그 안에 포함된 집합들의 개수가 그 집합들의 합집합에 포함된 원소의 개수보다 항상 작거나 같아야 함을 의미한다.
• '''횡단'''(transversal^영어) 또는 '''변별 대표원계'''(system of distinct representatives^영어)의 존재: 다음 조건들을 만족시키는 순서쌍 $(S,f)$가 존재한다.
• * $S$는 $\backslash mathcal\; T$에 속한 모든 집합들의 합집합($\backslash bigcup\backslash mathcal\; T$)의 부분 집합이다. 즉, $S\backslash subset\backslash bigcup\backslash mathcal\; T$ 이다.
• * $f$는 집합 $S$에서 집합족 $\backslash mathcal\; T$로 가는 전단사 함수이다. 즉, $f\backslash colon\; S\backslash to\; \backslash mathcal\; T$ 이다.
• * 집합 $S$의 모든 원소 $s$에 대하여, $s$는 $f(s)$의 원소이다. 즉, $s\backslash in\; f(s)$ 이다. 여기서 $f(s)$는 $\backslash mathcal\; T$에 속한 특정 집합을 나타낸다.

참조

_[1] 문헌 1986
_[2] 문헌 1984
_[3] 학술지 On Forming Committees http://www.jstor.org[...] 2011
_[4] 웹사이트 Graph Theory http://www.sfu.ca/~m[...]
_[5] 학술지 Coset Intersection Graphs for Groups
_[6] 학술지 An existence theorem for latin squares
_[7] 문헌 1986
_[8] 웹페이지 Equivalence of seven major theorems in combinatorics https://web.archive.[...]
_[9] 문헌 1984
_[10] 문헌 1986
_[11] 문헌 1986
_[12] 학술지 König's Duality Theorem for Infinite Bipartite Graphs 1984-02
_[13] 웹사이트 co.combinatorics - Fractional Matching version of Hall's Marriage theorem https://mathoverflow[...] 2020-06-29
_[14] 웹페이지 Equivalence of seven major theorems in combinatorics http://robertborgers[...]
_[15] 저널인용 On representatives of subsets 1935
_[16] 서적인용 새로운 조합수학 http://www.kyowoo.co[...] 교우사 2007