On the complexity of posets

DOI10.1016/0012-365X(76)90095-9zbMath0351.06003OpenAlexW2036163012MaRDI QIDQ1235192

William T. jun. Trotter, Kenneth P. Bogart

Publication date: 1976

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(76)90095-9

Mathematics Subject Classification ID

Partial orders, general (06A06)

Related Items (22)

Maximum Semiorders in Interval Orders ⋮ On the separation of two relations by a biorder or a semiorder ⋮ Algorithms constructing a representive vector criterion for a binary preference relation ⋮ A recognition algorithm for orders of interval dimension two ⋮ Generalizations of semiorders: A review note ⋮ A construction for partially ordered sets ⋮ Stacks and splits of partially ordered sets ⋮ A min-max property of chordal bipartite graphs with applications ⋮ Adjacency posets of planar graphs ⋮ The dimension of planar posets ⋮ Maximal dimensional partially ordered sets. III: A characterization of Hiraguchi's inequality for interval dimension ⋮ Characterization problems for graphs, partially ordered sets, lattices, and families of sets ⋮ On incomplete preference structures ⋮ Dimension and matchings in comparability and incomparability graphs. ⋮ Dimensions of hypergraphs ⋮ Angle orders ⋮ The Complexity of the Partial Order Dimension Problem ⋮ Split semiorders ⋮ On realizable biorders and the biorder dimension of a relation ⋮ The dimension of the Cartesian product of partial orders ⋮ The relationship between the threshold dimension of split graphs and various dimensional parameters ⋮ Interval dimension is a comparability invariant

Cites Work

• Unnamed Item
• Unnamed Item
• Irreducible posets with large height exist
• The dimension of planar posets
• Dimension of the crown \(S^k_n\)
• Maximal dimensional partially ordered sets. III: A characterization of Hiraguchi's inequality for interval dimension
• A bound on the dimension of interval orders
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• The dimension of semiorders
• Intransitive indifference with unequal indifference intervals
• Maximal dimensional partially ordered sets. I: Hiraguchi's theorem
• Maximal dimensional partially ordered sets. II: Characterization of 2n- element posets with dimension n
• A decomposition theorem for partially ordered sets
• Foundational aspects of theories of measurement
• Inequalities in Dimension Theory for Posets
• Natural Partial Orders

This page was built for publication: On the complexity of posets