미르스키의 정리

수학에서, 질서가론과 결합론의 영역에서, 미르스키의 정리는 질서의 분할이라는 관점에서 정해진 유한한 부분 순서의 높이를 최소의 반점수로 특징짓는다.레온 미르스키(1971)의 이름을 따서 지었으며, 딜워스의 부분 순서 폭 정리, 비교가능성 그래프의 완성도 , 그래프에서 가장 긴 경로와 색상을 연관시킨 갈라이-하세-로이-비타버 정리, 단조적 반복에 관한 에르드드-스-제케레스 정리 등과 밀접한 관련이 있다.

정리

부분적으로 정렬된 집합의 높이는 체인의 최대 카디널리티로 정의되며, 주어진 부분 순서의 완전히 정렬된 부분 집합이다.예를 들어, 1에서 N까지의 양의 정수 집합에서, 구별에 의해 명령된 가장 큰 체인 중 하나는 그 범위 내에 있는 두 개의 힘으로 구성되며, 여기서부터 이 부분 순서의 $1+\lfloor \log _{2}N\rfloor$ 는 $1+\lfloor \log _{2}N\rfloor$ 1 + $1+\lfloor \log _{2}N\rfloor$ + $1+\lfloor \log _{2}N\rfloor$ 2 $1+\lfloor \log _{2}N\rfloor$ N $1+\lfloor \log _{2}N\rfloor$ {\ $displaystyle$ 1 $+\llllfloor \log _{2}N\rfloor }$ 이다 $1+\lfloor \log _{2}N\rfloor$

미르스키의 정리는 모든 유한한 부분 순서의 집합에 대해 높이가 집합이 분할될 수 있는 최소 항적수(원소 쌍이 정렬되지 않은 하위 집합)와 동일하다고 명시하고 있다.그런 칸막이에서는 가장 긴 사슬의 두 원소가 모두 서로 다른 두 개의 반점 속으로 들어가야 하므로 항골의 수는 항상 높이보다 크거나 같으며, 미르스키의 또 다른 정리의 공식은 항골의 수가 키와 동일한 칸막이 항상 존재한다는 것이다.다시 말하지만, 구별에 의해 정렬된 양의 정수의 예에서, 숫자는 반점 {1, {2,3}, {4,5,6,7} 등으로 분할될 수 있다.이 칸막이에는 $1+\lfloor \log _{2}N\rfloor$ + $1+\lfloor \log _{2}N\rfloor$ $1+\lfloor \log _{2}N\rfloor$ 2 $1+\lfloor \log _{2}N\rfloor$ { $1+\lfloor \log _{2}N\rfloor$ $1+\lfloor \log _{2}N\rfloor$ {\ $displaystyle$ 1 $+\lfloor \log _{2}$ N\rfloor $}$ 세트가 $1+\lfloor \log _{2}N\rfloor$ 있으며, 이 각 세트 내에서 모든 한 쌍의 숫자가 2 미만의 비율을 형성하므로 이들 세트 내에서 두 개 내의 숫자는 분할할 수 없다.

임의의 유한한 부분 순서가 정해진 집합에 대해 적은 수의 반점들로 칸막이가 존재함을 증명하기 위해, x가 있는 모든 요소 x 체인을 가장 큰 요소로 간주하고, N(x)가 이러한 x-최대 체인 중 가장 큰 체인의 크기를 나타내도록 한다.그러면 N의 값이 같은 원소로 구성된 각각의 집합 N⁻¹(i)은 반제(antichain)이며, 이들 반제(antichain)는 부분 순서를 가장 큰 사슬의 크기와 같은 수의 반제(antichain)로 분할한다.그의 원본 증명에서 미르스키는 가장 긴 사슬의 최대 원소들의 반감을 선택하고, 나머지 원소들 중에서 가장 긴 사슬의 길이가 한 개씩 줄어든다는 것을 보여줌으로써 동일한 사슬을 귀납적으로 구성한다.

확장

미르스키의 정리는 높이가 유한한 무한 부분 순서 세트로 바로 확장된다.그러나 체인의 길이와 칸막이의 반창고 수 사이의 관계는 무한 추기경까지 확장되지 않는다: 무한 추기경 숫자 κ마다, 무한 체인이 없고 with 이하의 반창고를 가진 반창고 칸막이가 없는 부분 순서 집합이 존재한다(Schmerl 2002).

참조

Dilworth, Robert P. (1950), "A Decomposition Theorem for Partially Ordered Sets", Annals of Mathematics, 51 (1): 161–166, doi:10.2307/1969503, JSTOR 1969503.
Golumbic, Martin Charles (1980), "5.7. Coloring and other problems on comparability graphs", Algorithmic Graph Theory and Perfect Graphs, New York: Academic Press, pp. 132–135, ISBN 0-12-289260-7, MR 0562306.
Lovász, László (1972), "Normal hypergraphs and the perfect graph conjecture", Discrete Mathematics, 2 (3): 253–267, doi:10.1016/0012-365X(72)90006-4.
Mirsky, Leon (1971), "A dual of Dilworth's decomposition theorem", American Mathematical Monthly, 78 (8): 876–877, doi:10.2307/2316481, JSTOR 2316481.
Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Theorem 3.13", Sparsity: Graphs, Structures, and Algorithms (PDF), Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 42, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
Schmerl, James H. (2002), "Obstacles to extending Mirsky's theorem", Order, 19 (2): 209–211, doi:10.1023/A:1016541101728, MR 1922918, S2CID 26514679.

Search

미르스키의 정리

네임스페이스

더

목차

정리

관련결과

딜워스의 정리

갈라이-하세-로이-비타버 정리

에르드스-제케레스 정리

확장

참조