수학 문제 훈련 2
24 Jun 20264.
램지 정리 R(3,3)=6 증명, n-완전 그래프에서 색 2^n가지 칠하면 무조건 파랑이나 빨강 삼각형. 존재하는 최소숫자.
우선, 5개짜리 그래프를 그리자. 우선 택할 전략은 이거다. K_5에서 가지지 않는 경우 생기는 구조를 다루고(실례를 만드는걸 넘어 강제되는 구조에 대해 논하는것), 거기서 어떻게 점을 추가하건 삼각형이 생긴다는걸 논하는식. 우선 5개에서 한 점이랑 연결된 4개의 선을 칠하자., 4개의 선에서 2개가 같은 색이면, 그 선이 만드는 두 점 사이 색은 달라야 하는게 강제된다. 즉, 4개중 3개의 선이 같은 색이면 삼각형이 발생해 모순- 어, 잠깐 이러면 6개는 단색 삼각형이 반드시 나오는게 즉각 증명이네? 5개 선중 3개는 같은 색을 가져야하니? 흠 암튼, 5개는 그렇게 2개씩 칠하면 그 같은색 칠한 선들끼리 만든 애들의 선은 다른 색으로 칠하고, 4개가 남았는데, 현재 구조 하에선 4개의 선분 모두 색이 강제되지는 않음. 정확히는 저 우리가 처음 잡은 점이 엮인 삼각형에 대해서는 이제 앞으로 완전히 안전한게 보장됨, 왜냐면 걔가 개입하고 아직 완성 안된 삼각형은 두 변이 색이 다르거든, 암튼 그래서 그걸 빼고, K4에서, 두 연결되지 않은 선분이 다른 색으로 칠해진 상황에서 색칠 문제가 되는데, 거기서는 색 하나 고르면 나머지가 다 강제화가 되어 2가지.
풀면서 느낀게, 뭔가 구조적으로 풀려고 할때 아무것도 안되다, 일단 틀리려고 시도하자마자 바로 규칙이 보임,
한 하루종일 생각할때 못풀다가, 그냥 냅다 K5에서 그래프 그리자고 생각하면서 점 하나에 연결된 선분의 색을 쫙 칠해보고 고민하자 하니까 깔끔히 된 느낌.
진짜 오랜만에 답 안보이는 문제 길게 생각해서 푼 느낌,
5.
Hall의 매칭 정리
이분그래프 $G=(X \sqcup Y, E)$에서(X, Y 내부의 점끼리의 간선은 없음)
매칭(간선끼리 만나는 점 없는 간선부분집합)이
X를 포화(간선의 부분집합에 X의 임의의점을 지나는애가 있음)
일 필요충분 조건이, X의 임의의 부분집합에 대해, 부분집합과 간선으로 이웃한 Y의 점 수가 언제나 그 이상.동치인 형식화로,
유한집합족 $(A_i)_{i \in [n]}$, $A := \bigcup_{i \in [n]} A_i$에 대하여,
$f: [n] \hookrightarrow A$ such that $f(i) \in A_i$가 존재할 필요충분조건은
$I \subseteq [n]$에 대해 $\vert\bigcup_{i\in I} A_i\vert \ge \vert I \vert$
이거 동치인거 증명하고, 그 자체도 증명해보자.
우선 동치증명부터.
일단 제일 중요한건, X에서 포화한 매칭은, X의 모든 점을 포화하면서, 해당 점들이 Y에 대해 이웃이고, 이분그래프라 어차피 X-Y의 선분만 있음.
즉, 그러한 매칭을 $f:X \to Y$로 나타낼수 있게된다.
여기서 $x \in X$ 마다 이웃한 Y의 부분집합 $Y_x$을 잡을수 있고, $f(x) \in Y_x$이다.
| 여기서 X, Y모두 유한이므로, $n= | X | $으로 잡으면 2번째 형태의 문제로 변환이 저절로 된다. |
$[n]$을 $X$, $A$를 $Y$로 잡고, $i \in X, a \in A$에 대해 두 간선의 연결을 $a \in A_i$로써 나타내자. 이러면 얘 둘다 유한이라 똑같음,
이 부분은 여기정도만 하면 될거같음.
그러면 증명.
일단 역방향은 아래 알고리즘 돌리면 됨.
우선, Y를 $[|Y|]$로 각 원소를 일대일 대응시킬수 있고 , 거기서 $A_i$를 최댓값이 $I \leftarrow [n]$초기화하고, $I = \varnothing$ 이면 종료.
| 종료 전엔 $ | \bigcup_{i\in I} A_i | \ge | I | > 0$이므로 |
$\bigcup_{i\in I} A_i$에서 임의의 원소 $a$ 선택이 항상 가능, 정의상 강제로 $a \in A_i$인 $i$가 존재함.
$f(i)=a$로 해두고, $I$에서 $i$ 제거
반복하면, 해결.
| 역으로, 존재한다면 언제나 $f(I) \subseteq \bigcup_{i\in I} A_i$ 이고 $ | f(I) | = | I | $이다. |
5-1.
$A$와 집합족 $(A_i) {i \in I}$, $A_i \subseteq A$에 대하여, $f: I \hookrightarrow A$ such that $f(i) \in A_i$가 존재할 필요충분조건은 $I’ \subseteq I$에 대해 $g: I’ \hookrightarrow \bigcup{i\in I’} A_i$ 의 존재. 이게 참인가 거짓인가?
일단 정방향은 참인게,
$i \in I’$에 대해 $f(i) \in A_i \subseteq \bigcup_{i\in I’}A_i$
| 그러니까 $g=f | _{I’}$로 restriction하면 그대로 g가 나온다. |
이제 역방향이 무한이라 알고리즘으로 귀납이 안되어서 머리가 조금 아픈데
사실 고민하고 보니, f가 단사라는 보장이 없어서 위 알고리즘도 멍청하게 틀림.
걍 이렇게 된거 바로 무한을 풀자.
그리고 계속 고민하다가 보니 증명해야할 보조정리가 나옴.
$I \subseteq J, A \subseteq B$이고,
$f: I \hookrightarrow A,\ g: J \hookrightarrow B$ 가 존재하면
$f’:J \hookrightarrow B,\ f’|_I = f$인 $f’$이 존재한다.
일단 이게 된다면, ..아니다.
I, J, A, B 죄다 자연수로 잡고 J에 하나만 원소 추가하고, f가 항등이면 불가능.
걍, 단사함수를 다루는거 자체가 너무 좆같다.
$A$와 집합족 $(A_i) _{i \in I}$, $A_i \subseteq A$에 대하여, $f: I \hookrightarrow A$ such that $f(i) \in A_i$ 이 거짓이라는건
임의의 $f: I \rightarrow A$ such that $f(i) \in A_i$ 가 언제나 함숫값이 같은 두 입력이 존재한다는것.
5-2.
유한집합들로만 이뤄진 집합족 $(A_i) {i \in I}$에 대하여, $f: I \rightarrow \bigcup{i\in I} A_i$ such that $f(i) \in A_i$가 언제나 단사가 아니면 $g: I’ \rightarrow \bigcup_{i\in I’} A_i$가 항상 단사가 아닌 어느 유한 $I’ \subseteq I$가 존재.
일단 참이라면 $A_i$가 유한집합이어야한다고 함, $A = \bigcup_{i\in I} A_i$라 하자.
문제 자체를 어케 풀어야할까.
보조정리
유한집합들로만 이뤄진 집합족 $(A_i) {i \in I}$에 대하여, $f: I \rightarrow \bigcup{i\in I} A_i$ such that $f(i) \ㄹin A_i$가 언제나 단사가 아니면 $g: I’ \rightarrow \bigcup_{i\in I’} A_i$ such that $g(i) \in A_i$가 항상 단사가 아닌 어느 유한 $I’ \subseteq I$가 존재.
proof.
$A_i$에 이산위상을 부여한다. $A_i$가 유한인 덕에, 하우스드로프 컴팩트.
\[X := \prod_{i \in I} A_i\]와 같은 곱공간에서 곱위상을 생각하면, Tychonoff 정리에 의해 하우스드로프 컴팩트.
$x \in X$는 $x:I \to A$, $x(i) \in A_i$인 함수로써 볼 수 있다.
우선 $a \in A$에 대해, $\pi_i^{-1}(a) = \lbrace x \in X: x(i) = a\rbrace$는 열린집합이며
그 교집합인 $\pi_i^{-1}(a) \cap \pi_j^{-1}(a) = \lbrace x \in X: x(i) = x(j) = a\rbrace$ 또한 열린집합
\[C_{ij} := \lbrace{ x \in X: x(i) = x(j) \rbrace} = \bigcup_{a \in A} \pi_i^{-1}(a) \cap \pi_j^{-1}(a)\]또한 열린집합이다 (순회는 $a \in A_i \cap A_j$에서 유한번만 돌아도 되긴 하다)
그리고, 조건 하에 $x \in X$는 단사가 아니며, 즉 $i \neq j$, $x \in C_{ij}$인 어느 $i, j \in I$ 쌍이 존재한다.
따라서 \(X = \bigcup_{i \neq j} C_{ij}\)
은 전체를 덮는 열린덮개가 된다.
컴팩트성에 의해, $X = \bigcup_{k=1}^n C_{i_k,j_k}$인 유한한 덮개가 존재한다. ($n \in \mathbb{N}$)
$I’ = \bigcup_{k=1}^n \lbrace i_k,j_k \rbrace$라 두고
\[X' := \prod_{i \in I'} A_i\] \[C'_{ij} := \lbrace{ x \in X': x(i) = x(j) \rbrace}\]라 하면
\[X' = \bigcup_{k=1}^n C'_{i_k,j_k}\]로 볼 수 있다.
즉, 집합족 $(A_i) {i \in I’}$에 대하여, $g: I’ \rightarrow \bigcup{i\in I} A_i$ such that $g(i) \in A_i$는 언제나 단사가 아니다.
이러면 이제 무한에서 논하던 문제를 유한 매칭 문제로 끌어내린 느낌이긴 한데,
정작 유한 hall 매칭 정리에 대한 감각을 바로 주진 않는다.
그리고 $AC_{fin}$ 필요한거라, 빠지자 걍