분류 : 가져온 문서/오메가
Erdős–Ko–Rado theorem
N=\\{1,2,\\cdots,n\\}의 intersecting family의 최대 크기에 대한 정리이다. 집합족 \\mathscr{F}에 대하여 \\mathscr{F}의 모든 집합의 크기가 k이고 임의의 두 집합의 교집합이 공집합이 아닐 때 \\mathscr{F}를 intersecting k-family라 한다. Paul Erdos, Chao Ko, Richard Rado가 1938년에 증명했지만, 23년 후에 발표되었다.
1. 진술 ✎ ⊖
n \\geq 2k일 때, N=\\{1,2,\\cdots,n\\}의 부분집합들로 이루어진 intersecting k-family의 최대 크기는 \\binom{n-1}{k-1}이다.
2. 증명 ✎ ⊖
Gyula Katona의 증명이다. 다음 Lemma를 증명하자.
Lemma 원 위에 일정한 간격으로 점이 n(\\geq 2k)개 찍혀있다. 길이 k개 호들에 대해서 임의의 두 호가 겹치는 부분이 있을 때 호의 개수는 최대 k개이다.
Proof 만약 두 호의 끝점이 같다면 두 호는 같거나(공통인 끝점에서 같은 방향으로 갈 때) 겹치지 않는다(공통인 끝점에서 반대 방향으로 갈 때). 따라서 임의의 두 호는 공통인 끝점을 가지지 않는다.
호 A를 생각하자. 다른 호가 이 호와 겹치기 위해서는 그 끝점이 A의 내부에 있는 k-1개 점 중 하나이어야 한다. 위에서 봤듯이 끝점이 공통일 수는 없으므로 A를 제외한 호는 최대 k-1개 존재한다. 따라서 총 최대 k개의 호가 존재한다.
intersecting k-family \\mathscr{F}를 생각하자. 원 위에 일정한 간격으로 n개의 점을 찍고, n개의 호 옆에 N의 원소를 임의의 순서대로 적자. 원은 (n-1)!(원순열)가지 존재하고, 각 원마다 Lemma에 의해 원소가 원 위에 연속하게 나타나는 \\mathscr{F}의 집합의 개수는 최대 k개이므로(1) 총 세어지는 집합의 개수는 최대 k(n-1)!개이다.
각 집합이 세어지는 원의 개수는 k!(n-k)!개(2)이므로 총 세어지는 집합의 개수는 |\\mathscr{F}|\\ k!(n-k)!개이다. 따라서 다음 부등식이 성립한다.
\\displaystyle |\\mathscr{F}|\\ k!(n-k)! \\leq k(n-1)!
\\displaystyle \\therefore |\\mathscr{F}| \\leq \\frac{k(n-1)!}{k!(n-k)!} = \\binom{n-1}{k-1}
Lemma 원 위에 일정한 간격으로 점이 n(\\geq 2k)개 찍혀있다. 길이 k개 호들에 대해서 임의의 두 호가 겹치는 부분이 있을 때 호의 개수는 최대 k개이다.
Proof 만약 두 호의 끝점이 같다면 두 호는 같거나(공통인 끝점에서 같은 방향으로 갈 때) 겹치지 않는다(공통인 끝점에서 반대 방향으로 갈 때). 따라서 임의의 두 호는 공통인 끝점을 가지지 않는다.
호 A를 생각하자. 다른 호가 이 호와 겹치기 위해서는 그 끝점이 A의 내부에 있는 k-1개 점 중 하나이어야 한다. 위에서 봤듯이 끝점이 공통일 수는 없으므로 A를 제외한 호는 최대 k-1개 존재한다. 따라서 총 최대 k개의 호가 존재한다.
intersecting k-family \\mathscr{F}를 생각하자. 원 위에 일정한 간격으로 n개의 점을 찍고, n개의 호 옆에 N의 원소를 임의의 순서대로 적자. 원은 (n-1)!(원순열)가지 존재하고, 각 원마다 Lemma에 의해 원소가 원 위에 연속하게 나타나는 \\mathscr{F}의 집합의 개수는 최대 k개이므로(1) 총 세어지는 집합의 개수는 최대 k(n-1)!개이다.
각 집합이 세어지는 원의 개수는 k!(n-k)!개(2)이므로 총 세어지는 집합의 개수는 |\\mathscr{F}|\\ k!(n-k)!개이다. 따라서 다음 부등식이 성립한다.
\\displaystyle |\\mathscr{F}|\\ k!(n-k)! \\leq k(n-1)!
\\displaystyle \\therefore |\\mathscr{F}| \\leq \\frac{k(n-1)!}{k!(n-k)!} = \\binom{n-1}{k-1}
이 문서의 내용 중 전체 또는 일부는 오메가에서 가져왔으며 CC BY-NC-SA 3.0에 따라 이용할 수 있습니다.
