×

Balanced and Bruhat graphs. (English) Zbl 1484.06012

Summary: We generalize chain enumeration in graded partially ordered sets by relaxing the graded, poset and Eulerian requirements. The resulting balanced digraphs, which include the classical Eulerian posets having an \(R\)-labeling, imply the existence of the (non-homogeneous) \( \mathbf{cd} \)-index, a key invariant for studying inequalities for the flag vector of polytopes. Mirroring Alexander duality for Eulerian posets, we show an analogue of Alexander duality for bounded balanced digraphs. For Bruhat graphs of Coxeter groups, an important family of balanced graphs, our theory gives elementary proofs of the existence of the complete \(\mathbf{cd} \)-index and its properties. We also introduce the rising and falling quasisymmetric functions of a labeled acyclic digraph and show they are Hopf algebra homomorphisms mapping balanced digraphs to the Stembridge peak algebra. We conjecture non-negativity of the \(\mathbf{cd} \)-index for acyclic digraphs having a balanced linear edge labeling.

MSC:

06A07 Combinatorics of partially ordered sets
06A11 Algebraic aspects of posets
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
05E05 Symmetric functions and generalizations
16T15 Coalgebras and comodules; corings
20F55 Reflection and Coxeter groups (group-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bayer, M.; Billera, L., Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets, Invent. Math., 79, 143-157 (1985) · Zbl 0543.52007
[2] Bayer, M.; Ehrenborg, R., The toric \(h\)-vectors of partially ordered sets, Trans. Amer. Math. Soc., 352, 4515-4531 (2000) · Zbl 0971.52012
[3] Bayer, MM; Hetyei, G., Flag vectors of Eulerian partially ordered sets, European J. Combin., 22, 5-26 (2001) · Zbl 0971.06004
[4] Bayer, M.; Klapper, A., A new index for polytopes, Discrete Comput. Geom., 6, 33-47 (1991) · Zbl 0761.52009
[5] Bergeron, N.; Mykytiuk, S.; Sottile, F.; van Willigenburg, S., Noncommutative Pieri operators on posets, J. Combin. Theory Ser. A, 91, 84-110 (2000) · Zbl 0969.05064
[6] Bergeron, N.; Sottile, F., Hopf algebra and edge-labeled posets, J. of Alg., 216, 641-651 (1999) · Zbl 0933.05149
[7] Billera, LJ; Brenti, F., Quasisymmetric functions and Kazhdan-Lusztig polynomials, Israel Jour. Math., 184, 317-348 (2011) · Zbl 1269.20030
[8] Billera, LJ; Ehrenborg, R., Monotonicity of the cd-index for polytopes, Math. Z., 233, 421-441 (2000) · Zbl 0966.52014
[9] L. J. Billera, R. Ehrenborg, and M. Readdy, The c-2d-index of oriented matroids, J. Combin. Theory Ser. A80 (1997), 79-105 · Zbl 0886.05043
[10] L. J. Billera, R. Ehrenborg, and M. Readdy, The \({{\bf c}}{{\bf d}}\)-index of zonotopes and arrangements, Mathematical essays in honor of Gian-Carlo Rota (B. Sagan and R. P. Stanley, eds.), Birkhäuser, Boston, 1998, 23-40. · Zbl 0911.52008
[11] Billera, LJ; Liu, N., Noncommutative enumeration in graded posets, J. Algebraic Combin., 12, 7-24 (2000) · Zbl 0971.05005
[12] A. Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc.260 (1980), 159-183 · Zbl 0441.06002
[13] A. Björner and F. Brenti, “Combinatorics of Coxeter groups,” Springer, 2005. · Zbl 1110.05001
[14] A. Björner and M. Wachs, Shellable nonpure complexes and posets. I., Trans. Amer. Math. Soc.348 (1996), 1299-1327 · Zbl 0857.05102
[15] S. A. Blanco, The complete \({{\bf c}}{{\bf d}}\)-index of dihedral and universal Coxeter groups, Electron. J. Combin.18 (2011), no 1, Paper 174, 16pp.
[16] Blanco, SA, Shortest path poset of Bruhat intervals, J. Algebraic Combin., 38, 585-596 (2013) · Zbl 1273.05096
[17] Brenti, F., Lattice paths and Kazhdan-Lusztig polynomials, Jour. Amer. Math. Soc., 11, 229-259 (1998) · Zbl 0904.20033
[18] Brenti, F.; Caselli, F., Peak algebras, paths in the Bruhat graph and Kazhdan-Lusztig polynmials, Adv. in Math, 304, 539-582 (2017) · Zbl 1347.05247
[19] Brenti, F.; Caselli, F.; Marietti, M., Special Matchings and Coxeter groups, Adv. Applied Math, 38, 210-226 (2007) · Zbl 1146.05051
[20] M. J. Dyer, “Hecke algebras and reflections in Coxeter groups,” Doctoral dissertation, University of Sydney, 1987.
[21] Dyer, MJ, Hecke algebras and shellings of Bruhat intervals, Compositio Math., 89, 91-115 (1993) · Zbl 0817.20045
[22] Ehrenborg, R., On posets and Hopf algebras, Adv. Math., 119, 1-25 (1996) · Zbl 0851.16033
[23] Ehrenborg, R., Lifting inequalities for polytopes, Adv. Math., 193, 205-222 (2005) · Zbl 1079.52007
[24] R. Ehrenborg, Inequalities for zonotopes, in MSRI Publication on Combinatorial and Computational Geometry (J.E. Goodman, J. Pach and E. Eelzl, eds.), Cambridge University Press, Cambridge, England, 2005, pp. 277-286. · Zbl 1091.52004
[25] Ehrenborg, R.; Goresky, M.; Readdy, M., Euler flag enumeration of Whitney stratified spaces, Adv. Math., 268, 85-128 (2015) · Zbl 1302.05215
[26] Ehrenborg, R.; Hetyei, G.; Readdy, M., Level Eulerian posets, Graphs and Combinatorics, 29, 857-882 (2013) · Zbl 1317.06004
[27] R. Ehrenborg and K. Karu, Decomposition theorem for the \({{\bf c}}{{\bf d}}\)-index of Gorenstein* posets, J. Algebraic Combin.26 (2007), 225-251 · Zbl 1134.52012
[28] Ehrenborg, R.; Readdy, M., Sheffer posets and \(r\)-signed permutations, Ann. Sci. Math. Québec, 19, 173-196 (1995) · Zbl 0843.06003
[29] R. Ehrenborg and M. Readdy, The r-cubical lattice and a generalization of the cd-index, European J. Combin.17 (1996), 709-725 · Zbl 0861.05003
[30] R. Ehrenborg and M. Readdy, Coproducts and the \({{\bf c}}{{\bf d}}\)-index, J. Algebraic Combin.8 (1998), 273-299 · Zbl 0917.06001
[31] Ehrenborg, R.; Readdy, M., Homology of Newtonian coalgebras, European J. Combin., 23, 919-927 (2002) · Zbl 1034.52010
[32] Ehrenborg, R.; Readdy, M., On the non-existence of an \(R\)-labeling, Order, 28, 437-442 (2011) · Zbl 1232.06002
[33] Ehrenborg, R.; Readdy, M., Manifold arrangements, J. Combin. Theory Ser. A, 125, 214-239 (2014) · Zbl 1295.05267
[34] Ehrenborg, R.; Readdy, M., The Tchebyshev transforms of the first and second kind, Ann. Comb., 14, 211-244 (2010) · Zbl 1230.06002
[35] Ehrenborg, R.; Readdy, M.; Slone, M., Affine and toric hyperplane arrangements, Discrete Comput. Geom., 41, 481-512 (2009) · Zbl 1168.52018
[36] N. J. Y. Fan and L. He, The complete \({{\bf c}}{{\bf d}}\)-index of Boolean lattices, Electron. J. Combin.22 (2015), no. 2, Paper 2.45, 18 pp.
[37] N. J. Y. Fan and L. He, On the non-negativity of the complete \({{\bf c}}{{\bf d}}\)-index, Discrete Math.338 (2015), 2037-2041 · Zbl 1314.05215
[38] Fox, NB, A lattice path interpretation of the diamond product, Ann. Comb., 20, 569-586 (2016) · Zbl 1390.06002
[39] Joni, SA; Rota, G-C, Coalgebras and bialgebras in combinatorics, Stud. Appl. Math., 61, 93-139 (1979) · Zbl 0471.05020
[40] Karu, K., Hard Lefschetz theorem for nonrational polytopes, Invent. Math., 157, 419-447 (2004) · Zbl 1077.14071
[41] Karu, K., The \(cd\)-index of fans and posets, Compos. Math., 142, 701-718 (2006) · Zbl 1103.14029
[42] Karu, K., On the complete \({\bf cd}\)-index of a Bruhat interval, J. Algebraic Combin., 38, 27-541 (2013) · Zbl 1291.20041
[43] Kazhdan, D.; Lusztig, G., Representations of Coxeter groups and Hecke algebras, Invent. Math, 53, 165-184 (1979) · Zbl 0499.20035
[44] Kazhdan, D.; Lusztig, G., Schubert varieties and Poincaré duality, Proc. Sympos. Pure Math., 34, 185-203 (1980) · Zbl 0461.14015
[45] Malvenuto, C.; Reutenauer, C., Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, 177, 967-982 (1995) · Zbl 0838.05100
[46] Morel, S., Note sur les polynômes de Kazhdan-Lusztig, Math. Z, 268, 593-600 (2011) · Zbl 1233.20005
[47] N. Reading, The \(cd\)-index of Bruhat intervals, Electron. J. Combin.11 (2004), no. 1, Research Paper 74, 25 pp. · Zbl 1067.20050
[48] M. Slone, “Homological combinatorics and extensions of the \({\bf cd}\)-index,” Doctoral dissertation, University of Kentucky, 2008.
[49] Stanley, RP, Flag \(f\)-vectors and the \(cd\)-index, Math. Z., 216, 483-499 (1994) · Zbl 0805.06003
[50] R. P. Stanley, “Enumerative combinatorics. Volume 1. Second edition.,” Cambridge University Press, Cambridge, 2012. · Zbl 1247.05003
[51] R. P. Stanley, Flag \(f\)-vectors and the \(cd\)-index, Math. Z.216 (1994), 483-499 · Zbl 0805.06003
[52] Stembridge, J., Enriched \(P\)-partitions, Trans. Amer. Math. Soc., 349, 763-788 (1997) · Zbl 0863.06005
[53] M. Sweedler, “Hopf Algebras,” Benjamin, New York, 1969. · Zbl 0194.32901
[54] Verma, D-N, Möbius inversion for the Bruhat order on a Weyl group, Ann. Sci. École Norm. Sup., 4, 393-398 (1971) · Zbl 0236.20035
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.