Dilworth Theorem #26
Description
- 문제 이름: 딜워스 정리
- 문제 출처: 나
BackGround(패스해도 큰 무리는 없다.)
집합론에서는, 집합에 순서(Order) 를 부여할 수 있다. 대표적인 예로 우리가 아는 실수 체계가 있다. 그러나 실수처럼 모든 원소가 서로 비교가능할 필요는 없다. 실수와 같이 '순서체' 로 만들 수는 없어도, 복소수에도 적당한 순서를 부여하여 순서 집합으로 만들 수 있다.
단 순서 기호 (>= 라 하자) 는 우리의 직관에 부합하는 다음 세 가지 성질 x >=y ---> y <= x, x > =y , y>= z -----> x >= z, x>=x 를 만족시켜야 한다.
순서가 부여된 어떤 집합이 주어졌을 때, 그 집합의 부분집합 S의 모든 원소들이 그 순서 하에서 서로 비교가능할 때 S는 사슬(Chain), S의 원소들 중 어느 두 개도 비교가능하지 않을 때 S는 반사슬(Antichain) 이라고 부른다. 사슬이나 반사슬의 원소 개수를 그 크기로 정의한다.
(집합 P는 유한으로 가정한다.)
이때, P가 Chain 들로 분할되었다면 (P가 전부 커버되기만 하면 각 사슬의 원소가 중복되어도 상관없다) 각 Chain 안의 원소는 서로 비교가능해야 하므로, P의 어떤 Antichain 을 생각하면 그 원소들은 같은 Chain 안에 있을 수 없다. 따라서, P의 사슬에 의한 분할의 크기 >= 반사슬의 크기이다.
이 부등식은 임의의 사슬 분할, 임의의 반사슬에 대하여 적용된다.
이때 딜워스 정리는 다음을 선사한다.
<집합 P의 Antichain 의 최대 크기는 P의 Chain들에 의한 분할의 최소 크기와 같다.>
Models
이를 모델화하는 것은 어렵지 않다. 먼저 Graph에 의한 모델링과 Line diagram 에 의한 것이 있다.
Graph의 각 점은 P의 각 원소를 나타낸다. 이 그래프 G의 두 점은, 오직 두 원소가 비교가능할 때만 간선으로 연결된다. 그러면 G로 순서집합 P를 묘사 가능하다. 이때 사슬은 G의 완전 부분 그래프가 되고 반사슬은 G의 간선없는 부분 그래프가 된다.
그러나 우리는 비교가능성만 생각할 것이지 그 대소에는 신경 쓰지 않으므로, 그래프보다 더 편리한 Line diagram 으로 나타낼 수 있다.