# Dimension Theory for Ordered Sets

Ontology type: schema:Chapter

### Chapter Info

DATE

1982

AUTHORS

David Kelly , William T. Trotter

ABSTRACT

In 1930, E. Szpilrajn proved that any order relation on a set X can be extended to a linear order on X. It also follows that any order relation is the intersection of its linear extensions. B. Dushnik and E.W. Miller later defined the dimension of an ordered set P = 〈X;≤〉 to be the minimum number of linear extensions whose intersection is the ordering ≤. For a cardinal m, $${\underset{\raise0.3em\hbox{\smash{\scriptscriptstyle\thicksim}}}{2} ^m}$$ denotes the subsets of m, ordered by inclusion. As the notation indicates, $${\underset{\raise0.3em\hbox{\smash{\scriptscriptstyle\thicksim}}}{2} ^m}$$ is a product of 2-element chains (linearly ordered sets). Any poset 〈X;≤〉 with ∣x∣ ≤ m can be embedded in $${\underset{\raise0.3em\hbox{\smash{\scriptscriptstyle\thicksim}}}{2} ^m}$$. O. Ore proved that the dimension of a poset P is the least number of chains whose product contains P as a subposet. He also showed that the product of m nontrivial chains has dimension m. In particular, $${\underset{\raise0.3em\hbox{\smash{\scriptscriptstyle\thicksim}}}{2} ^m}$$ has dimension m, a result of H. Komm. Thus, every cardinal is the dimension of some poset. It is usually very difficult to calculate the dimension of any “standard” poset. However, dimension can be related to other parameters of a poset. For example, the dimension of a finite poset does not exceed the size of any maximal antichain. Also, T. Hiraguchi showed that any poset of dimension d ≥ 3 has at least 2d elements. Moreover, any integer ≥ 2d is the size of some poset of dimension d. Let d be a positive integer. A poset is d-irreducible if it has dimension d and removal of any element lowers its dimension. Any poset whose dimension is at least d contains a d-irreducible subposet. Although there is only one 2-irreducible poset, there are infinitely many d-irreducible posets whenever d ≥ 3. The set of all 3-irreducible posets was independently determined by D. Kelly and W.T. Trotter, Jr. and J.I. Moore, Jr. There is a 3-irreducible poset of any size n not excluded by Hiraguchi; i.e., for any n ≥ 6. However, R.J. Kimble, Jr. has shown that a d-irreducible poset cannot have size 2d + 1 when d ≥ 4. If d ≥ 4 and n ≥ 2d but n ≠ 2d + 1, then there is a d-irreducible poset of size n. A finite poset is planar if its diagram can be drawn in the plane without any crossing of lines. Planar posets have arbitrary finite dimension. However, K.A. Baker showed that a finite lattice is planar exactly when its dimension does not exceed 2. He also showed that the completion of a poset is a lattice that has the same dimension as the poset. Baker’s results and three papers of D. Kelly and I. Rival were used to obtain the list of 3-irreducible posets. The approach of W.T. Trotter and J.I. Moore, Jr. rested on the observation of Dushnik and Miller that a poset has dimension at most 2 if and only if its incomparability graph is a comparability graph. T. Gallai’s characterization of comparability graphs in terms of excluded subgraphs was then applied. More... »

PAGES

171-211

### Book

TITLE

Ordered Sets

ISBN

978-94-009-7800-3
978-94-009-7798-3

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-94-009-7798-3_5

DOI

http://dx.doi.org/10.1007/978-94-009-7798-3_5

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1048349248

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Pure Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "University of Manitoba",
"id": "https://www.grid.ac/institutes/grid.21613.37",
"name": [
"Department of Mathematics and Astronomy, The University of Manitoba, Winnipeg, R3T 2N2, Canada"
],
"type": "Organization"
},
"familyName": "Kelly",
"givenName": "David",
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of South Carolina",
"id": "https://www.grid.ac/institutes/grid.254567.7",
"name": [
"Department of Mathematics and Statistics, University of South Carolina, Columbia, South Carolina\u00a029208, USA"
],
"type": "Organization"
},
"familyName": "Trotter",
"givenName": "William T.",
"id": "sg:person.016230330371.47",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016230330371.47"
],
"type": "Person"
}
],
"citation": [
{
"id": "https://doi.org/10.1016/0012-365x(80)90141-7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001287404"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0097-3165(76)90081-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001411333"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02253207",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001791602",
"https://doi.org/10.1007/bf02253207"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02253207",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001791602",
"https://doi.org/10.1007/bf02253207"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0012-365x(81)90203-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002442062"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02485838",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003100180",
"https://doi.org/10.1007/bf02485838"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02485838",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003100180",
"https://doi.org/10.1007/bf02485838"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1090/s0002-9939-1975-0369192-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005751833"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0012-365x(76)90111-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005780935"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02020961",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005931527",
"https://doi.org/10.1007/bf02020961"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02020961",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005931527",
"https://doi.org/10.1007/bf02020961"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0012-365x(74)90113-7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006584813"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0012-365x(76)90095-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007609182"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02483085",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013486384",
"https://doi.org/10.1007/bf02483085"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02483085",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013486384",
"https://doi.org/10.1007/bf02483085"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0097-3165(77)90046-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015956904"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0012-365x(76)80011-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1016261296"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0012-365x(75)90031-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1016482131"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0022-2496(70)90062-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017204684"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0012-365x(73)90024-1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017418677"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0097-3165(78)90032-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017675819"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0012-365x(80)90157-0",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018061858"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02483890",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1019986327",
"https://doi.org/10.1007/bf02483890"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02483890",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1019986327",
"https://doi.org/10.1007/bf02483890"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1090/s0002-9939-1976-0417001-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1021521074"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0095-8956(80)90043-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1021997354"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/mana.19700460115",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1022371177"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02276109",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1023440538",
"https://doi.org/10.1007/bf02276109"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/net.3230020103",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1024275235"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0095-8956(76)90024-1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1025374458"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0097-3165(78)90030-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1025376248"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/malq.19560020803",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027543387"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0097-3165(76)90004-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027944443"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01683266",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029752051",
"https://doi.org/10.1007/bf01683266"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01683266",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029752051",
"https://doi.org/10.1007/bf01683266"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0012-365x(79)90082-7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031455717"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1090/s0002-9939-1950-0038922-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031665808"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0095-8956(77)90048-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031842206"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1090/s0002-9939-1974-0329988-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032324647"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1112/jlms/s2-3.2.260",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032474322"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0012-365x(76)90052-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1033981023"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0097-3165(74)90098-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039882552"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0095-8956(77)90049-1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041396395"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1090/s0002-9939-1977-0450144-0",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043199262"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0097-3165(75)90019-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043831328"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0167-5060(08)70731-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1046754752"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1112/jlms/s2-21.1.31",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1048790061"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0012-365x(73)90025-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1049092770"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01895851",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1049981496",
"https://doi.org/10.1007/bf01895851"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01895851",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1049981496",
"https://doi.org/10.1007/bf01895851"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01900297",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1050039277",
"https://doi.org/10.1007/bf01900297"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01900297",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1050039277",
"https://doi.org/10.1007/bf01900297"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02485278",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1050805038",
"https://doi.org/10.1007/bf02485278"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02485278",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1050805038",
"https://doi.org/10.1007/bf02485278"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01896428",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1051024082",
"https://doi.org/10.1007/bf01896428"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01896428",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1051024082",
"https://doi.org/10.1007/bf01896428"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0012-365x(76)90007-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1051859468"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0304-3975(76)90059-1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052030997"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.2307/1969503",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1069674881"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.2307/2371374",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1069898094"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.4153/cjm-1964-055-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1072264594"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.4153/cjm-1974-120-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1072265938"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.4153/cjm-1975-074-0",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1072266040"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.4153/cjm-1977-040-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1072266282"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.4153/cjm-1978-104-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1072266479"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.4153/cjm-1979-003-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1072266489"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.4153/cmb-1974-016-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1072270258"
],
"type": "CreativeWork"
}
],
"datePublished": "1982",
"datePublishedReg": "1982-01-01",
"description": "In 1930, E. Szpilrajn proved that any order relation on a set X can be extended to a linear order on X. It also follows that any order relation is the intersection of its linear extensions. B. Dushnik and E.W. Miller later defined the dimension of an ordered set P = \u3008X;\u2264\u3009 to be the minimum number of linear extensions whose intersection is the ordering \u2264. For a cardinal m, \$${\\underset{\\raise0.3em\\hbox{\\smash{\\scriptscriptstyle\\thicksim}}}{2} ^m}\$$ denotes the subsets of m, ordered by inclusion. As the notation indicates, \$${\\underset{\\raise0.3em\\hbox{\\smash{\\scriptscriptstyle\\thicksim}}}{2} ^m}\$$ is a product of 2-element chains (linearly ordered sets). Any poset \u3008X;\u2264\u3009 with \u2223x\u2223 \u2264 m can be embedded in \$${\\underset{\\raise0.3em\\hbox{\\smash{\\scriptscriptstyle\\thicksim}}}{2} ^m}\$$. O. Ore proved that the dimension of a poset P is the least number of chains whose product contains P as a subposet. He also showed that the product of m nontrivial chains has dimension m. In particular, \$${\\underset{\\raise0.3em\\hbox{\\smash{\\scriptscriptstyle\\thicksim}}}{2} ^m}\$$ has dimension m, a result of H. Komm. Thus, every cardinal is the dimension of some poset. It is usually very difficult to calculate the dimension of any \u201cstandard\u201d poset. However, dimension can be related to other parameters of a poset. For example, the dimension of a finite poset does not exceed the size of any maximal antichain. Also, T. Hiraguchi showed that any poset of dimension d \u2265 3 has at least 2d elements. Moreover, any integer \u2265 2d is the size of some poset of dimension d. Let d be a positive integer. A poset is d-irreducible if it has dimension d and removal of any element lowers its dimension. Any poset whose dimension is at least d contains a d-irreducible subposet. Although there is only one 2-irreducible poset, there are infinitely many d-irreducible posets whenever d \u2265 3. The set of all 3-irreducible posets was independently determined by D. Kelly and W.T. Trotter, Jr. and J.I. Moore, Jr. There is a 3-irreducible poset of any size n not excluded by Hiraguchi; i.e., for any n \u2265 6. However, R.J. Kimble, Jr. has shown that a d-irreducible poset cannot have size 2d + 1 when d \u2265 4. If d \u2265 4 and n \u2265 2d but n \u2260 2d + 1, then there is a d-irreducible poset of size n. A finite poset is planar if its diagram can be drawn in the plane without any crossing of lines. Planar posets have arbitrary finite dimension. However, K.A. Baker showed that a finite lattice is planar exactly when its dimension does not exceed 2. He also showed that the completion of a poset is a lattice that has the same dimension as the poset. Baker\u2019s results and three papers of D. Kelly and I. Rival were used to obtain the list of 3-irreducible posets. The approach of W.T. Trotter and J.I. Moore, Jr. rested on the observation of Dushnik and Miller that a poset has dimension at most 2 if and only if its incomparability graph is a comparability graph. T. Gallai\u2019s characterization of comparability graphs in terms of excluded subgraphs was then applied.",
"editor": [
{
"familyName": "Rival",
"givenName": "Ivan",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-94-009-7798-3_5",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-94-009-7800-3",
"978-94-009-7798-3"
],
"name": "Ordered Sets",
"type": "Book"
},
"name": "Dimension Theory for Ordered Sets",
"pagination": "171-211",
"productId": [
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-94-009-7798-3_5"
]
},
{
"type": "PropertyValue",
"value": [
"e653d005223a5e0ca395496f73cedbd8a95549f31eec4ae27330f440b6993791"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1048349248"
]
}
],
"publisher": {
"location": "Dordrecht",
"name": "Springer Netherlands",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-94-009-7798-3_5",
"https://app.dimensions.ai/details/publication/pub.1048349248"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-15T14:28",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8669_00000273.jsonl",
"type": "Chapter",
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-94-009-7798-3_5'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-94-009-7798-3_5'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-94-009-7798-3_5'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-94-009-7798-3_5'

This table displays all metadata directly associated to this object as RDF triples.

256 TRIPLES      23 PREDICATES      84 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0101
3 schema:author Nea918f06ca124c24a9ebf23de94c73bc
4 schema:citation sg:pub.10.1007/bf01683266
5 sg:pub.10.1007/bf01895851
6 sg:pub.10.1007/bf01896428
7 sg:pub.10.1007/bf01900297
8 sg:pub.10.1007/bf02020961
9 sg:pub.10.1007/bf02253207
10 sg:pub.10.1007/bf02276109
11 sg:pub.10.1007/bf02483085
12 sg:pub.10.1007/bf02483890
13 sg:pub.10.1007/bf02485278
14 sg:pub.10.1007/bf02485838
15 https://doi.org/10.1002/malq.19560020803
16 https://doi.org/10.1002/mana.19700460115
17 https://doi.org/10.1002/net.3230020103
18 https://doi.org/10.1016/0012-365x(73)90024-1
19 https://doi.org/10.1016/0012-365x(73)90025-3
20 https://doi.org/10.1016/0012-365x(74)90113-7
21 https://doi.org/10.1016/0012-365x(75)90031-x
22 https://doi.org/10.1016/0012-365x(76)90007-8
23 https://doi.org/10.1016/0012-365x(76)90052-2
24 https://doi.org/10.1016/0012-365x(76)90095-9
25 https://doi.org/10.1016/0012-365x(76)90111-4
26 https://doi.org/10.1016/0012-365x(79)90082-7
27 https://doi.org/10.1016/0012-365x(80)90141-7
28 https://doi.org/10.1016/0012-365x(80)90157-0
29 https://doi.org/10.1016/0012-365x(81)90203-x
30 https://doi.org/10.1016/0022-2496(70)90062-3
31 https://doi.org/10.1016/0095-8956(76)90024-1
32 https://doi.org/10.1016/0095-8956(77)90048-x
33 https://doi.org/10.1016/0095-8956(77)90049-1
34 https://doi.org/10.1016/0095-8956(80)90043-x
35 https://doi.org/10.1016/0097-3165(74)90098-3
36 https://doi.org/10.1016/0097-3165(75)90019-9
37 https://doi.org/10.1016/0097-3165(76)90004-2
38 https://doi.org/10.1016/0097-3165(76)90081-9
39 https://doi.org/10.1016/0097-3165(77)90046-2
40 https://doi.org/10.1016/0097-3165(78)90030-4
41 https://doi.org/10.1016/0097-3165(78)90032-8
42 https://doi.org/10.1016/0304-3975(76)90059-1
43 https://doi.org/10.1016/s0012-365x(76)80011-8
44 https://doi.org/10.1016/s0167-5060(08)70731-3
45 https://doi.org/10.1090/s0002-9939-1950-0038922-4
46 https://doi.org/10.1090/s0002-9939-1974-0329988-9
47 https://doi.org/10.1090/s0002-9939-1975-0369192-2
48 https://doi.org/10.1090/s0002-9939-1976-0417001-6
49 https://doi.org/10.1090/s0002-9939-1977-0450144-0
50 https://doi.org/10.1112/jlms/s2-21.1.31
51 https://doi.org/10.1112/jlms/s2-3.2.260
52 https://doi.org/10.2307/1969503
53 https://doi.org/10.2307/2371374
54 https://doi.org/10.4153/cjm-1964-055-5
55 https://doi.org/10.4153/cjm-1974-120-2
56 https://doi.org/10.4153/cjm-1975-074-0
57 https://doi.org/10.4153/cjm-1977-040-3
58 https://doi.org/10.4153/cjm-1978-104-2
59 https://doi.org/10.4153/cjm-1979-003-8
60 https://doi.org/10.4153/cmb-1974-016-3
61 schema:datePublished 1982
62 schema:datePublishedReg 1982-01-01
63 schema:description In 1930, E. Szpilrajn proved that any order relation on a set X can be extended to a linear order on X. It also follows that any order relation is the intersection of its linear extensions. B. Dushnik and E.W. Miller later defined the dimension of an ordered set P = 〈X;≤〉 to be the minimum number of linear extensions whose intersection is the ordering ≤. For a cardinal m, $${\underset{\raise0.3em\hbox{\smash{\scriptscriptstyle\thicksim}}}{2} ^m}$$ denotes the subsets of m, ordered by inclusion. As the notation indicates, $${\underset{\raise0.3em\hbox{\smash{\scriptscriptstyle\thicksim}}}{2} ^m}$$ is a product of 2-element chains (linearly ordered sets). Any poset 〈X;≤〉 with ∣x∣ ≤ m can be embedded in $${\underset{\raise0.3em\hbox{\smash{\scriptscriptstyle\thicksim}}}{2} ^m}$$. O. Ore proved that the dimension of a poset P is the least number of chains whose product contains P as a subposet. He also showed that the product of m nontrivial chains has dimension m. In particular, $${\underset{\raise0.3em\hbox{\smash{\scriptscriptstyle\thicksim}}}{2} ^m}$$ has dimension m, a result of H. Komm. Thus, every cardinal is the dimension of some poset. It is usually very difficult to calculate the dimension of any “standard” poset. However, dimension can be related to other parameters of a poset. For example, the dimension of a finite poset does not exceed the size of any maximal antichain. Also, T. Hiraguchi showed that any poset of dimension d ≥ 3 has at least 2d elements. Moreover, any integer ≥ 2d is the size of some poset of dimension d. Let d be a positive integer. A poset is d-irreducible if it has dimension d and removal of any element lowers its dimension. Any poset whose dimension is at least d contains a d-irreducible subposet. Although there is only one 2-irreducible poset, there are infinitely many d-irreducible posets whenever d ≥ 3. The set of all 3-irreducible posets was independently determined by D. Kelly and W.T. Trotter, Jr. and J.I. Moore, Jr. There is a 3-irreducible poset of any size n not excluded by Hiraguchi; i.e., for any n ≥ 6. However, R.J. Kimble, Jr. has shown that a d-irreducible poset cannot have size 2d + 1 when d ≥ 4. If d ≥ 4 and n ≥ 2d but n ≠ 2d + 1, then there is a d-irreducible poset of size n. A finite poset is planar if its diagram can be drawn in the plane without any crossing of lines. Planar posets have arbitrary finite dimension. However, K.A. Baker showed that a finite lattice is planar exactly when its dimension does not exceed 2. He also showed that the completion of a poset is a lattice that has the same dimension as the poset. Baker’s results and three papers of D. Kelly and I. Rival were used to obtain the list of 3-irreducible posets. The approach of W.T. Trotter and J.I. Moore, Jr. rested on the observation of Dushnik and Miller that a poset has dimension at most 2 if and only if its incomparability graph is a comparability graph. T. Gallai’s characterization of comparability graphs in terms of excluded subgraphs was then applied.
65 schema:genre chapter
66 schema:inLanguage en
67 schema:isAccessibleForFree false
69 schema:name Dimension Theory for Ordered Sets
70 schema:pagination 171-211
71 schema:productId N0bd4dfd546a84a77bc859d89e4d01f9e
72 N4031a38dcd814da7a725a2cbc927ace8
73 Ndd98b88d7c3449e197197ae24a686d42
74 schema:publisher N49c4bb92c6e0481193c3a687bd60873e
75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048349248
76 https://doi.org/10.1007/978-94-009-7798-3_5
77 schema:sdDatePublished 2019-04-15T14:28
79 schema:sdPublisher N79b7782944ef4eaabbf4a7562c7b0c27
82 sgo:sdDataset chapters
83 rdf:type schema:Chapter
85 schema:value e653d005223a5e0ca395496f73cedbd8a95549f31eec4ae27330f440b6993791
86 rdf:type schema:PropertyValue
87 N2cacc0787ff64fbaa6710314d61598fa rdf:first sg:person.016230330371.47
88 rdf:rest rdf:nil
89 N4031a38dcd814da7a725a2cbc927ace8 schema:name doi
90 schema:value 10.1007/978-94-009-7798-3_5
91 rdf:type schema:PropertyValue
92 N49c4bb92c6e0481193c3a687bd60873e schema:location Dordrecht
93 schema:name Springer Netherlands
94 rdf:type schema:Organisation
95 N79b7782944ef4eaabbf4a7562c7b0c27 schema:name Springer Nature - SN SciGraph project
96 rdf:type schema:Organization
97 N7dc1e3d8f3cf4863835dd5fe0777070c schema:familyName Rival
98 schema:givenName Ivan
99 rdf:type schema:Person
101 rdf:rest rdf:nil
102 Nc0f66f0dd196426393d2081a3fd030a2 schema:affiliation https://www.grid.ac/institutes/grid.21613.37
103 schema:familyName Kelly
104 schema:givenName David
105 rdf:type schema:Person
106 Ndd98b88d7c3449e197197ae24a686d42 schema:name dimensions_id
107 schema:value pub.1048349248
108 rdf:type schema:PropertyValue
110 978-94-009-7800-3
111 schema:name Ordered Sets
112 rdf:type schema:Book
113 Nea918f06ca124c24a9ebf23de94c73bc rdf:first Nc0f66f0dd196426393d2081a3fd030a2
114 rdf:rest N2cacc0787ff64fbaa6710314d61598fa
115 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
116 schema:name Mathematical Sciences
117 rdf:type schema:DefinedTerm
118 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
119 schema:name Pure Mathematics
120 rdf:type schema:DefinedTerm
121 sg:person.016230330371.47 schema:affiliation https://www.grid.ac/institutes/grid.254567.7
122 schema:familyName Trotter
123 schema:givenName William T.
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016230330371.47
125 rdf:type schema:Person
126 sg:pub.10.1007/bf01683266 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029752051
127 https://doi.org/10.1007/bf01683266
128 rdf:type schema:CreativeWork
129 sg:pub.10.1007/bf01895851 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049981496
130 https://doi.org/10.1007/bf01895851
131 rdf:type schema:CreativeWork
132 sg:pub.10.1007/bf01896428 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051024082
133 https://doi.org/10.1007/bf01896428
134 rdf:type schema:CreativeWork
135 sg:pub.10.1007/bf01900297 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050039277
136 https://doi.org/10.1007/bf01900297
137 rdf:type schema:CreativeWork
138 sg:pub.10.1007/bf02020961 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005931527
139 https://doi.org/10.1007/bf02020961
140 rdf:type schema:CreativeWork
141 sg:pub.10.1007/bf02253207 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001791602
142 https://doi.org/10.1007/bf02253207
143 rdf:type schema:CreativeWork
144 sg:pub.10.1007/bf02276109 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023440538
145 https://doi.org/10.1007/bf02276109
146 rdf:type schema:CreativeWork
147 sg:pub.10.1007/bf02483085 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013486384
148 https://doi.org/10.1007/bf02483085
149 rdf:type schema:CreativeWork
150 sg:pub.10.1007/bf02483890 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019986327
151 https://doi.org/10.1007/bf02483890
152 rdf:type schema:CreativeWork
153 sg:pub.10.1007/bf02485278 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050805038
154 https://doi.org/10.1007/bf02485278
155 rdf:type schema:CreativeWork
156 sg:pub.10.1007/bf02485838 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003100180
157 https://doi.org/10.1007/bf02485838
158 rdf:type schema:CreativeWork
159 https://doi.org/10.1002/malq.19560020803 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027543387
160 rdf:type schema:CreativeWork
161 https://doi.org/10.1002/mana.19700460115 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022371177
162 rdf:type schema:CreativeWork
163 https://doi.org/10.1002/net.3230020103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024275235
164 rdf:type schema:CreativeWork
165 https://doi.org/10.1016/0012-365x(73)90024-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017418677
166 rdf:type schema:CreativeWork
167 https://doi.org/10.1016/0012-365x(73)90025-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049092770
168 rdf:type schema:CreativeWork
169 https://doi.org/10.1016/0012-365x(74)90113-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006584813
170 rdf:type schema:CreativeWork
171 https://doi.org/10.1016/0012-365x(75)90031-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1016482131
172 rdf:type schema:CreativeWork
173 https://doi.org/10.1016/0012-365x(76)90007-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051859468
174 rdf:type schema:CreativeWork
175 https://doi.org/10.1016/0012-365x(76)90052-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033981023
176 rdf:type schema:CreativeWork
177 https://doi.org/10.1016/0012-365x(76)90095-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007609182
178 rdf:type schema:CreativeWork
179 https://doi.org/10.1016/0012-365x(76)90111-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005780935
180 rdf:type schema:CreativeWork
181 https://doi.org/10.1016/0012-365x(79)90082-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031455717
182 rdf:type schema:CreativeWork
183 https://doi.org/10.1016/0012-365x(80)90141-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001287404
184 rdf:type schema:CreativeWork
185 https://doi.org/10.1016/0012-365x(80)90157-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018061858
186 rdf:type schema:CreativeWork
187 https://doi.org/10.1016/0012-365x(81)90203-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1002442062
188 rdf:type schema:CreativeWork
189 https://doi.org/10.1016/0022-2496(70)90062-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017204684
190 rdf:type schema:CreativeWork
191 https://doi.org/10.1016/0095-8956(76)90024-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025374458
192 rdf:type schema:CreativeWork
193 https://doi.org/10.1016/0095-8956(77)90048-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1031842206
194 rdf:type schema:CreativeWork
195 https://doi.org/10.1016/0095-8956(77)90049-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041396395
196 rdf:type schema:CreativeWork
197 https://doi.org/10.1016/0095-8956(80)90043-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1021997354
198 rdf:type schema:CreativeWork
199 https://doi.org/10.1016/0097-3165(74)90098-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039882552
200 rdf:type schema:CreativeWork
201 https://doi.org/10.1016/0097-3165(75)90019-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043831328
202 rdf:type schema:CreativeWork
203 https://doi.org/10.1016/0097-3165(76)90004-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027944443
204 rdf:type schema:CreativeWork
205 https://doi.org/10.1016/0097-3165(76)90081-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001411333
206 rdf:type schema:CreativeWork
207 https://doi.org/10.1016/0097-3165(77)90046-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015956904
208 rdf:type schema:CreativeWork
209 https://doi.org/10.1016/0097-3165(78)90030-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025376248
210 rdf:type schema:CreativeWork
211 https://doi.org/10.1016/0097-3165(78)90032-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017675819
212 rdf:type schema:CreativeWork
213 https://doi.org/10.1016/0304-3975(76)90059-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052030997
214 rdf:type schema:CreativeWork
215 https://doi.org/10.1016/s0012-365x(76)80011-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016261296
216 rdf:type schema:CreativeWork
217 https://doi.org/10.1016/s0167-5060(08)70731-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046754752
218 rdf:type schema:CreativeWork
219 https://doi.org/10.1090/s0002-9939-1950-0038922-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031665808
220 rdf:type schema:CreativeWork
221 https://doi.org/10.1090/s0002-9939-1974-0329988-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032324647
222 rdf:type schema:CreativeWork
223 https://doi.org/10.1090/s0002-9939-1975-0369192-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005751833
224 rdf:type schema:CreativeWork
225 https://doi.org/10.1090/s0002-9939-1976-0417001-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021521074
226 rdf:type schema:CreativeWork
227 https://doi.org/10.1090/s0002-9939-1977-0450144-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043199262
228 rdf:type schema:CreativeWork
229 https://doi.org/10.1112/jlms/s2-21.1.31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048790061
230 rdf:type schema:CreativeWork
231 https://doi.org/10.1112/jlms/s2-3.2.260 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032474322
232 rdf:type schema:CreativeWork
233 https://doi.org/10.2307/1969503 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069674881
234 rdf:type schema:CreativeWork
235 https://doi.org/10.2307/2371374 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069898094
236 rdf:type schema:CreativeWork
237 https://doi.org/10.4153/cjm-1964-055-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072264594
238 rdf:type schema:CreativeWork
239 https://doi.org/10.4153/cjm-1974-120-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072265938
240 rdf:type schema:CreativeWork
241 https://doi.org/10.4153/cjm-1975-074-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072266040
242 rdf:type schema:CreativeWork
243 https://doi.org/10.4153/cjm-1977-040-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072266282
244 rdf:type schema:CreativeWork
245 https://doi.org/10.4153/cjm-1978-104-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072266479
246 rdf:type schema:CreativeWork
247 https://doi.org/10.4153/cjm-1979-003-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072266489
248 rdf:type schema:CreativeWork
249 https://doi.org/10.4153/cmb-1974-016-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072270258
250 rdf:type schema:CreativeWork
251 https://www.grid.ac/institutes/grid.21613.37 schema:alternateName University of Manitoba
252 schema:name Department of Mathematics and Astronomy, The University of Manitoba, Winnipeg, R3T 2N2, Canada
253 rdf:type schema:Organization
254 https://www.grid.ac/institutes/grid.254567.7 schema:alternateName University of South Carolina
255 schema:name Department of Mathematics and Statistics, University of South Carolina, Columbia, South Carolina 29208, USA
256 rdf:type schema:Organization