17:
53:
1510:
920:
297:
1395:
1292:
1008:
645:
443:
343:
1041:
383:
851:
214:
715:
966:
590:
564:
538:
512:
1540:
1327:
1224:
1081:
486:
86:
1569:
1140:
1589:
1160:
940:
874:
798:
774:
680:
403:
238:
1189:
1107:
800:. For interval orders, dimension can be arbitrarily large. And while the problem of determining the dimension of general partial orders is known to be
815:, which is defined analogously, but in terms of interval orders instead of linear orders. Thus, the interval dimension of a partially ordered set
1409:
1598:
746:
1762:
595:
The subclass of interval orders obtained by restricting the intervals to those of unit length, so they all have the form
1796:
879:
243:
1605:
1, 2, 5, 15, 53, 217, 1014, 5335, 31240, 201608, 1422074, 10886503, 89903100, 796713190, 7541889195, 75955177642, …
1691:
1332:
1229:
971:
598:
1401:
1142:. These are the involutions with no so-called left- or right-neighbor nestings where, for any involution
16:
408:
1682:
302:
1110:
1013:
348:
1113:
805:
818:
181:
1894:
688:
1889:
945:
1828:(2001), "Vassiliev invariants and a strange identity related to the Dedekind eta-function",
1754:
569:
543:
517:
491:
1853:
1817:
1783:
1722:
1518:
1297:
1194:
1054:
720:
Interval orders should not be confused with the interval-containment orders, which are the
459:
59:
1545:
8:
659:
1739:
1122:
1830:
1726:
1700:
1574:
1145:
925:
859:
783:
759:
665:
388:
223:
1844:
1165:
1086:
1868:
1809:
1791:
449:
1839:
1805:
1771:
1730:
1710:
655:
1849:
1813:
1779:
1718:
1689:(2010), "(2+2) free posets, ascent sequences and pattern avoiding permutations",
1043:. The interval dimension of an order is never greater than its order dimension.
753:
725:
721:
488:-free posets . Fully written out, this means that for any two pairs of elements
453:
448:
Such posets may be equivalently characterized as those with no induced subposet
1714:
743:
What is the complexity of determining the order dimension of an interval order?
683:
52:
1775:
804:, determining the dimension of an interval order remains a problem of unknown
1883:
1686:
173:
141:
45:
777:
133:
1794:(1970), "Intransitive indifference with unequal indifference intervals",
1117:
129:
1825:
735:
144:
corresponding to their left-to-right precedence relation—one interval,
1873:
Interval Orders and
Interval Graphs: A Study of Partially Ordered Sets
648:
217:
88:
poset (black Hasse diagram) cannot be part of an interval order: if
1705:
1505:{\displaystyle F(t)=\sum _{n\geq 0}\prod _{i=1}^{n}(1-(1-t)^{i}).}
1681:
1656:
854:
801:
48:(left) and a collection of intervals that represents it (right).
1638:
176:
1755:"On the interplay between interval dimension and dimension"
1593:
724:
on intervals on the real line (equivalently, the orders of
1741:
Interval Orders: Combinatorial
Structure and Algorithms
1571:
gives the number of unlabeled interval orders of size
140:
for a collection of intervals on the real line is the
1577:
1548:
1521:
1412:
1335:
1300:
1232:
1197:
1168:
1148:
1125:
1089:
1057:
1016:
974:
948:
928:
882:
862:
821:
786:
762:
691:
668:
601:
572:
546:
520:
494:
462:
411:
391:
351:
305:
246:
226:
184:
62:
1752:
1747:, Ph.D. dissertation, Technische Universität Berlin
1644:
216:is an interval order if and only if there exists a
1583:
1563:
1534:
1504:
1389:
1321:
1286:
1218:
1183:
1154:
1134:
1101:
1075:
1035:
1002:
960:
934:
914:
868:
845:
792:
768:
709:
674:
639:
584:
558:
532:
506:
480:
437:
397:
377:
337:
291:
232:
208:
80:
1400:Such involutions, according to semi-length, have
915:{\displaystyle \preceq _{1},\ldots ,\preceq _{k}}
1881:
731:
1753:Felsner, S.; Habib, M.; Möhring, R. H. (1994),
737:
292:{\displaystyle x_{i}\mapsto (\ell _{i},r_{i})}
752:An important parameter of partial orders is
1083:-free posets, unlabeled interval orders on
1591:. The sequence of these numbers (sequence
1390:{\displaystyle f(i)<f(i+1)<i<i+1}
1287:{\displaystyle i<i+1<f(i+1)<f(i)}
1843:
1704:
1867:
1790:
1621:
51:
15:
1737:
1632:
1109:are also in bijection with a subset of
1003:{\displaystyle x\preceq _{1}y,\ldots ,}
747:(more unsolved problems in mathematics)
640:{\displaystyle (\ell _{i},\ell _{i}+1)}
1882:
1824:
1667:
876:for which there exist interval orders
151:, being considered less than another,
1763:SIAM Journal on Discrete Mathematics
1645:Felsner, Habib & Möhring (1994)
1051:In addition to being isomorphic to
756:: the dimension of a partial order
13:
1861:
1797:Journal of Mathematical Psychology
438:{\displaystyle r_{i}<\ell _{j}}
14:
1906:
1685:; Claesson, Anders; Dukes, Mark;
1046:
338:{\displaystyle x_{i},x_{j}\in X}
1692:Journal of Combinatorial Theory
738:Unsolved problem in mathematics
240:to a set of real intervals, so
1661:
1650:
1626:
1615:
1558:
1552:
1496:
1487:
1474:
1465:
1422:
1416:
1366:
1354:
1345:
1339:
1316:
1307:
1281:
1275:
1266:
1254:
1213:
1204:
1178:
1169:
1096:
1090:
1070:
1058:
1036:{\displaystyle x\preceq _{k}y}
840:
828:
704:
692:
634:
602:
475:
463:
378:{\displaystyle x_{i}<x_{j}}
286:
260:
257:
203:
191:
75:
63:
1:
1845:10.1016/s0040-9383(00)00005-7
1675:
732:Interval orders and dimension
165:is completely to the left of
1810:10.1016/0022-2496(70)90062-3
1657:Bousquet-MĂ©lou et al. (2010)
1402:ordinary generating function
120:must be completely right of
20:A partial order on the set {
7:
846:{\displaystyle P=(X,\leq )}
452:to the pair of two-element
209:{\displaystyle P=(X,\leq )}
10:
1911:
1715:10.1016/j.jcta.2009.12.007
1294:and a right nesting is an
1776:10.1137/S089548019121885X
710:{\displaystyle (X,\cap )}
1683:Bousquet-MĂ©lou, Mireille
1609:
806:computational complexity
456:, in other words as the
1191:, a left nesting is an
961:{\displaystyle x\leq y}
811:A related parameter is
776:is the least number of
112:is completely right of
92:is completely right of
1585:
1565:
1536:
1506:
1464:
1391:
1323:
1288:
1220:
1185:
1156:
1136:
1103:
1077:
1037:
1004:
962:
936:
916:
870:
847:
794:
780:whose intersection is
770:
711:
676:
662:of an interval order (
641:
586:
585:{\displaystyle c>b}
560:
559:{\displaystyle a>d}
534:
533:{\displaystyle c>d}
508:
507:{\displaystyle a>b}
482:
439:
399:
379:
339:
293:
234:
210:
125:
82:
49:
1586:
1566:
1537:
1535:{\displaystyle t^{n}}
1507:
1444:
1392:
1324:
1322:{\displaystyle i\in }
1289:
1221:
1219:{\displaystyle i\in }
1186:
1157:
1137:
1116:on ordered sets with
1104:
1078:
1076:{\displaystyle (2+2)}
1038:
1005:
963:
937:
917:
871:
848:
795:
771:
712:
677:
642:
587:
561:
535:
509:
483:
481:{\displaystyle (2+2)}
440:
400:
380:
340:
294:
235:
211:
83:
81:{\displaystyle (2+2)}
55:
44:} illustrated by its
19:
1738:Felsner, S. (1992),
1575:
1564:{\displaystyle F(t)}
1546:
1542:in the expansion of
1519:
1410:
1333:
1298:
1230:
1195:
1166:
1146:
1123:
1087:
1055:
1014:
972:
946:
926:
880:
860:
819:
784:
760:
689:
666:
599:
570:
544:
518:
492:
460:
409:
389:
349:
303:
299:, such that for any
244:
224:
182:
60:
1515:The coefficient of
660:comparability graph
647:, is precisely the
172:. More formally, a
100:overlaps with both
1792:Fishburn, Peter C.
1581:
1561:
1532:
1502:
1443:
1387:
1319:
1284:
1216:
1181:
1152:
1135:{\displaystyle 2n}
1132:
1099:
1073:
1033:
1000:
958:
932:
912:
866:
843:
813:interval dimension
790:
766:
707:
672:
637:
582:
556:
530:
504:
478:
435:
395:
375:
335:
289:
230:
206:
126:
124:(light gray edge).
78:
50:
1584:{\displaystyle n}
1428:
1155:{\displaystyle f}
935:{\displaystyle X}
869:{\displaystyle k}
793:{\displaystyle P}
769:{\displaystyle P}
675:{\displaystyle X}
398:{\displaystyle P}
233:{\displaystyle X}
1902:
1876:
1856:
1847:
1820:
1786:
1759:
1748:
1746:
1733:
1708:
1670:
1665:
1659:
1654:
1648:
1642:
1636:
1630:
1624:
1619:
1596:
1590:
1588:
1587:
1582:
1570:
1568:
1567:
1562:
1541:
1539:
1538:
1533:
1531:
1530:
1511:
1509:
1508:
1503:
1495:
1494:
1463:
1458:
1442:
1396:
1394:
1393:
1388:
1328:
1326:
1325:
1320:
1293:
1291:
1290:
1285:
1225:
1223:
1222:
1217:
1190:
1188:
1187:
1184:{\displaystyle }
1182:
1161:
1159:
1158:
1153:
1141:
1139:
1138:
1133:
1111:fixed-point-free
1108:
1106:
1105:
1102:{\displaystyle }
1100:
1082:
1080:
1079:
1074:
1042:
1040:
1039:
1034:
1029:
1028:
1009:
1007:
1006:
1001:
987:
986:
967:
965:
964:
959:
941:
939:
938:
933:
921:
919:
918:
913:
911:
910:
892:
891:
875:
873:
872:
867:
852:
850:
849:
844:
799:
797:
796:
791:
775:
773:
772:
767:
739:
722:inclusion orders
716:
714:
713:
708:
681:
679:
678:
673:
646:
644:
643:
638:
627:
626:
614:
613:
591:
589:
588:
583:
565:
563:
562:
557:
539:
537:
536:
531:
513:
511:
510:
505:
487:
485:
484:
479:
444:
442:
441:
436:
434:
433:
421:
420:
404:
402:
401:
396:
384:
382:
381:
376:
374:
373:
361:
360:
344:
342:
341:
336:
328:
327:
315:
314:
298:
296:
295:
290:
285:
284:
272:
271:
256:
255:
239:
237:
236:
231:
215:
213:
212:
207:
87:
85:
84:
79:
1910:
1909:
1905:
1904:
1903:
1901:
1900:
1899:
1880:
1879:
1869:Fishburn, Peter
1864:
1862:Further reading
1757:
1744:
1678:
1673:
1666:
1662:
1655:
1651:
1643:
1639:
1631:
1627:
1622:Fishburn (1970)
1620:
1616:
1612:
1592:
1576:
1573:
1572:
1547:
1544:
1543:
1526:
1522:
1520:
1517:
1516:
1490:
1486:
1459:
1448:
1432:
1411:
1408:
1407:
1334:
1331:
1330:
1299:
1296:
1295:
1231:
1228:
1227:
1196:
1193:
1192:
1167:
1164:
1163:
1147:
1144:
1143:
1124:
1121:
1120:
1088:
1085:
1084:
1056:
1053:
1052:
1049:
1024:
1020:
1015:
1012:
1011:
982:
978:
973:
970:
969:
947:
944:
943:
927:
924:
923:
906:
902:
887:
883:
881:
878:
877:
861:
858:
857:
820:
817:
816:
785:
782:
781:
761:
758:
757:
754:order dimension
750:
749:
744:
741:
734:
690:
687:
686:
667:
664:
663:
622:
618:
609:
605:
600:
597:
596:
571:
568:
567:
545:
542:
541:
519:
516:
515:
493:
490:
489:
461:
458:
457:
429:
425:
416:
412:
410:
407:
406:
390:
387:
386:
369:
365:
356:
352:
350:
347:
346:
323:
319:
310:
306:
304:
301:
300:
280:
276:
267:
263:
251:
247:
245:
242:
241:
225:
222:
221:
183:
180:
179:
171:
164:
157:
150:
61:
58:
57:
12:
11:
5:
1908:
1898:
1897:
1892:
1878:
1877:
1863:
1860:
1859:
1858:
1838:(5): 945–960,
1822:
1804:(1): 144–149,
1788:
1750:
1735:
1699:(7): 884–909,
1687:Kitaev, Sergey
1677:
1674:
1672:
1671:
1660:
1649:
1637:
1625:
1613:
1611:
1608:
1607:
1606:
1580:
1560:
1557:
1554:
1551:
1529:
1525:
1513:
1512:
1501:
1498:
1493:
1489:
1485:
1482:
1479:
1476:
1473:
1470:
1467:
1462:
1457:
1454:
1451:
1447:
1441:
1438:
1435:
1431:
1427:
1424:
1421:
1418:
1415:
1386:
1383:
1380:
1377:
1374:
1371:
1368:
1365:
1362:
1359:
1356:
1353:
1350:
1347:
1344:
1341:
1338:
1318:
1315:
1312:
1309:
1306:
1303:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1244:
1241:
1238:
1235:
1215:
1212:
1209:
1206:
1203:
1200:
1180:
1177:
1174:
1171:
1151:
1131:
1128:
1098:
1095:
1092:
1072:
1069:
1066:
1063:
1060:
1048:
1045:
1032:
1027:
1023:
1019:
999:
996:
993:
990:
985:
981:
977:
957:
954:
951:
931:
909:
905:
901:
898:
895:
890:
886:
865:
842:
839:
836:
833:
830:
827:
824:
789:
765:
745:
742:
736:
733:
730:
706:
703:
700:
697:
694:
684:interval graph
671:
636:
633:
630:
625:
621:
617:
612:
608:
604:
581:
578:
575:
555:
552:
549:
540:one must have
529:
526:
523:
503:
500:
497:
477:
474:
471:
468:
465:
432:
428:
424:
419:
415:
394:
372:
368:
364:
359:
355:
334:
331:
326:
322:
318:
313:
309:
288:
283:
279:
275:
270:
266:
262:
259:
254:
250:
229:
205:
202:
199:
196:
193:
190:
187:
169:
162:
155:
148:
138:interval order
77:
74:
71:
68:
65:
9:
6:
4:
3:
2:
1907:
1896:
1895:Combinatorics
1893:
1891:
1888:
1887:
1885:
1874:
1870:
1866:
1865:
1855:
1851:
1846:
1841:
1837:
1833:
1832:
1827:
1823:
1819:
1815:
1811:
1807:
1803:
1799:
1798:
1793:
1789:
1785:
1781:
1777:
1773:
1769:
1765:
1764:
1756:
1751:
1743:
1742:
1736:
1732:
1728:
1724:
1720:
1716:
1712:
1707:
1702:
1698:
1694:
1693:
1688:
1684:
1680:
1679:
1669:
1668:Zagier (2001)
1664:
1658:
1653:
1646:
1641:
1635:, p. 47)
1634:
1633:Felsner (1992
1629:
1623:
1618:
1614:
1604:
1603:
1602:
1600:
1595:
1578:
1555:
1549:
1527:
1523:
1499:
1491:
1483:
1480:
1477:
1471:
1468:
1460:
1455:
1452:
1449:
1445:
1439:
1436:
1433:
1429:
1425:
1419:
1413:
1406:
1405:
1404:
1403:
1398:
1384:
1381:
1378:
1375:
1372:
1369:
1363:
1360:
1357:
1351:
1348:
1342:
1336:
1313:
1310:
1304:
1301:
1278:
1272:
1269:
1263:
1260:
1257:
1251:
1248:
1245:
1242:
1239:
1236:
1233:
1210:
1207:
1201:
1198:
1175:
1172:
1149:
1129:
1126:
1119:
1115:
1112:
1093:
1067:
1064:
1061:
1047:Combinatorics
1044:
1030:
1025:
1021:
1017:
997:
994:
991:
988:
983:
979:
975:
968:exactly when
955:
952:
949:
929:
907:
903:
899:
896:
893:
888:
884:
863:
856:
853:is the least
837:
834:
831:
825:
822:
814:
809:
807:
803:
787:
779:
778:linear orders
763:
755:
748:
729:
727:
723:
718:
701:
698:
695:
685:
669:
661:
657:
652:
650:
631:
628:
623:
619:
615:
610:
606:
593:
579:
576:
573:
553:
550:
547:
527:
524:
521:
501:
498:
495:
472:
469:
466:
455:
451:
446:
430:
426:
422:
417:
413:
405:exactly when
392:
370:
366:
362:
357:
353:
332:
329:
324:
320:
316:
311:
307:
281:
277:
273:
268:
264:
252:
248:
227:
219:
200:
197:
194:
188:
185:
178:
175:
168:
161:
154:
147:
143:
142:partial order
139:
135:
132:, especially
131:
123:
119:
115:
111:
107:
103:
99:
95:
91:
72:
69:
66:
54:
47:
46:Hasse diagram
43:
39:
35:
31:
27:
23:
18:
1890:Order theory
1875:, John Wiley
1872:
1835:
1829:
1801:
1795:
1770:(1): 32–40,
1767:
1761:
1740:
1696:
1695:, Series A,
1690:
1663:
1652:
1640:
1628:
1617:
1514:
1399:
1050:
812:
810:
751:
719:
682:, ≤) is the
653:
594:
447:
166:
159:
152:
145:
137:
134:order theory
127:
121:
117:
113:
109:
105:
101:
97:
93:
89:
41:
37:
33:
29:
25:
21:
1826:Zagier, Don
1118:cardinality
1114:involutions
130:mathematics
1884:Categories
1676:References
1329:such that
1226:such that
656:complement
649:semiorders
450:isomorphic
1706:0806.0666
1601:) begins
1481:−
1472:−
1446:∏
1437:≥
1430:∑
1305:∈
1202:∈
1022:⪯
995:…
980:⪯
953:≤
904:⪯
897:…
885:⪯
838:≤
726:dimension
702:∩
620:ℓ
607:ℓ
427:ℓ
330:∈
265:ℓ
258:↦
218:bijection
201:≤
174:countable
1871:(1985),
1831:Topology
345:we have
1854:1860536
1818:0253942
1784:1259007
1731:8677150
1723:2652101
1597:in the
1594:A022493
855:integer
802:NP-hard
658:of the
116:, then
1852:
1816:
1782:
1729:
1721:
728:≤ 2).
454:chains
136:, the
108:, and
96:, and
1758:(PDF)
1745:(PDF)
1727:S2CID
1701:arXiv
1610:Notes
942:with
220:from
177:poset
158:, if
1599:OEIS
1376:<
1370:<
1349:<
1270:<
1249:<
1237:<
1010:and
654:The
577:>
551:>
525:>
514:and
499:>
423:<
363:<
104:and
56:The
1840:doi
1806:doi
1772:doi
1711:doi
1697:117
1162:on
922:on
566:or
385:in
128:In
1886::
1850:MR
1848:,
1836:40
1834:,
1814:MR
1812:,
1800:,
1780:MR
1778:,
1766:,
1760:,
1725:,
1719:MR
1717:,
1709:,
1397:.
808:.
717:.
651:.
592:.
445:.
40:,
36:,
32:,
28:,
24:,
1857:.
1842::
1821:.
1808::
1802:7
1787:.
1774::
1768:7
1749:.
1734:.
1713::
1703::
1647:.
1579:n
1559:)
1556:t
1553:(
1550:F
1528:n
1524:t
1500:.
1497:)
1492:i
1488:)
1484:t
1478:1
1475:(
1469:1
1466:(
1461:n
1456:1
1453:=
1450:i
1440:0
1434:n
1426:=
1423:)
1420:t
1417:(
1414:F
1385:1
1382:+
1379:i
1373:i
1367:)
1364:1
1361:+
1358:i
1355:(
1352:f
1346:)
1343:i
1340:(
1337:f
1317:]
1314:n
1311:2
1308:[
1302:i
1282:)
1279:i
1276:(
1273:f
1267:)
1264:1
1261:+
1258:i
1255:(
1252:f
1246:1
1243:+
1240:i
1234:i
1214:]
1211:n
1208:2
1205:[
1199:i
1179:]
1176:n
1173:2
1170:[
1150:f
1130:n
1127:2
1097:]
1094:n
1091:[
1071:)
1068:2
1065:+
1062:2
1059:(
1031:y
1026:k
1018:x
998:,
992:,
989:y
984:1
976:x
956:y
950:x
930:X
908:k
900:,
894:,
889:1
864:k
841:)
835:,
832:X
829:(
826:=
823:P
788:P
764:P
740::
705:)
699:,
696:X
693:(
670:X
635:)
632:1
629:+
624:i
616:,
611:i
603:(
580:b
574:c
554:d
548:a
528:d
522:c
502:b
496:a
476:)
473:2
470:+
467:2
464:(
431:j
418:i
414:r
393:P
371:j
367:x
358:i
354:x
333:X
325:j
321:x
317:,
312:i
308:x
287:)
282:i
278:r
274:,
269:i
261:(
253:i
249:x
228:X
204:)
198:,
195:X
192:(
189:=
186:P
170:2
167:I
163:1
160:I
156:2
153:I
149:1
146:I
122:b
118:c
114:d
110:c
106:b
102:a
98:d
94:b
90:a
76:)
73:2
70:+
67:2
64:(
42:f
38:e
34:d
30:c
26:b
22:a
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
.svg)