Erdős–Ko–Rado 정리 (원본) (3)

[[분류:가져온 문서/오메가]]
Erdős–Ko–Rado theorem

[math(N=\{1,2,\cdots,n\})]의 intersecting family의 최대 크기에 대한 정리이다. 집합족 [math(\mathscr{F})]에 대하여 [math(\mathscr{F})]의 모든 집합의 크기가 [math(k)]이고 임의의 두 집합의 교집합이 공집합이 아닐 때 [math(\mathscr{F})]를 intersecting k-family라 한다. [[폴 에르되시|Paul Erdos]], Chao Ko, Richard Rado가 1938년에 증명했지만, 23년 후에 발표되었다. 이 정리는 조합론의 극단 집합론 분야에서 중요한 위치를 차지하며, 다양한 응용 분야를 가진다.

== 진술 ==
[math(n \geq 2k)]일 때, [math(N=\{1,2,\cdots,n\})]의 부분집합들로 이루어진 intersecting k-family의 최대 크기는 [math(\binom{n-1}{k-1})]이다.

== 증명 ==
Gyula Katona의 증명이다. 다음 '''Lemma'''를 증명하자.

'''Lemma''' 원 위에 일정한 간격으로 점이 [math(n(\geq 2k))]개 찍혀있다. 길이 [math(k)]개 호들에 대해서 임의의 두 호가 겹치는 부분이 있을 때 호의 개수는 최대 [math(k)]개이다.

'''Proof''' 만약 두 호의 끝점이 같다면 두 호는 같거나(공통인 끝점에서 같은 방향으로 갈 때) 겹치지 않는다(공통인 끝점에서 반대 방향으로 갈 때). 따라서 임의의 두 호는 공통인 끝점을 가지지 않는다.

호 [math(A)]를 생각하자. 다른 호가 이 호와 겹치기 위해서는 그 끝점이 [math(A)]의 내부에 있는 [math(k-1)]개 점 중 하나이어야 한다. 위에서 봤듯이 끝점이 공통일 수는 없으므로 [math(A)]를 제외한 호는 최대 [math(k-1)]개 존재한다. 따라서 총 최대 [math(k)]개의 호가 존재한다.

intersecting k-family [math(\mathscr{F})]를 생각하자. 원 위에 일정한 간격으로 [math(n)]개의 점을 찍고, [math(n)]개의 호 옆에 [math(N)]의 원소를 임의의 순서대로 적자. 원은 [math((n-1)!)](원순열)가지 존재하고, 각 원마다 '''Lemma'''에 의해 원소가 원 위에 연속하게 나타나는 [math(\mathscr{F})]의 집합의 개수는 최대 [math(k)]개이므로[* 원소가 연속하게 나타나는 집합을 원 위에 표시하면 길이 [math(k)]인 호들이 되는데, [math(\mathscr{F})]가 intersecting k-family이므로 이 호 중 임의의 두 호를 잡으면 겹치는 부분이 존재한다. 따라서 '''Lemma'''의 조건을 만족한다.] 총 세어지는 집합의 개수는 최대 [math(k(n-1)!)]개이다.

각 집합이 세어지는 원의 개수는 [math(k!(n-k)!)]개[* 집합 내 원소를 나열하고, 그 외 원소를 나열한다]이므로 총 세어지는 집합의 개수는 [math(|\mathscr{F}|\ k!(n-k)!)]개이다. 따라서 다음 부등식이 성립한다.

[math(\displaystyle |\mathscr{F}|\ k!(n-k)! \leq k(n-1)!)]

[math(\displaystyle \therefore |\mathscr{F}| \leq \frac{k(n-1)!}{k!(n-k)!} = \binom{n-1}{k-1})]

[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]