Linear inequalities for enumerating chains in partially ordered sets
HTML articles powered by AMS MathViewer
- by Samuel K. Hsiao, Lauren Rose, Rachel Stahl and Ezra M. Winston PDF
- Trans. Amer. Math. Soc. 363 (2011), 2715-2732 Request permission
Abstract:
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.References
- Marcelo Aguiar, Nantel Bergeron, and Frank Sottile, Combinatorial Hopf algebras and generalized Dehn-Sommerville relations, Compos. Math. 142 (2006), no. 1, 1–30. MR 2196760, DOI 10.1112/S0010437X0500165X
- 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. MR 1730171
- 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. MR 1736134, DOI 10.1006/jcta.1999.3008
- Louis J. Billera and Gábor Hetyei, Decompositions of partially ordered sets, Order 17 (2000), no. 2, 141–166. MR 1795999, DOI 10.1023/A:1006420120193
- Louis J. Billera, Samuel K. Hsiao, and Stephanie van Willigenburg, Peak quasisymmetric functions and Eulerian enumeration, Adv. Math. 176 (2003), no. 2, 248–276. MR 1982883, DOI 10.1016/S0001-8708(02)00067-1
- Louis J. Billera and Niandong Liu, Noncommutative enumeration in graded posets, J. Algebraic Combin. 12 (2000), no. 1, 7–24. MR 1791443, DOI 10.1023/A:1008703300280
- A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1819–1872. MR 1373690
- 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. MR 905148, DOI 10.1007/BF02579197
- Anders Björner and Michelle Wachs, On lexicographically shellable posets, Trans. Amer. Math. Soc. 277 (1983), no. 1, 323–341. MR 690055, DOI 10.1090/S0002-9947-1983-0690055-6
- Anders Björner and Michelle L. Wachs, Shellable nonpure complexes and posets. I, Trans. Amer. Math. Soc. 348 (1996), no. 4, 1299–1327. MR 1333388, DOI 10.1090/S0002-9947-96-01534-6
- Anders Björner and Michelle L. Wachs, Shellable nonpure complexes and posets. II, Trans. Amer. Math. Soc. 349 (1997), no. 10, 3945–3975. MR 1401765, DOI 10.1090/S0002-9947-97-01838-2
- Anders Björner, Michelle Wachs, and Volkmar Welker, On sequentially Cohen-Macaulay complexes and posets, Israel J. Math. 169 (2009), 295–316. MR 2460907, DOI 10.1007/s11856-009-0012-2
- Richard Ehrenborg, On posets and Hopf algebras, Adv. Math. 119 (1996), no. 1, 1–25. MR 1383883, DOI 10.1006/aima.1996.0026
- Peter Frankl, Zoltán Füredi, and Gil Kalai, Shadows of colored complexes, Math. Scand. 63 (1988), no. 2, 169–178. MR 1018807, DOI 10.7146/math.scand.a-12231
- Gábor Hetyei, Graphs and balanced simplicial complexes, Graphs Combin. 18 (2002), no. 3, 533–564. MR 1939073, DOI 10.1007/s003730200039
- William R. Schmitt, Antipodes and incidence coalgebras, J. Combin. Theory Ser. A 46 (1987), no. 2, 264–290. MR 914660, DOI 10.1016/0097-3165(87)90006-9
- 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. MR 1828468, DOI 10.1090/S0002-9947-01-02730-1
- Richard P. Stanley, Balanced Cohen-Macaulay complexes, Trans. Amer. Math. Soc. 249 (1979), no. 1, 139–157. MR 526314, DOI 10.1090/S0002-9947-1979-0526314-6
- Richard P. Stanley, Some aspects of groups acting on finite posets, J. Combin. Theory Ser. A 32 (1982), no. 2, 132–161. MR 654618, DOI 10.1016/0097-3165(82)90017-6
- Richard P. Stanley, Combinatorics and commutative algebra, 2nd ed., Progress in Mathematics, vol. 41, Birkhäuser Boston, Inc., Boston, MA, 1996. MR 1453579
- 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. MR 1442260, DOI 10.1017/CBO9780511805967
- 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. MR 1676282, DOI 10.1017/CBO9780511609589
- Michelle L. Wachs, Whitney homology of semipure shellable posets, J. Algebraic Combin. 9 (1999), no. 2, 173–207. MR 1679252, DOI 10.1023/A:1018694401498
Additional Information
- Samuel K. Hsiao
- Affiliation: Mathematics Program, Bard College, Annandale-on-Hudson, New York 12504
- Lauren Rose
- Affiliation: Mathematics Program, Bard College, Annandale-on-Hudson, New York 12504
- Rachel Stahl
- Affiliation: Mathematics Program, Bard College, Annandale-on-Hudson, New York 12504
- Ezra M. Winston
- Affiliation: Mathematics Program, Bard College, Annandale-on-Hudson, New York 12504
- Received by editor(s): April 10, 2009
- Received by editor(s) in revised form: October 19, 2009
- Published electronically: November 30, 2010
- © Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 363 (2011), 2715-2732
- MSC (2010): Primary 06A07, 05E99, 16T30
- DOI: https://doi.org/10.1090/S0002-9947-2010-05253-5
- MathSciNet review: 2763734