슈페르너의 정리 문서 원본 보기

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

== 공식화 ==
원소의 개수가 n인 집합 S의 [[부분집합]]들의 모임 중 [[반사슬]]들을 모은 A는 다음 부등식을 만족한다.<ref>윤영진, 《새로운 조합수학》, 교우사, 2007, 284쪽.</ref>

:<math>|A| \le {n \choose \lfloor{n/2}\rfloor}.</math>

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

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

* 원소의 개수가 n인 집합 S의 [[부분집합]]들의 모임 A에서, A에 속하는 S의 부분집합 중 어떤 k+1개도 [[사슬]]이 되지 않을 때, 다음 부등식이 성립한다.
: <math>|A| \le \sum_{i=0}^{k-1} {n \choose \lfloor{(n+i)/2}\rfloor}.</math>

== 같이 보기 ==
* [[LYM 부등식]]
* [[더 브라위인 정리]]
* [[슈페르너 족]]

== 각주 ==
{{각주}}

== 참고 문헌 ==
* 윤영진, 《새로운 조합수학》, 교우사, 2007

[[분류:집합족]]
[[분류:조합적 집합론]]
[[분류:계승과 이항식 주제]]
[[분류:부등식]]