딜워스 정리

최적설계 수치해석 마지막 수정: 2026-08-19 04:13:27

1. 개요[편집]

딜워스 정리 Dilworth's Theorem
발표	Robert P. Dilworth (1950)
진술	유한 poset에서 최대 반사슬 크기 = 최소 사슬 분할 개수
기호	너비 $w(P)$ — width
쌍대	미르스키 정리 (1971) — 최대 사슬 길이 = 최소 반사슬 분할 개수
동치 정리	쾨니그 정리 · 홀의 결혼정리 · 멩거 · 최대유량-최소절단
계산	이분 매칭 한 번 — $O(n^{2.5})$ 수준
대표 응용	DAG 최소 경로 덮개 · 에르되시-세케레시 · 레벨 스케줄링

딜워스 정리(Dilworth’s theorem)는 유한 부분순서집합에서 최대 반사슬의 크기와 그 집합을 덮는 데 필요한 사슬의 최소 개수가 언제나 같다는 최소-최대 정리다. 1950년 로버트 딜워스가 Annals of Mathematics에 발표했다.

용어부터 정리하자. 부분순서집합(partially ordered set, poset) $P$ 에서

사슬(chain)은 원소들이 전부 서로 비교 가능한 부분집합이다. “이건 저것보다 먼저”가 모든 쌍에서 정해지는 줄.
반사슬(antichain)은 어느 두 원소도 비교 불가능한 부분집합이다. 서로 아무 관계 없는 것들의 무더기.

이 둘은 정의부터 정확히 반대다. 그런데 사슬 하나와 반사슬 하나는 원소를 최대 하나만 공유할 수 있으므로(둘 이상 공유하면 그 두 원소가 비교 가능이면서 동시에 비교 불가능해야 한다), 반사슬 $A$ 와 사슬 덮개 $\mathcal{C}$ 에 대해 $|A| \le |\mathcal{C}|$ 가 자명하게 성립한다. 딜워스가 보인 것은 이 부등식이 항상 등식으로 달성된다는 것이다. 그 공통값을 poset의 너비(width) $w(P)$ 라 부른다.

w(P) \;=\; \max_{A \text{ 반사슬}} |A| \;=\; \min_{\mathcal{C} \text{ 사슬 덮개}} |\mathcal{C}|

쾨니그 정리가 그렇듯 이 정리의 값어치는 증명서에 있다. 반사슬 하나와 같은 크기의 사슬 분할 하나를 동시에 손에 쥐면, 양쪽 모두 최적임이 그 자리에서 증명된다. “더는 못 줄이겠는데요”가 근거 있는 문장이 되는 순간이다.

2. 쌍대 — 미르스키 정리[편집]

사슬과 반사슬의 역할을 통째로 바꾸면 어떻게 될까. 미르스키 정리(Mirsky, 1971)가 그 답이다.

유한 poset에서 최대 사슬의 길이는 그 poset을 분할하는 데 필요한 반사슬의 최소 개수와 같다.

재미있는 것은 난이도의 비대칭이다. 미르스키 쪽은 세 줄이면 증명된다. 각 원소 $x$ 에 대해 $x$ 에서 끝나는 최장 사슬의 길이를 $h(x)$ 라 두고 $h$ 가 같은 원소끼리 묶으면, 각 묶음이 반사슬이 된다( $x < y$ 면 반드시 $h(x) < h(y)$ 이므로). 묶음의 개수는 정확히 최장 사슬의 길이다. 반대로 딜워스 쪽은 이런 자연스러운 함수가 없어서, 원래 증명도 귀납이 꽤 번거롭고 이후에 펄커슨(1956)·펄레스(1963)·갤빈(1994)의 짧은 증명들이 따로 나왔다.¹

이 비대칭에는 계산적 대응물도 있다. 미르스키 분할은 위상 정렬 한 번의 부산물이라 $O(n+m)$ 이지만, 딜워스 분할은 아래에서 보듯 매칭을 풀어야 한다.

3. 쾨니그로부터 두 줄 만에 — 최소 경로 덮개[편집]

펄커슨(1956)의 증명이 사실상 알고리즘이다. poset $P$ 의 원소가 $n$ 개일 때 이분 그래프를 이렇게 만든다.

원소 $v$ 마다 왼쪽에 $v_{\text{out}}$ , 오른쪽에 $v_{\text{in}}$ 을 둔다(정점 분할).
$u < v$ 일 때마다 $u_{\text{out}} - v_{\text{in}}$ 간선을 잇는다.

이 이분 그래프에서 매칭 $M$ 을 고르는 것은 “각 원소마다 뒤따르는 원소를 최대 하나 지정하기”이고, 지정 관계를 따라가면 원소들이 여러 개의 사슬로 이어진다. 사슬의 개수는 정확히 $n - |M|$ 이다(간선 하나를 쓸 때마다 덩어리 두 개가 하나로 합쳐지므로). 따라서

\min_{\mathcal{C}} |\mathcal{C}| \;=\; n - \nu(G_{\text{split}})

이고, 여기에 쾨니그 정리의 따름정리 $\alpha = n - \nu$ 를 얹으면 오른쪽이 곧 최대 독립집합의 크기, 즉 최대 반사슬의 크기가 된다. 딜워스 완성. 반대 방향 유도도 알려져 있어 두 정리는 동치다.

여기서 주의할 점 하나. 이분 그래프를 만들 때 간선을 추이 폐포(transitive closure)에 대해 그려야 한다. $u < v < w$ 인데 $u\!-\!w$ 간선을 빼먹으면, 원래 poset에서는 허용되는 사슬 $u \to w$ 를 못 만들어 답이 커진다. DAG로 바꿔 말하면 이렇다.

정점 서로소 최소 경로 덮개(vertex-disjoint minimum path cover)를 DAG의 간선만 써서 구하는 문제 → 위 이분 매칭 그대로. 다항시간.
정점을 공유해도 되는 최소 경로 덮개 → 도달 가능성 관계가 곧 poset이므로 추이 폐포를 먼저 만든 뒤 같은 매칭. 역시 다항시간이고, 이쪽이 딜워스의 원래 진술이다.
사이클이 있는 일반 유향그래프의 최소 경로 덮개 → 덮개가 1개인지 묻는 것이 해밀턴 경로 존재성이므로 NP-난해. 순서 구조가 사라지는 순간 정리가 통째로 무너진다.

비용은 이분 매칭이 지배한다. 홉크로프트-카프로 $O(E\sqrt{V})$ , 추이 폐포까지 세면 대략 $O(n^{2.5})$ 수준이며, 실제 반사슬을 뽑을 때는 쾨니그의 교대 경로 도달 집합을 그대로 재활용한다. 결국 딜워스 정리는 네트워크 흐름 코드 한 덩어리로 전부 계산되는 물건이다.

4. 무한 poset에서는[편집]

유한 조건은 장식이 아니다. 딜워스 정리는 너비가 유한한 poset이면 무한 집합에서도 성립하지만, 너비가 무한이면 “최대 반사슬 크기 = 최소 사슬 덮개 개수”라는 기수(cardinal) 등식은 일반적으로 깨진다. 무한 반사슬이 없는데도 사슬로 가산 개만큼 덮을 수 없는 예가 있다.² 실무에서 다루는 poset은 항상 유한하니 걱정할 일은 없지만, 정리를 “당연히 성립하는 것”으로 외우면 곤란하다는 정도는 기억할 만하다.

5. 에르되시-세케레시가 한 줄로 나온다[편집]

딜워스 정리가 조합론에서 유명한 이유의 절반은 이 따름정리다.

서로 다른 실수 $rs+1$ 개의 수열에는 길이 $r+1$ 의 증가 부분수열 또는 길이 $s+1$ 의 감소 부분수열이 반드시 존재한다.

증명은 다음과 같다. 수열 $a_1,\dots,a_N$ 에 대해 $i \le j$ 이고 $a_i \le a_j$ 일 때 $i \preceq j$ 라 정의하면 이것이 poset이 된다. 이 poset의 사슬 = 증가 부분수열, 반사슬 = 감소 부분수열이다(인덱스는 커지는데 값이 커지지 않아야 비교 불가능이므로). 딜워스에 의해 최대 반사슬이 $s$ 이하이면 poset은 사슬 $s$ 개 이하로 덮이고, 비둘기집에 의해 어떤 사슬은 원소를 $\lceil N/s \rceil$ 개 이상 갖는다. $N = rs+1$ 이면 그 길이가 $r+1$ 이상. 끝.

에르되시와 세케레시가 1935년에 낸 원래 증명은 딜워스보다 15년 앞섰고 방식도 달랐지만, 지금은 이 유도가 표준 교과서 서술이다. 계산 쪽 대응물이 **최장 증가 부분수열**의 $O(n\log n)$ 알고리즘(patience sorting)인데, 이 알고리즘이 만드는 카드 더미의 개수가 정확히 최장 감소 부분수열의 길이 — 즉 알고리즘 자체가 딜워스 분할을 하나 구성한다.³

6. 계산·수치 쪽 접점[편집]

poset이 등장하는 곳은 결국 의존성이 등장하는 곳이고, 그건 수치 소프트웨어의 절반이다.

희소 삼각계 레벨 스케줄링. 희소행렬의 전방/후방 대입은 미지수 사이에 “먼저 풀려야 함” 관계가 있는 DAG다. 여기서 미르스키 분할이 곧 레벨 집합이고, 레벨의 개수는 최장 의존 사슬의 길이 — 즉 임계 경로다. 아무리 코어를 늘려도 레벨 수보다 빨라지지 않는다는 하한이 미르스키 정리의 직접적 귀결이다. GPU에서 삼각 솔브가 안 빨라지는 이유를 한 문장으로 설명하면 “레벨이 많아서”다.
작업 배정과 사슬 덮개. 반대로 딜워스 쪽은 “의존 사슬 몇 개로 작업 전체를 나눌 수 있는가”에 답한다. 사슬 하나를 프로세서 하나에 얹으면 사슬 내부 순서만 지키면 되므로 통신이 사라진다. 너비 $w(P)$ 는 동시에 실행 가능한 작업 수의 상한이자 사슬 기반 분할의 최소 프로세서 수다.
버전 관리·계보 그래프. 커밋 DAG나 데이터 계보에서 “서로 무관해 병합 충돌 위험이 없는 변경 집합”이 반사슬이다.
구간 순서와 스케줄링. 구간들의 poset(끝나야 시작 가능)에서 반사슬은 겹치는 구간들의 집합이고, 딜워스 정리는 “겹침 최대 수 = 필요한 기계 대수”라는 학부 스케줄링 정리를 poset 언어로 다시 말한 것이다. 이 특수 경우는 탐욕으로 $O(n\log n)$ 에 끝나 매칭까지 갈 필요가 없다.

7. 일반화 — 그린-클라이트만[편집]

딜워스 정리는 “반사슬 1개”와 “사슬 덮개”의 관계지만, 이걸 $k$ 개짜리로 밀어붙인 것이 그린-클라이트만 정리(1976)다. 반사슬 $k$ 개의 합집합으로 얻을 수 있는 최대 크기 $d_k(P)$ 는 사슬 덮개 $\mathcal{C}$ 에 대한

d_k(P) \;=\; \min_{\mathcal{C}} \sum_{C \in \mathcal{C}} \min(|C|, k)

로 주어진다. $k=1$ 이 딜워스, 사슬/반사슬을 바꾸면 미르스키의 $k$ -확장이 나온다. 이 계열 결과는 poset의 사슬 덮개들이 이루는 구조가 실은 다면체적임을 시사하고, 실제로 poset의 반사슬 격자와 사슬 다면체는 전체 단모듈성을 통해 정수계획법의 정수성 결과로 이어진다. 조합 최적화 교과서가 딜워스·쾨니그·멩거·홀을 한 장에 몰아넣는 이유가 여기 있다 — 이들은 사실 같은 다면체를 서로 다른 각도에서 본 것이다.⁴

8. 관련 문서[편집]

딜워스 본인의 1950년 논문은 격자 이론(lattice theory) 연구 도중에 나온 부산물에 가깝다. 정작 조합 최적화 쪽에서 이 정리가 유명해진 것은 펄커슨이 1956년에 “쾨니그로 두 줄이면 되는데요”라고 시연한 뒤였다. 순수수학자가 힘들게 증명한 걸 응용수학자가 기존 도구로 재유도해 버리는, 이 바닥에서 종종 벌어지는 광경이다. ↩
대표적인 반례는 펄레스가 정리한 계열이다. 요점만 말하면 “무한 반사슬이 없다”와 “가산 개 사슬로 덮인다”가 무한에서는 갈라진다는 것. 조합론에서 유한 → 무한 확장이 얌전히 되는 경우가 오히려 드물다. ↩
patience sorting은 카드를 한 장씩 보면서 “맨 위 카드가 지금 카드보다 큰 첫 더미”에 얹는 놀이다. 더미의 개수가 최장 증가 부분수열의 길이가 되고, 각 더미가 감소 부분수열이므로 그 자체로 반사슬 분할이다. 카드 게임에서 최소-최대 정리가 튀어나오는 건 몇 번을 봐도 좀 킹받는다. ↩
“최대화 문제의 답 = 최소화 문제의 답” 형태의 정리를 모아 놓고 보면 전부 어떤 LP의 강쌍대성 + 다면체 정수성으로 환원된다. 이 관점을 밀어붙인 것이 에드먼즈·풀커슨 계열의 다면체 조합론이고, 결과적으로 “왜 어떤 조합 문제는 쉬운가”에 대한 가장 그럴듯한 답이 됐다. 물론 어렵다는 쪽의 답은 아직도 P vs NP다. ↩