슈페르너의 정리
보이기
슈페르너의 정리(독일어: Satz von Sperner, Sperner's theorem, -定理)는 조합적 집합론의 기초적인 정리로, 독일 수학자 에마누엘 슈페르너(독일어: Emmanuel Sperner)가 제시하였다. 이 정리는 수학에서 다루는 가장 기본적인 대상 중 하나인 집합의 개수에 관해 조합론적 기법을 전개할 수 있음을 보였다는 점에서 의미가 있다.
공식화
[편집]원소의 개수가 n인 집합 S의 부분집합들의 모임 중 반사슬들을 모은 A는 다음 부등식을 만족한다.[1]
이를 슈페르너 부등식이라고도 한다. 이 정리를 증명하는 방법은 여러 가지인데, 가장 간단한 것은 LYM 부등식을 이용하는 방법이다. LYM 부등식은 슈페르너 부등식보다 강한 부등식이다. 원래 슈페르너는 LYM 부등식을 이용하지 않고 몇 개의 보조정리를 이용하여 비교적 복잡한 방법으로 이 부등식을 증명하였다.[2] 나중에 네덜란드 수학자 니콜라스 고버르트 더 브라위인(Nicolaas Govert de Bruijn)이 제시한 대칭사슬 분해 기법을 이용하면 또다른 증명도 가능하다.[3]
확장
[편집]슈페르너의 정리는 여러 방식으로 확장할 수 있다. 기술한 LYM 부등식이 대표적인 확장 형태이다. 그밖의 것으로 에르되시 팔이 제시한 다음과 같은 정리가 있다.[4]
같이 보기
[편집]각주
[편집]참고 문헌
[편집]- 윤영진, 《새로운 조합수학》, 교우사, 2007