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년 후에 발표되었다. 이 정리는 조합론의 극단 집합론 분야에서 중요한 위치를 차지하며, 다양한 응용 분야를 가진다.
n \\geq 2k일 때, N=\\{1,2,\\cdots,n\\}의 부분집합들로 이루어진 intersecting k-family의 최대 크기는 \\binom{n-1}{k-1}이다.
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}
