티스토리 뷰

수학/이산수학

Erdős–Ko–Rado 정리

leejseo 2017. 7. 29. 01:54

Theorem. $A$가 $[n]$의 몇몇 부분집합들로 이루어진 집합이라고 하자. 모든 $A$의 원소는 크기가 $r$이고, 임의의 두 $x, y \in A$에 대해 $x \cap y \neq \emptyset$이다. 이 때, $A$의 크기는 $\pmatrix{ n-1 \\ r-1 }$ 이하이다. (이 때, $ n \geq 2r$이다.)


Proof. 

이 정리에 대한 증명은 단순한 더블카운팅으로 가능하다.


$[n]$과 $A$가 주어졌다고 가정하자. 이제, 우리는 원주상에 $[n]$의 원소들을 cyclic order로 배열을 하고, $A$에서 길이가 $r$인 구간들에 대해 생각할 것이다. 예를 들어, $n = 6$이고 $r = 2$이고, cyclic order $(1, 5, 4, 2, 3, 6)$을 택한 경우, $(1,5), (5, 4), (4, 2), (2, 3), (3, 6), (6, 1)$의 총 6가지의 구간들이 있다. 그런데, 여기에서 우리가 관찰할 수 있는 것은 cyclic order의 interval 가운데 항상 모든 것이 $A$에 속할 수 있는 것은 아니라는 것이다. 왜냐하면 이들 가운데 일부는 disjoint 하기 때문이다. 여기에서 이제 $A$에 속하는 구간의 수는 많아야 $r$임을 알 수 있다.


이제, 이 아이디어를 기반해 $S \in A$와 cyclic order $C$에 대하여 순서쌍 $(S, C)$를 세자. 먼저, 각각의 $S$는 자신을 구간으로서 포함하는 $C$를 generate 할 때, $r!(n-r)!$가지의 경우가 생긴다. 따라서, $S$를 기준으로 카운트하면, 총 $|A| r! (n-r)!$가지가 된다.


이제는 $C$를 기준으로 카운트하여 upper bound를 잡자. 아까 위에서 밝힌 사실에 의하면 각각의 cyclic order에 대해 $A$에 속하는 구간의 수는 많아야 $r$개이다. 또한, 총 cyclic order의 수는 $(n-1)!$ 가지이다. 따라서 $|A| r! (n-r)! \leq r(n-1)!$을 얻게되고, 이것은 $|A| \leq \pmatrix{n-1 \\ r-1}$임을 의미한다.


(등호 성립 조건: 하나의 원소를 택해서 그 원소를 포함하는 $r$-subset들로 $A$를 구성하면 등호가 성립함.)

'수학 > 이산수학' 카테고리의 다른 글

고정된 크기의 클릭의 수  (0) 2018.04.11
Projective Plane의 Blocking Set의 크기  (0) 2018.02.03
2N개의 점들  (0) 2018.01.01
그들 사이의 거리  (0) 2017.09.18
Erdős–Ko–Rado 정리  (0) 2017.07.29
간단한 poset을 이용하는 문제  (0) 2017.07.27
댓글
댓글쓰기 폼