슈페르너의 정리

슈페르너의 정리(독일어: Satz von Sperner, Sperner's theorem, -定理)는 조합적 집합론의 기초적인 정리로, 독일 수학자 에마누엘 슈페르너(독일어: Emmanuel Sperner)가 제시하였다. 이 정리는 수학에서 다루는 가장 기본적인 대상 중 하나인 집합의 개수에 관해 조합론적 기법을 전개할 수 있음을 보였다는 점에서 의미가 있다.

공식화

원소의 개수가 n인 집합 S의 부분집합들의 모임 중 반사슬들을 모은 A는 다음 부등식을 만족한다.

$|A|\leq {n \choose \lfloor {n/2}\rfloor }.$

이를 슈페르너 부등식이라고도 한다. 이 정리를 증명하는 방법은 여러 가지인데, 가장 간단한 것은 LYM 부등식을 이용하는 방법이다. LYM 부등식은 슈페르너 부등식보다 강한 부등식이다. 원래 슈페르너는 LYM 부등식을 이용하지 않고 몇 개의 보조정리를 이용하여 비교적 복잡한 방법으로 이 부등식을 증명하였다. 나중에 네덜란드 수학자 니콜라스 고버르트 더 브라위인(Nicolaas Govert de Bruijn)이 제시한 대칭사슬 분해 기법을 이용하면 또다른 증명도 가능하다.

확장

슈페르너의 정리는 여러 방식으로 확장할 수 있다. 기술한 LYM 부등식이 대표적인 확장 형태이다. 그밖의 것으로 에르되시 팔이 제시한 다음과 같은 정리가 있다.

• 원소의 개수가 n인 집합 S의 부분집합들의 모임 A에서, A에 속하는 S의 부분집합 중 어떤 k+1개도 사슬이 되지 않을 때, 다음 부등식이 성립한다.

$|A|\leq \sum _{i=0}^{k-1}{n \choose \lfloor {(n+i)/2}\rfloor }.$

같이 보기

• LYM 부등식
• 더 브라위인 정리
• 슈페르너 족

참고 문헌

• 윤영진, 《새로운 조합수학》, 교우사, 2007