557:
states that this bound can always be reached: there always exists an antichain, and a partition of the elements into chains, such that the number of chains equals the number of elements in the antichain, which must therefore also equal the width. Similarly, one can define the
942:
820:
994:
for distributive lattices states that every finite distributive lattice can be represented via join and meet operations on antichains of a finite partial order, or equivalently as union and intersection operations on the
722:
829:
294:
211:
489:
of a partially ordered set is the cardinality of a maximum antichain. Any antichain can intersect any chain in at most one element, so, if we can partition the elements of an order into
735:
345:
989:
455:
962:
646:
592:
547:
527:
507:
432:
412:
389:
365:
316:
251:
231:
164:
144:
124:
654:
1112:
566:
states that in any partial order of finite height, the height equals the smallest number of antichains into which the order may be partitioned.
728:) all lower sets have this form. The union of any two lower sets is another lower set, and the union operation corresponds in this way to a
1227:
Provan, J. Scott; Ball, Michael O. (1983), "The complexity of counting cuts and of computing the probability that a graph is connected",
1972:
620:
Even the empty set has two antichains in its power set: one containing a single set (the empty set itself) and one containing no sets.
613:
434:
in which each pair of different elements is incomparable; that is, there is no order relation between any two different elements in
1955:
1485:
1321:
63:, this also equals the minimum number of chains (totally ordered subsets) into which the set can be partitioned. Dually, the
17:
1802:
991:
82:. For the partially ordered system of all subsets of a finite set, ordered by set inclusion, the antichains are called
1938:
1797:
1792:
256:
173:
1428:
1510:
1829:
1749:
1076:
1614:
1543:
1423:
937:{\displaystyle A\wedge B=\{x\in L_{A}\cap L_{B}:\nexists y\in L_{A}\cap L_{B}{\mbox{ such that }}x<y\}.}
1517:
1505:
1468:
1443:
1418:
1372:
1341:
1814:
1448:
1438:
1314:
1787:
1453:
1229:
1153:
1110:
Kahn, Jeff (2002), "Entropy, independent sets and antichains: a new approach to
Dedekind's problem",
725:
87:
94:
of elements. More generally, counting the number of antichains of a finite partially ordered set is
1719:
1346:
324:
1967:
1950:
1879:
1495:
1007:
A maximum antichain (and its size, the width of a given partially ordered set) can be found in
2005:
1857:
1692:
1683:
1552:
1433:
1387:
1351:
1307:
1037:
554:
462:
60:
54:
43:
1945:
1904:
1894:
1884:
1629:
1592:
1582:
1562:
1547:
1250:
1206:
1135:
965:
550:
79:
8:
1872:
1783:
1729:
1688:
1678:
1567:
1500:
1463:
1198:
815:{\displaystyle A\vee B=\{x\in A\cup B:\nexists y\in A\cup B{\mbox{ such that }}x<y\}.}
563:
68:
971:
437:
1984:
1911:
1764:
1673:
1663:
1604:
1522:
1458:
1210:
1093:
1054:
1032:
947:
631:
577:
532:
512:
492:
417:
397:
374:
350:
301:
236:
216:
149:
129:
109:
1824:
1181:"Recognition algorithms for orders of small width and graphs of small Dilworth number"
1921:
1899:
1759:
1744:
1724:
1527:
1268:
485:
is an antichain that has cardinality at least as large as every other antichain. The
1180:
1734:
1587:
1238:
1214:
1194:
1162:
1148:
1121:
1085:
1046:
458:
1166:
1126:
606:
2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (sequence
553:, there would be 2 of its elements belonging to the same chain, a contradiction).
1916:
1699:
1577:
1572:
1557:
1473:
1382:
1367:
1246:
1202:
1185:
1131:
1012:
1008:
944:
The join and meet operations on all finite antichains of finite subsets of a set
599:
95:
91:
47:
1834:
1819:
1809:
1668:
1646:
1624:
1271:
595:
83:
1999:
1933:
1889:
1867:
1739:
1609:
1597:
1402:
478:
167:
75:
53:
The size of the largest antichain in a partially ordered set is known as its
724:
In a finite partial order (or more generally a partial order satisfying the
74:
The family of all antichains in a finite partially ordered set can be given
1754:
1636:
1619:
1537:
1377:
1330:
213:
If two elements are not comparable, they are called incomparable; that is,
35:
826:
operation on antichains, corresponding to the intersection of lower sets:
1960:
1653:
1532:
1397:
1071:
368:
67:
of the partially ordered set (the length of its longest chain) equals by
31:
1011:. Counting the number of antichains in a given partially ordered set is
71:
the minimum number of antichains into which the set can be partitioned.
1928:
1862:
1703:
1291:
1097:
1058:
717:{\displaystyle L_{A}=\{x:\exists y\in A{\mbox{ such that }}x\leq y\}.}
1979:
1658:
1276:
996:
649:
1242:
1089:
1050:
1774:
1641:
1392:
1286:
1299:
392:
319:
1035:(1950), "A decomposition theorem for partially ordered sets",
598:. The number of different Sperner families is counted by the
562:
of a partial order to be the maximum cardinality of a chain.
608:
1179:
Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy (2003),
574:
An antichain in the inclusion ordering of subsets of an
457:(However, some authors use the term "antichain" to mean
347:
in which each pair of elements is comparable; that is,
1178:
1074:(1971), "A dual of Dilworth's decomposition theorem",
913:
791:
693:
465:
smaller than two distinct elements of the antichain.)
46:
such that any two distinct elements in the subset are
974:
950:
832:
738:
657:
634:
580:
535:
515:
495:
440:
420:
400:
377:
353:
327:
304:
259:
239:
219:
176:
152:
132:
112:
509:chains then the width of the order must be at most
1266:
983:
956:
936:
814:
716:
640:
586:
541:
521:
501:
449:
426:
406:
383:
359:
339:
310:
288:
245:
225:
205:
158:
138:
118:
1997:
1113:Proceedings of the American Mathematical Society
461:, a subset such that there is no element of the
1315:
968:, the free distributive lattice generated by
289:{\displaystyle x\leq y{\text{ nor }}y\leq x.}
928:
845:
806:
751:
708:
671:
206:{\displaystyle a\leq b{\text{ or }}b\leq a.}
1002:
623:
1973:Positive cone of a partially ordered group
1322:
1308:
1226:
1172:
1125:
126:be a partially ordered set. Two elements
1956:Positive cone of an ordered vector space
1147:
1031:
1220:
1141:
1025:
14:
1998:
1070:
166:of a partially ordered set are called
1303:
1267:
1064:
602:, the first few of which numbers are
1109:
1103:
569:
468:
24:
1483:Properties & Types (
1199:10.1023/B:ORDE.0000034609.99940.fb
680:
25:
2017:
1939:Positive cone of an ordered field
1260:
992:Birkhoff's representation theorem
1793:Ordered topological vector space
1329:
529:(if the antichain has more than
78:operations, making them into a
27:Subset of incomparable elements
477:is an antichain that is not a
101:
13:
1:
1750:Series-parallel partial order
1167:10.1215/S0012-7094-37-00334-X
1127:10.1090/S0002-9939-01-06058-0
1077:American Mathematical Monthly
1018:
1429:Cantor's isomorphism theorem
340:{\displaystyle C\subseteq S}
253:are incomparable if neither
7:
1469:Szpilrajn extension theorem
1444:Hausdorff maximal principle
1419:Boolean prime ideal theorem
822:Similarly, we can define a
594:-element set is known as a
10:
2022:
1815:Topological vector lattice
481:of any other antichain. A
1845:
1773:
1712:
1482:
1411:
1360:
1337:
1230:SIAM Journal on Computing
1154:Duke Mathematical Journal
1151:(1937), "Rings of sets",
732:operation on antichains:
726:ascending chain condition
88:free distributive lattice
1424:Cantor–Bernstein theorem
1003:Computational complexity
624:Join and meet operations
1968:Partially ordered group
1788:Specialization preorder
86:and their lattice is a
1454:Kruskal's tree theorem
1449:Knaster–Tarski theorem
1439:Dushnik–Miller theorem
999:of the partial order.
985:
958:
938:
816:
718:
642:
588:
543:
523:
503:
451:
428:
408:
385:
361:
341:
312:
290:
247:
227:
207:
160:
140:
120:
1193:(4): 351–364 (2004),
1038:Annals of Mathematics
986:
959:
939:
915: such that
817:
793: such that
719:
695: such that
643:
589:
544:
524:
504:
452:
429:
409:
386:
362:
342:
313:
291:
248:
228:
208:
161:
141:
121:
44:partially ordered set
18:Width (partial order)
1946:Ordered vector space
972:
966:distributive lattice
948:
830:
736:
655:
632:
578:
551:pigeonhole principle
533:
513:
493:
438:
418:
398:
375:
351:
325:
302:
257:
237:
217:
174:
150:
130:
110:
80:distributive lattice
1784:Alexandrov topology
1730:Lexicographic order
1689:Well-quasi-ordering
1033:Dilworth, Robert P.
1765:Transitive closure
1725:Converse/Transpose
1434:Dilworth's theorem
1269:Weisstein, Eric W.
984:{\displaystyle X.}
981:
954:
934:
917:
812:
795:
714:
697:
638:
584:
555:Dilworth's theorem
539:
519:
499:
450:{\displaystyle A.}
447:
424:
404:
381:
371:. An antichain in
357:
337:
308:
286:
243:
223:
203:
156:
136:
116:
61:Dilworth's theorem
1993:
1992:
1951:Partially ordered
1760:Symmetric closure
1745:Reflexive closure
1488:
1149:Birkhoff, Garrett
957:{\displaystyle X}
916:
794:
696:
648:corresponds to a
641:{\displaystyle A}
587:{\displaystyle n}
549:elements, by the
542:{\displaystyle k}
522:{\displaystyle k}
502:{\displaystyle k}
483:maximum antichain
475:maximal antichain
427:{\displaystyle S}
407:{\displaystyle A}
384:{\displaystyle S}
360:{\displaystyle C}
311:{\displaystyle S}
272:
246:{\displaystyle y}
226:{\displaystyle x}
189:
159:{\displaystyle b}
139:{\displaystyle a}
119:{\displaystyle S}
42:is a subset of a
34:, in the area of
16:(Redirected from
2013:
1735:Linear extension
1484:
1464:Mirsky's theorem
1324:
1317:
1310:
1301:
1300:
1296:
1282:
1281:
1254:
1253:
1224:
1218:
1217:
1176:
1170:
1169:
1145:
1139:
1138:
1129:
1107:
1101:
1100:
1068:
1062:
1061:
1029:
990:
988:
987:
982:
963:
961:
960:
955:
943:
941:
940:
935:
918:
914:
911:
910:
898:
897:
876:
875:
863:
862:
821:
819:
818:
813:
796:
792:
723:
721:
720:
715:
698:
694:
667:
666:
647:
645:
644:
639:
611:
600:Dedekind numbers
593:
591:
590:
585:
570:Sperner families
564:Mirsky's theorem
548:
546:
545:
540:
528:
526:
525:
520:
508:
506:
505:
500:
469:Height and width
459:strong antichain
456:
454:
453:
448:
433:
431:
430:
425:
413:
411:
410:
405:
390:
388:
387:
382:
366:
364:
363:
358:
346:
344:
343:
338:
317:
315:
314:
309:
295:
293:
292:
287:
273:
270:
252:
250:
249:
244:
232:
230:
229:
224:
212:
210:
209:
204:
190:
187:
165:
163:
162:
157:
145:
143:
142:
137:
125:
123:
122:
117:
84:Sperner families
69:Mirsky's theorem
21:
2021:
2020:
2016:
2015:
2014:
2012:
2011:
2010:
1996:
1995:
1994:
1989:
1985:Young's lattice
1841:
1769:
1708:
1558:Heyting algebra
1506:Boolean algebra
1478:
1459:Laver's theorem
1407:
1373:Boolean algebra
1368:Binary relation
1356:
1333:
1328:
1285:
1263:
1258:
1257:
1243:10.1137/0212053
1225:
1221:
1177:
1173:
1146:
1142:
1108:
1104:
1090:10.2307/2316481
1069:
1065:
1051:10.2307/1969503
1030:
1026:
1021:
1009:polynomial time
1005:
973:
970:
969:
949:
946:
945:
912:
906:
902:
893:
889:
871:
867:
858:
854:
831:
828:
827:
790:
737:
734:
733:
692:
662:
658:
656:
653:
652:
633:
630:
629:
626:
607:
579:
576:
575:
572:
534:
531:
530:
514:
511:
510:
494:
491:
490:
471:
439:
436:
435:
419:
416:
415:
399:
396:
395:
376:
373:
372:
369:totally ordered
352:
349:
348:
326:
323:
322:
303:
300:
299:
271: nor
269:
258:
255:
254:
238:
235:
234:
218:
215:
214:
186:
175:
172:
171:
151:
148:
147:
131:
128:
127:
111:
108:
107:
104:
92:Dedekind number
28:
23:
22:
15:
12:
11:
5:
2019:
2009:
2008:
1991:
1990:
1988:
1987:
1982:
1977:
1976:
1975:
1965:
1964:
1963:
1958:
1953:
1943:
1942:
1941:
1931:
1926:
1925:
1924:
1919:
1912:Order morphism
1909:
1908:
1907:
1897:
1892:
1887:
1882:
1877:
1876:
1875:
1865:
1860:
1855:
1849:
1847:
1843:
1842:
1840:
1839:
1838:
1837:
1832:
1830:Locally convex
1827:
1822:
1812:
1810:Order topology
1807:
1806:
1805:
1803:Order topology
1800:
1790:
1780:
1778:
1771:
1770:
1768:
1767:
1762:
1757:
1752:
1747:
1742:
1737:
1732:
1727:
1722:
1716:
1714:
1710:
1709:
1707:
1706:
1696:
1686:
1681:
1676:
1671:
1666:
1661:
1656:
1651:
1650:
1649:
1639:
1634:
1633:
1632:
1627:
1622:
1617:
1615:Chain-complete
1607:
1602:
1601:
1600:
1595:
1590:
1585:
1580:
1570:
1565:
1560:
1555:
1550:
1540:
1535:
1530:
1525:
1520:
1515:
1514:
1513:
1503:
1498:
1492:
1490:
1480:
1479:
1477:
1476:
1471:
1466:
1461:
1456:
1451:
1446:
1441:
1436:
1431:
1426:
1421:
1415:
1413:
1409:
1408:
1406:
1405:
1400:
1395:
1390:
1385:
1380:
1375:
1370:
1364:
1362:
1358:
1357:
1355:
1354:
1349:
1344:
1338:
1335:
1334:
1327:
1326:
1319:
1312:
1304:
1298:
1297:
1283:
1262:
1261:External links
1259:
1256:
1255:
1237:(4): 777–788,
1219:
1171:
1161:(3): 443–454,
1140:
1120:(2): 371–378,
1102:
1084:(8): 876–877,
1063:
1045:(1): 161–166,
1023:
1022:
1020:
1017:
1004:
1001:
980:
977:
953:
933:
930:
927:
924:
921:
909:
905:
901:
896:
892:
888:
885:
882:
879:
874:
870:
866:
861:
857:
853:
850:
847:
844:
841:
838:
835:
811:
808:
805:
802:
799:
789:
786:
783:
780:
777:
774:
771:
768:
765:
762:
759:
756:
753:
750:
747:
744:
741:
713:
710:
707:
704:
701:
691:
688:
685:
682:
679:
676:
673:
670:
665:
661:
637:
628:Any antichain
625:
622:
618:
617:
596:Sperner family
583:
571:
568:
561:
538:
518:
498:
488:
470:
467:
446:
443:
423:
403:
380:
356:
336:
333:
330:
307:
285:
282:
279:
276:
268:
265:
262:
242:
222:
202:
199:
196:
193:
188: or
185:
182:
179:
155:
135:
115:
103:
100:
26:
9:
6:
4:
3:
2:
2018:
2007:
2004:
2003:
2001:
1986:
1983:
1981:
1978:
1974:
1971:
1970:
1969:
1966:
1962:
1959:
1957:
1954:
1952:
1949:
1948:
1947:
1944:
1940:
1937:
1936:
1935:
1934:Ordered field
1932:
1930:
1927:
1923:
1920:
1918:
1915:
1914:
1913:
1910:
1906:
1903:
1902:
1901:
1898:
1896:
1893:
1891:
1890:Hasse diagram
1888:
1886:
1883:
1881:
1878:
1874:
1871:
1870:
1869:
1868:Comparability
1866:
1864:
1861:
1859:
1856:
1854:
1851:
1850:
1848:
1844:
1836:
1833:
1831:
1828:
1826:
1823:
1821:
1818:
1817:
1816:
1813:
1811:
1808:
1804:
1801:
1799:
1796:
1795:
1794:
1791:
1789:
1785:
1782:
1781:
1779:
1776:
1772:
1766:
1763:
1761:
1758:
1756:
1753:
1751:
1748:
1746:
1743:
1741:
1740:Product order
1738:
1736:
1733:
1731:
1728:
1726:
1723:
1721:
1718:
1717:
1715:
1713:Constructions
1711:
1705:
1701:
1697:
1694:
1690:
1687:
1685:
1682:
1680:
1677:
1675:
1672:
1670:
1667:
1665:
1662:
1660:
1657:
1655:
1652:
1648:
1645:
1644:
1643:
1640:
1638:
1635:
1631:
1628:
1626:
1623:
1621:
1618:
1616:
1613:
1612:
1611:
1610:Partial order
1608:
1606:
1603:
1599:
1598:Join and meet
1596:
1594:
1591:
1589:
1586:
1584:
1581:
1579:
1576:
1575:
1574:
1571:
1569:
1566:
1564:
1561:
1559:
1556:
1554:
1551:
1549:
1545:
1541:
1539:
1536:
1534:
1531:
1529:
1526:
1524:
1521:
1519:
1516:
1512:
1509:
1508:
1507:
1504:
1502:
1499:
1497:
1496:Antisymmetric
1494:
1493:
1491:
1487:
1481:
1475:
1472:
1470:
1467:
1465:
1462:
1460:
1457:
1455:
1452:
1450:
1447:
1445:
1442:
1440:
1437:
1435:
1432:
1430:
1427:
1425:
1422:
1420:
1417:
1416:
1414:
1410:
1404:
1403:Weak ordering
1401:
1399:
1396:
1394:
1391:
1389:
1388:Partial order
1386:
1384:
1381:
1379:
1376:
1374:
1371:
1369:
1366:
1365:
1363:
1359:
1353:
1350:
1348:
1345:
1343:
1340:
1339:
1336:
1332:
1325:
1320:
1318:
1313:
1311:
1306:
1305:
1302:
1294:
1293:
1288:
1284:
1279:
1278:
1273:
1270:
1265:
1264:
1252:
1248:
1244:
1240:
1236:
1232:
1231:
1223:
1216:
1212:
1208:
1204:
1200:
1196:
1192:
1188:
1187:
1182:
1175:
1168:
1164:
1160:
1156:
1155:
1150:
1144:
1137:
1133:
1128:
1123:
1119:
1115:
1114:
1106:
1099:
1095:
1091:
1087:
1083:
1079:
1078:
1073:
1067:
1060:
1056:
1052:
1048:
1044:
1040:
1039:
1034:
1028:
1024:
1016:
1014:
1010:
1000:
998:
993:
978:
975:
967:
951:
931:
925:
922:
919:
907:
903:
899:
894:
890:
886:
883:
880:
877:
872:
868:
864:
859:
855:
851:
848:
842:
839:
836:
833:
825:
809:
803:
800:
797:
787:
784:
781:
778:
775:
772:
769:
766:
763:
760:
757:
754:
748:
745:
742:
739:
731:
727:
711:
705:
702:
699:
689:
686:
683:
677:
674:
668:
663:
659:
651:
635:
621:
615:
610:
605:
604:
603:
601:
597:
581:
567:
565:
559:
556:
552:
536:
516:
496:
486:
484:
480:
479:proper subset
476:
466:
464:
460:
444:
441:
421:
401:
394:
378:
370:
354:
334:
331:
328:
321:
305:
296:
283:
280:
277:
274:
266:
263:
260:
240:
220:
200:
197:
194:
191:
183:
180:
177:
169:
153:
133:
113:
99:
97:
93:
89:
85:
81:
77:
76:join and meet
72:
70:
66:
62:
58:
57:
51:
49:
45:
41:
37:
33:
19:
2006:Order theory
1852:
1777:& Orders
1755:Star product
1684:Well-founded
1637:Prefix order
1593:Distributive
1583:Complemented
1553:Foundational
1518:Completeness
1474:Zorn's lemma
1378:Cyclic order
1361:Key concepts
1331:Order theory
1290:
1275:
1234:
1228:
1222:
1190:
1184:
1174:
1158:
1152:
1143:
1117:
1111:
1105:
1081:
1075:
1072:Mirsky, Leon
1066:
1042:
1036:
1027:
1006:
823:
729:
627:
619:
573:
482:
474:
472:
297:
105:
73:
64:
55:
52:
48:incomparable
39:
36:order theory
29:
1961:Riesz space
1922:Isomorphism
1798:Normal cone
1720:Composition
1654:Semilattice
1563:Homogeneous
1548:Equivalence
1398:Total order
1287:"Antichain"
1272:"Antichain"
1013:#P-complete
298:A chain in
102:Definitions
96:#P-complete
32:mathematics
1929:Order type
1863:Cofinality
1704:Well-order
1679:Transitive
1568:Idempotent
1501:Asymmetric
1292:PlanetMath
1019:References
997:lower sets
168:comparable
1980:Upper set
1917:Embedding
1853:Antichain
1674:Tolerance
1664:Symmetric
1659:Semiorder
1605:Reflexive
1523:Connected
1277:MathWorld
964:define a
900:∩
887:∈
881:∄
865:∩
852:∈
837:∧
785:∪
779:∈
773:∄
764:∪
758:∈
743:∨
703:≤
687:∈
681:∃
650:lower set
332:⊆
278:≤
264:≤
195:≤
181:≤
90:, with a
40:antichain
2000:Category
1775:Topology
1642:Preorder
1625:Eulerian
1588:Complete
1538:Directed
1528:Covering
1393:Preorder
1352:Category
1347:Glossary
1880:Duality
1858:Cofinal
1846:Related
1825:Fréchet
1702:)
1578:Bounded
1573:Lattice
1546:)
1544:Partial
1412:Results
1383:Lattice
1251:0721012
1215:1363140
1207:2079151
1136:1862115
1098:2316481
1059:1969503
612:in the
609:A000372
1905:Subnet
1885:Filter
1835:Normed
1820:Banach
1786:&
1693:Better
1630:Strict
1620:Graded
1511:topics
1342:Topics
1249:
1213:
1205:
1134:
1096:
1057:
560:height
393:subset
320:subset
65:height
1895:Ideal
1873:Graph
1669:Total
1647:Total
1533:Dense
1211:S2CID
1186:Order
1094:JSTOR
1055:JSTOR
487:width
463:poset
391:is a
318:is a
59:. By
56:width
38:, an
1486:list
923:<
824:meet
801:<
730:join
614:OEIS
233:and
146:and
106:Let
1900:Net
1700:Pre
1239:doi
1195:doi
1163:doi
1122:doi
1118:130
1086:doi
1047:doi
414:of
367:is
170:if
30:In
2002::
1289:.
1274:.
1247:MR
1245:,
1235:12
1233:,
1209:,
1203:MR
1201:,
1191:20
1189:,
1183:,
1157:,
1132:MR
1130:,
1116:,
1092:,
1082:78
1080:,
1053:,
1043:51
1041:,
1015:.
616:).
473:A
98:.
50:.
1698:(
1695:)
1691:(
1542:(
1489:)
1323:e
1316:t
1309:v
1295:.
1280:.
1241::
1197::
1165::
1159:3
1124::
1088::
1049::
979:.
976:X
952:X
932:.
929:}
926:y
920:x
908:B
904:L
895:A
891:L
884:y
878::
873:B
869:L
860:A
856:L
849:x
846:{
843:=
840:B
834:A
810:.
807:}
804:y
798:x
788:B
782:A
776:y
770::
767:B
761:A
755:x
752:{
749:=
746:B
740:A
712:.
709:}
706:y
700:x
690:A
684:y
678::
675:x
672:{
669:=
664:A
660:L
636:A
582:n
537:k
517:k
497:k
445:.
442:A
422:S
402:A
379:S
355:C
335:S
329:C
306:S
284:.
281:x
275:y
267:y
261:x
241:y
221:x
201:.
198:a
192:b
184:b
178:a
154:b
134:a
114:S
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.