156:
different antichains, so the number of antichains is always greater than or equal to the height; another formulation of Mirsky's theorem is that there always exists a partition for which the number of antichains equals the height. Again, in the example of positive integers ordered by divisibility, the numbers can be partitioned into the antichains {1}, {2,3}, {4,5,6,7}, etc. There are
236:, is an antichain, and these antichains partition the partial order into a number of antichains equal to the size of the largest chain. In his original proof, Mirsky constructs the same partition inductively, by choosing an antichain of the maximal elements of longest chains, and showing that the length of the longest chain among the remaining elements is reduced by one.
285:
of a partially ordered set, a clique represents a chain and a coloring represents a partition into antichains, and induced subgraphs of comparability graphs are themselves comparability graphs, so Mirsky's theorem states that comparability graphs are perfect. Analogously, Dilworth's theorem states
155:
Mirsky's theorem states that, for every finite partially ordered set, the height also equals the minimum number of antichains (subsets in which no pair of elements are ordered) into which the set may be partitioned. In such a partition, every two elements of the longest chain must go into two
261:
ordering of points in general position in the plane is an antichain in the set of points formed by a 90° rotation from the original set, and vice versa) but for more general partial orders the two theorems differ, and (as Mirsky observes) Dilworth's theorem is more difficult to prove.
419:
Mirsky's theorem extends immediately to infinite partially ordered sets with finite height. However, the relation between the length of a chain and the number of antichains in a partition into antichains does not extend to infinite cardinalities: for every infinite
350:
gives the longest chain in the reachability ordering, and the sets of vertices with the same image in a homomorphism to a transitive tournament form a partition into antichains. This statement generalizes to the case that
199:
150:
253:, stating that, for every partially ordered set, the maximum size of an antichain equals the minimum number of chains in a partition of the set into chains. For sets of
201:
sets in this partition, and within each of these sets, every pair of numbers forms a ratio less than two, so no two numbers within one of these sets can be divisible.
298:
states that the complements of perfect graphs are always perfect, and can be used to deduce
Dilworth's theorem from Mirsky's theorem and vice versa (
424:κ, there exist partially ordered sets that have no infinite chain and that do not have an antichain partition with κ or fewer antichains (
204:
To prove the existence of a partition into a small number of antichains for an arbitrary finite partially ordered set, consider for every element
356:
64:
1315:
1298:
828:
664:
586:
1145:
1358:
1281:
1140:
484:
1135:
159:
110:
771:
853:
507:
1172:
1092:
533:
396:
76:
957:
886:
766:
860:
848:
811:
786:
761:
715:
684:
1157:
791:
781:
657:
364:
379:
It follows from either
Dilworth's theorem or Mirsky's theorem that, in every partially ordered set of
1130:
796:
331:
1062:
689:
566:
403: + 1 totally ordered elements there must exist a monotonically increasing subsequence of
1353:
1310:
1293:
472:
1222:
838:
562:
311:
1348:
1200:
1035:
1026:
895:
776:
730:
694:
650:
443:
291:
265:
Mirsky's theorem and
Dilworth's theorem are also related to each other through the theory of
250:
52:
36:
502:
1288:
1247:
1237:
1227:
972:
935:
925:
905:
890:
627:
596:
494:
107:
that lie within that range, from which it follows that the height of this partial order is
95:
subset of the given partial order. For instance, in the set of positive integers from 1 to
68:
8:
1215:
1126:
1072:
1031:
1021:
910:
843:
282:
60:
1327:
1254:
1107:
1016:
1006:
947:
865:
801:
631:
550:
460:
438:
395:
uses this observation, applied to a partial order of order dimension two, to prove the
319:
1167:
1264:
1242:
1102:
1087:
1067:
870:
582:
520:
480:
635:
87:
The height of a partially ordered set is defined to be the maximum cardinality of a
1077:
930:
615:
574:
542:
516:
452:
287:
278:
274:
1259:
1042:
920:
915:
900:
816:
725:
710:
623:
606:
592:
490:
421:
254:
573:, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 42,
1177:
1162:
1152:
1011:
989:
967:
360:
72:
619:
578:
1342:
1276:
1232:
1210:
1082:
952:
940:
745:
270:
266:
56:
28:
1097:
979:
962:
880:
720:
673:
315:
258:
104:
100:
24:
1303:
996:
875:
740:
528:
92:
44:
20:
1271:
1205:
1046:
554:
464:
339:
1322:
1195:
1001:
604:
Schmerl, James H. (2002), "Obstacles to extending Mirsky's theorem",
407: + 1 elements or a monotonically decreasing subsequence of
88:
40:
546:
475:(1980), "5.7. Coloring and other problems on comparability graphs",
456:
1117:
984:
735:
642:
505:(1972), "Normal hypergraphs and the perfect graph conjecture",
441:(1950), "A Decomposition Theorem for Partially Ordered Sets",
39:
in terms of a partition of the order into a minimum number of
16:
Characterizes the height of any finite partially ordered set
334:
if and only if there does not exist a homomorphism from a (
346:. For, the largest path graph that has a homomorphism to
318:
of their vertices), as the statement that there exists a
561:
368:
531:(1971), "A dual of Dilworth's decomposition theorem",
383: + 1 elements, there must exist a chain of
162:
113:
232:), consisting of elements that have equal values of
305:
193:
144:
1340:
257:two, the two theorems coincide (a chain in the
479:, New York: Academic Press, pp. 132–135,
281:equals the size of the largest clique. In the
658:
310:Mirsky's theorem can be restated in terms of
571:Sparsity: Graphs, Structures, and Algorithms
194:{\displaystyle 1+\lfloor \log _{2}N\rfloor }
188:
169:
145:{\displaystyle 1+\lfloor \log _{2}N\rfloor }
139:
120:
103:, one of the largest chains consists of the
477:Algorithmic Graph Theory and Perfect Graphs
387: + 1 elements or an antichain of
1316:Positive cone of a partially ordered group
665:
651:
220:) denote the size of the largest of these
374:
314:(representing a partially ordered set by
290:of a comparability graph is perfect. The
1299:Positive cone of an ordered vector space
471:
437:
299:
55:on the widths of partial orders, to the
603:
425:
35:characterizes the height of any finite
1341:
527:
501:
392:
295:
48:
646:
355:is not acyclic, and is a form of the
244:
369:Nešetřil & Ossona de Mendez 2012
322:from a given directed acyclic graph
13:
826:Properties & Types (
239:
212:as their largest element, and let
14:
1370:
1282:Positive cone of an ordered field
1136:Ordered topological vector space
672:
357:Gallai–Hasse–Roy–Vitaver theorem
306:Gallai–Hasse–Roy–Vitaver theorem
65:Gallai–Hasse–Roy–Vitaver theorem
224:-maximal chains. Then each set
82:
1:
1093:Series-parallel partial order
534:American Mathematical Monthly
431:
414:
772:Cantor's isomorphism theorem
521:10.1016/0012-365X(72)90006-4
51:) and is closely related to
7:
812:Szpilrajn extension theorem
787:Hausdorff maximal principle
762:Boolean prime ideal theorem
79:on monotonic subsequences.
10:
1375:
1158:Topological vector lattice
399:that in every sequence of
1359:Theorems in combinatorics
1188:
1116:
1055:
825:
754:
703:
680:
579:10.1007/978-3-642-27875-4
567:Ossona de Mendez, Patrice
411: + 1 elements.
391: + 1 elements.
269:. An undirected graph is
767:Cantor–Bernstein theorem
569:(2012), "Theorem 3.13",
473:Golumbic, Martin Charles
1311:Partially ordered group
1131:Specialization preorder
620:10.1023/A:1016541101728
338: + 1)-vertex
312:directed acyclic graphs
249:Mirsky was inspired by
797:Kruskal's tree theorem
792:Knaster–Tarski theorem
782:Dushnik–Miller theorem
397:Erdős–Szekeres theorem
375:Erdős–Szekeres theorem
195:
146:
77:Erdős–Szekeres theorem
75:in graphs, and to the
444:Annals of Mathematics
332:transitive tournament
292:perfect graph theorem
208:the chains that have
196:
147:
37:partially ordered set
1289:Ordered vector space
508:Discrete Mathematics
160:
111:
61:comparability graphs
1127:Alexandrov topology
1073:Lexicographic order
1032:Well-quasi-ordering
439:Dilworth, Robert P.
283:comparability graph
1108:Transitive closure
1068:Converse/Transpose
777:Dilworth's theorem
563:Nešetřil, Jaroslav
320:graph homomorphism
251:Dilworth's theorem
245:Dilworth's theorem
191:
142:
53:Dilworth's theorem
43:. It is named for
23:, in the areas of
1336:
1335:
1294:Partially ordered
1103:Symmetric closure
1088:Reflexive closure
831:
588:978-3-642-27874-7
1366:
1078:Linear extension
827:
807:Mirsky's theorem
667:
660:
653:
644:
643:
638:
599:
557:
523:
497:
467:
288:complement graph
279:chromatic number
275:induced subgraph
200:
198:
197:
192:
181:
180:
151:
149:
148:
143:
132:
131:
33:Mirsky's theorem
1374:
1373:
1369:
1368:
1367:
1365:
1364:
1363:
1339:
1338:
1337:
1332:
1328:Young's lattice
1184:
1112:
1051:
901:Heyting algebra
849:Boolean algebra
821:
802:Laver's theorem
750:
716:Boolean algebra
711:Binary relation
699:
676:
671:
589:
547:10.2307/2316481
487:
457:10.2307/1969503
434:
422:cardinal number
417:
377:
361:graph colorings
308:
255:order dimension
247:
242:
240:Related results
176:
172:
161:
158:
157:
127:
123:
112:
109:
108:
93:totally ordered
85:
45:Leon Mirsky
17:
12:
11:
5:
1372:
1362:
1361:
1356:
1354:Perfect graphs
1351:
1334:
1333:
1331:
1330:
1325:
1320:
1319:
1318:
1308:
1307:
1306:
1301:
1296:
1286:
1285:
1284:
1274:
1269:
1268:
1267:
1262:
1255:Order morphism
1252:
1251:
1250:
1240:
1235:
1230:
1225:
1220:
1219:
1218:
1208:
1203:
1198:
1192:
1190:
1186:
1185:
1183:
1182:
1181:
1180:
1175:
1173:Locally convex
1170:
1165:
1155:
1153:Order topology
1150:
1149:
1148:
1146:Order topology
1143:
1133:
1123:
1121:
1114:
1113:
1111:
1110:
1105:
1100:
1095:
1090:
1085:
1080:
1075:
1070:
1065:
1059:
1057:
1053:
1052:
1050:
1049:
1039:
1029:
1024:
1019:
1014:
1009:
1004:
999:
994:
993:
992:
982:
977:
976:
975:
970:
965:
960:
958:Chain-complete
950:
945:
944:
943:
938:
933:
928:
923:
913:
908:
903:
898:
893:
883:
878:
873:
868:
863:
858:
857:
856:
846:
841:
835:
833:
823:
822:
820:
819:
814:
809:
804:
799:
794:
789:
784:
779:
774:
769:
764:
758:
756:
752:
751:
749:
748:
743:
738:
733:
728:
723:
718:
713:
707:
705:
701:
700:
698:
697:
692:
687:
681:
678:
677:
670:
669:
662:
655:
647:
641:
640:
614:(2): 209–211,
601:
587:
559:
541:(8): 876–877,
525:
515:(3): 253–267,
503:Lovász, László
499:
485:
469:
451:(1): 161–166,
433:
430:
416:
413:
376:
373:
307:
304:
267:perfect graphs
246:
243:
241:
238:
190:
187:
184:
179:
175:
171:
168:
165:
141:
138:
135:
130:
126:
122:
119:
116:
84:
81:
15:
9:
6:
4:
3:
2:
1371:
1360:
1357:
1355:
1352:
1350:
1347:
1346:
1344:
1329:
1326:
1324:
1321:
1317:
1314:
1313:
1312:
1309:
1305:
1302:
1300:
1297:
1295:
1292:
1291:
1290:
1287:
1283:
1280:
1279:
1278:
1277:Ordered field
1275:
1273:
1270:
1266:
1263:
1261:
1258:
1257:
1256:
1253:
1249:
1246:
1245:
1244:
1241:
1239:
1236:
1234:
1233:Hasse diagram
1231:
1229:
1226:
1224:
1221:
1217:
1214:
1213:
1212:
1211:Comparability
1209:
1207:
1204:
1202:
1199:
1197:
1194:
1193:
1191:
1187:
1179:
1176:
1174:
1171:
1169:
1166:
1164:
1161:
1160:
1159:
1156:
1154:
1151:
1147:
1144:
1142:
1139:
1138:
1137:
1134:
1132:
1128:
1125:
1124:
1122:
1119:
1115:
1109:
1106:
1104:
1101:
1099:
1096:
1094:
1091:
1089:
1086:
1084:
1083:Product order
1081:
1079:
1076:
1074:
1071:
1069:
1066:
1064:
1061:
1060:
1058:
1056:Constructions
1054:
1048:
1044:
1040:
1037:
1033:
1030:
1028:
1025:
1023:
1020:
1018:
1015:
1013:
1010:
1008:
1005:
1003:
1000:
998:
995:
991:
988:
987:
986:
983:
981:
978:
974:
971:
969:
966:
964:
961:
959:
956:
955:
954:
953:Partial order
951:
949:
946:
942:
941:Join and meet
939:
937:
934:
932:
929:
927:
924:
922:
919:
918:
917:
914:
912:
909:
907:
904:
902:
899:
897:
894:
892:
888:
884:
882:
879:
877:
874:
872:
869:
867:
864:
862:
859:
855:
852:
851:
850:
847:
845:
842:
840:
839:Antisymmetric
837:
836:
834:
830:
824:
818:
815:
813:
810:
808:
805:
803:
800:
798:
795:
793:
790:
788:
785:
783:
780:
778:
775:
773:
770:
768:
765:
763:
760:
759:
757:
753:
747:
746:Weak ordering
744:
742:
739:
737:
734:
732:
731:Partial order
729:
727:
724:
722:
719:
717:
714:
712:
709:
708:
706:
702:
696:
693:
691:
688:
686:
683:
682:
679:
675:
668:
663:
661:
656:
654:
649:
648:
645:
637:
633:
629:
625:
621:
617:
613:
609:
608:
602:
598:
594:
590:
584:
580:
576:
572:
568:
564:
560:
556:
552:
548:
544:
540:
536:
535:
530:
526:
522:
518:
514:
510:
509:
504:
500:
496:
492:
488:
486:0-12-289260-7
482:
478:
474:
470:
466:
462:
458:
454:
450:
446:
445:
440:
436:
435:
429:
427:
423:
412:
410:
406:
402:
398:
394:
393:Mirsky (1971)
390:
386:
382:
372:
370:
366:
362:
358:
354:
349:
345:
341:
337:
333:
329:
325:
321:
317:
313:
303:
301:
300:Golumbic 1980
297:
296:Lovász (1972)
293:
289:
284:
280:
276:
273:if, in every
272:
268:
263:
260:
256:
252:
237:
235:
231:
227:
223:
219:
215:
211:
207:
202:
185:
182:
177:
173:
166:
163:
153:
136:
133:
128:
124:
117:
114:
106:
105:powers of two
102:
99:, ordered by
98:
94:
90:
80:
78:
74:
70:
69:longest paths
66:
62:
58:
54:
50:
46:
42:
38:
34:
30:
29:combinatorics
26:
22:
1349:Order theory
1120:& Orders
1098:Star product
1027:Well-founded
980:Prefix order
936:Distributive
926:Complemented
896:Foundational
861:Completeness
817:Zorn's lemma
806:
721:Cyclic order
704:Key concepts
674:Order theory
611:
605:
570:
538:
532:
529:Mirsky, Leon
512:
506:
476:
448:
442:
426:Schmerl 2002
418:
408:
404:
400:
388:
384:
380:
378:
365:orientations
352:
347:
343:
335:
327:
323:
316:reachability
309:
264:
259:majorization
248:
233:
229:
225:
221:
217:
213:
209:
205:
203:
154:
101:divisibility
96:
86:
32:
25:order theory
18:
1304:Riesz space
1265:Isomorphism
1141:Normal cone
1063:Composition
997:Semilattice
906:Homogeneous
891:Equivalence
741:Total order
286:that every
83:The theorem
21:mathematics
1343:Categories
1272:Order type
1206:Cofinality
1047:Well-order
1022:Transitive
911:Idempotent
844:Asymmetric
432:References
415:Extensions
340:path graph
57:perfection
41:antichains
1323:Upper set
1260:Embedding
1196:Antichain
1017:Tolerance
1007:Symmetric
1002:Semiorder
948:Reflexive
866:Connected
189:⌋
183:
170:⌊
140:⌋
134:
121:⌊
73:colorings
67:relating
63:, to the
1118:Topology
985:Preorder
968:Eulerian
931:Complete
881:Directed
871:Covering
736:Preorder
695:Category
690:Glossary
636:26514679
330:-vertex
1223:Duality
1201:Cofinal
1189:Related
1168:Fréchet
1045:)
921:Bounded
916:Lattice
889:)
887:Partial
755:Results
726:Lattice
628:1922918
597:2920058
555:2316481
495:0562306
465:1969503
271:perfect
47: (
1248:Subnet
1228:Filter
1178:Normed
1163:Banach
1129:&
1036:Better
973:Strict
963:Graded
854:topics
685:Topics
634:
626:
595:
585:
553:
493:
483:
463:
277:, the
1238:Ideal
1216:Graph
1012:Total
990:Total
876:Dense
632:S2CID
607:Order
551:JSTOR
461:JSTOR
326:to a
89:chain
829:list
583:ISBN
481:ISBN
363:and
91:, a
71:and
49:1971
27:and
1243:Net
1043:Pre
616:doi
575:doi
543:doi
517:doi
453:doi
428:).
371:).
359:on
342:to
302:).
294:of
174:log
125:log
59:of
19:In
1345::
630:,
624:MR
622:,
612:19
610:,
593:MR
591:,
581:,
565:;
549:,
539:78
537:,
511:,
491:MR
489:,
459:,
449:51
447:,
401:rs
381:rs
152:.
31:,
1041:(
1038:)
1034:(
885:(
832:)
666:e
659:t
652:v
639:.
618::
600:.
577::
558:.
545::
524:.
519::
513:2
498:.
468:.
455::
409:s
405:r
389:s
385:r
367:(
353:G
348:G
344:G
336:k
328:k
324:G
234:N
230:i
228:(
226:N
222:x
218:x
216:(
214:N
210:x
206:x
186:N
178:2
167:+
164:1
137:N
129:2
118:+
115:1
97:N
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.