scientific article; zbMATH DE number 1028228
After some preliminaries, the author shows that Dilworth's theorem, perhaps the most important result in the theory of partial orders, follows from and implies the defect form of Hall's marriage theorem. He then introduces various graphs and digraphs associated with partially ordered sets and discusses how properties of the partial orders are reflected in the graphs. In particular, he presents a characterization due to Ghouli-Houri and Gilmore and Hoffman of graphs that are the comparability graph of some partial order and he discusses the classic result of Gallai on the relation between partial orders that have the same comparability graph. He also considers the incidence order of a graph and proves Schnyder's theorem that a graph is planar if and only if the dimension of its incidence order is at most three. For the entire collection see [Zbl 0862.00008].
- A bipartite analogue of Dilworth's theorem for multiple partial orders
- Ordering orders
- Spacetime is as spacetime does
- Segment orders
- scientific article; zbMATH DE number 4156160 (Why is no real title available?)
- Minimal elements for product orders
- The Hardness of Approximating Poset Dimension
- scientific article; zbMATH DE number 4195994 (Why is no real title available?)
- Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4342018)
