Linear inequalities for enumerating chains in partially ordered sets

Hsiao, Samuel; Rose, Lauren; Stahl, Rachel; Winston, Ezra

doi:10.1090/S0002-9947-2010-05253-5

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