×

zbMATH — the first resource for mathematics

Linear inequalities for enumerating chains in partially ordered sets. (English) Zbl 1231.06003
Summary: We characterize the linear inequalities satisfied by flag \( f\)-vectors of all finite bounded posets. We do the same for semipure posets. In particular, the closed convex cone generated by flag \( f\)-vectors of bounded posets of fixed rank is shown to be simplicial, and the closed cone generated by flag \( f\)-vectors of semipure posets of fixed rank is shown to be polyhedral. The extreme rays of both of these cones are described explicitly in terms of quasisymmetric functions. The extreme rays of the first cone are then used to define a new basis for the algebra of quasisymmetric functions. This basis has nonnegative structure constants, for which a combinatorial interpretation involving lattice paths is given.
MSC:
06A07 Combinatorics of partially ordered sets
05A15 Exact enumeration problems, generating functions
05E05 Symmetric functions and generalizations
16T30 Connections of Hopf algebras with combinatorics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Marcelo Aguiar, Nantel Bergeron, and Frank Sottile, Combinatorial Hopf algebras and generalized Dehn-Sommerville relations, Compos. Math. 142 (2006), no. 1, 1 – 30. · Zbl 1092.05070 · doi:10.1112/S0010437X0500165X · doi.org
[2] Louis J. Billera and Anders Björner, Face numbers of polytopes and complexes, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 291 – 310. · Zbl 0917.52008
[3] Louis J. Billera and Gábor Hetyei, Linear inequalities for flags in graded partially ordered sets, J. Combin. Theory Ser. A 89 (2000), no. 1, 77 – 104. · Zbl 0959.52010 · doi:10.1006/jcta.1999.3008 · doi.org
[4] Louis J. Billera and Gábor Hetyei, Decompositions of partially ordered sets, Order 17 (2000), no. 2, 141 – 166. · Zbl 0982.06002 · doi:10.1023/A:1006420120193 · doi.org
[5] Louis J. Billera, Samuel K. Hsiao, and Stephanie van Willigenburg, Peak quasisymmetric functions and Eulerian enumeration, Adv. Math. 176 (2003), no. 2, 248 – 276. · Zbl 1027.05105 · doi:10.1016/S0001-8708(02)00067-1 · doi.org
[6] Louis J. Billera and Niandong Liu, Noncommutative enumeration in graded posets, J. Algebraic Combin. 12 (2000), no. 1, 7 – 24. · Zbl 0971.05005 · doi:10.1023/A:1008703300280 · doi.org
[7] A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1819 – 1872. · Zbl 0851.52016
[8] A. Björner, P. Frankl, and R. Stanley, The number of faces of balanced Cohen-Macaulay complexes and a generalized Macaulay theorem, Combinatorica 7 (1987), no. 1, 23 – 34. · Zbl 0651.05010 · doi:10.1007/BF02579197 · doi.org
[9] Anders Björner and Michelle Wachs, On lexicographically shellable posets, Trans. Amer. Math. Soc. 277 (1983), no. 1, 323 – 341. · Zbl 0514.05009
[10] Anders Björner and Michelle L. Wachs, Shellable nonpure complexes and posets. I, Trans. Amer. Math. Soc. 348 (1996), no. 4, 1299 – 1327. · Zbl 0857.05102
[11] Anders Björner and Michelle L. Wachs, Shellable nonpure complexes and posets. II, Trans. Amer. Math. Soc. 349 (1997), no. 10, 3945 – 3975. · Zbl 0886.05126
[12] Anders Björner, Michelle Wachs, and Volkmar Welker, On sequentially Cohen-Macaulay complexes and posets, Israel J. Math. 169 (2009), 295 – 316. · Zbl 1247.05270 · doi:10.1007/s11856-009-0012-2 · doi.org
[13] Richard Ehrenborg, On posets and Hopf algebras, Adv. Math. 119 (1996), no. 1, 1 – 25. · Zbl 0851.16033 · doi:10.1006/aima.1996.0026 · doi.org
[14] Peter Frankl, Zoltán Füredi, and Gil Kalai, Shadows of colored complexes, Math. Scand. 63 (1988), no. 2, 169 – 178. · Zbl 0651.05003 · doi:10.7146/math.scand.a-12231 · doi.org
[15] Gábor Hetyei, Graphs and balanced simplicial complexes, Graphs Combin. 18 (2002), no. 3, 533 – 564. · Zbl 1015.52011 · doi:10.1007/s003730200039 · doi.org
[16] William R. Schmitt, Antipodes and incidence coalgebras, J. Combin. Theory Ser. A 46 (1987), no. 2, 264 – 290. · Zbl 0699.05003 · doi:10.1016/0097-3165(87)90006-9 · doi.org
[17] John Shareshian, On the shellability of the order complex of the subgroup lattice of a finite group, Trans. Amer. Math. Soc. 353 (2001), no. 7, 2689 – 2703. · Zbl 0982.06004
[18] Richard P. Stanley, Balanced Cohen-Macaulay complexes, Trans. Amer. Math. Soc. 249 (1979), no. 1, 139 – 157. · Zbl 0411.05012
[19] Richard P. Stanley, Some aspects of groups acting on finite posets, J. Combin. Theory Ser. A 32 (1982), no. 2, 132 – 161. · Zbl 0496.06001 · doi:10.1016/0097-3165(82)90017-6 · doi.org
[20] Richard P. Stanley, Combinatorics and commutative algebra, 2nd ed., Progress in Mathematics, vol. 41, Birkhäuser Boston, Inc., Boston, MA, 1996. · Zbl 0838.13008
[21] Richard P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota; Corrected reprint of the 1986 original. · Zbl 0889.05001
[22] Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. · Zbl 0928.05001
[23] Michelle L. Wachs, Whitney homology of semipure shellable posets, J. Algebraic Combin. 9 (1999), no. 2, 173 – 207. · Zbl 0922.06005 · doi:10.1023/A:1018694401498 · doi.org
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.