Erdos-Ko-Rado

A family F of a set이 을 만족시키면 F는 intersecting 또는 intersecting family라 부른다. n>=2k, F는 a family of k-subsets of 라 하자. Erdos-Ko-Rado theorem은 F가 intersecting family이면 라는 것이다. 등호의 경우는 한 점을 항상 들어가게 하고 남은 n-1 멤버중에서 k-1개 골라주면 된다.

G. Katona의 확률론적 증명을 소개할 것이고(매우 짧지만, 다른 증명들이 길다는 걸 생각하면 강력...), 모두 Alon, Spencer의 The Probablistic Method에 잇다.

Lemma.

이라 하면, F는 기껏 해봐야 k개의 A_s를 가지고 잇다. 어떤 l에 대해, 라 해보자. 그럼 A_s들 중에서 A_l이랑 intersect하는 것은 2k-2개가 잇는데(A_l 빼고) 이들은 k-1개의 nonintersecting pair로 정리할 수 잇다(평행이동하면서). 그렇다면 F는 저 각각의 k-1개의 pair에서 기껏 해봐야 하나밖에 못 가진다.

Erdos-Ko-Rado theorem을 증명해보자. n-set 의 permutation 와 가 uniformly, independently, randomly 골라진다고 하자. 라 하면, lemma에 의해 각각의 sigma에 대해 A가 F에 속할 확률이 k/n을 넘지 못한다(n-set은 아무리 섞어봐야 n-set이다). 따라서

A는 모든 k-subset을 uniform하게 취하므로,

따라서

어머나. 지금 저 확률론 책을 보고잇는데 참 재밋는 것들이 많다. 확률론의 힘을 이해하고 처음으로 응용하기 시작한 사람도 Erdos라 한다. 우왕