zbMATH — the first resource for mathematics

Two poset polytopes. (English) Zbl 0595.52008
With a partially ordered set \(P\) with \(n\) elements, the author associates two \(n\)-dimensional convex polytopes, the order polytope \(\mathcal O(P)\) and the chain polytope \(\mathcal C(P)\). He determines the face lattice of \(\mathcal O(P)\), the vertices of \(\mathcal C(P)\), and describes a piecewise-linear bijection from \(\mathcal O(P)\) onto \(\mathcal C(P)\) which allows to transfer properties of \(\mathcal O(P)\) over to \(\mathcal C(P)\). It is shown that the Ehrhart polynomials of \(\mathcal O(P)\) and \(\mathcal C(P)\) satisfy \(i(\mathcal O(P),m)=i(\mathcal C(P),m)=\Omega (P,m+1)\), where \(\Omega(P,m)\), the order polynomial, is the number of order-preserving maps \(P\to \{1,\ldots,m\}\). In particular, \(n!\,\mathrm{vol}\,\mathcal O(P)= n!\,\mathrm{vol}\,\mathcal C(P)\) is the number of linear extensions of \(P\). Similarly as in a former paper [J. Comb. Theory Ser. A 31, 56–65 (1981; Zbl 0484.05012)], the author uses the Aleksandrov-Fenchel inequalities for mixed volumes in connection with \(\mathcal C(P)\) to obtain new log-concave sequences involving linear extensions of \(P\).

52B12 Special polytopes (linear programming, centrally symmetric, etc.)
06A06 Partial orders, general
Full Text: DOI EuDML
[1] Björner, A.; Garsia, A.; Stanley, R.; Rival, I. (ed.), An introduction to the theory of Cohen-Maculay partially ordered sets, 583-616, (1982), Dordrecht-Boston-London
[2] Chvátal, V., On certain polytopes associated with graphs, J. Combin. Theory Ser B, 18, 138-154, (1975) · Zbl 0277.05139
[3] L. Comtet, Advanced Combinatorics, Reidel, Dordrecht-Boston, 1974. · Zbl 0283.05001
[4] Doberkat, E. E., Problem 84-20, SIAM Review, 26, 580-580, (1984)
[5] B. Dreesen, W. Poguntke, and P. Winkler, Comparability invariance of the fixed point property, preprint. · Zbl 0577.06005
[6] L. Geissinger, A polytope associated to a finite ordered set, preprint. · Zbl 0523.06005
[7] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980. · Zbl 0541.05054
[8] Habib, M., Comparability invariants, Ann. Discrete Math., 23, 371-386, (1984)
[9] Kahn, J.; Saks, M., Balancing poset extensions, Order, 1, 113-126, (1984) · Zbl 0561.06004
[10] Macdonald, I. G.; Nelsen, R. B., Solution to E2701, Amer. Math. Monthly, 86, 396-396, (1979)
[11] J. S. Provan and L. J. Billera, Simplicial Complexes Associated with Convex Polyhedra, I: Constructions and Combinatorial Examples, Technical Rept. no. 402, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York, January 1979.
[12] Stanley, R., A chromatic-like polynomial for ordered sets, 421-427, (1970), Chapel Hill
[13] R. Stanley, Ordered structures and partitions, Mem. Amer. Math. Society, no. 119, 1972. · Zbl 0246.05007
[14] Stanley, R.; Aigner, M. (ed.), Eulerian partitions of a unit hypercube, 49-49, (1977), Dordrecht-Boston
[15] Stanley, R., Decompositions of rational convex polytopes, Ann. Discrete Math., 6, 333-342, (1980) · Zbl 0812.52012
[16] Stanley, R., Two combinatorial applications of the Aleksandrov-Fenchel inequalities, J. Combin. Theory Ser A, 31, 56-65, (1981) · Zbl 0484.05012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.