Balanced and Bruhat Graphs
- PDF / 695,087 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 263 Views
Annals of Combinatorics
Balanced and Bruhat Graphs Richard Ehrenborg and Margaret Readdy Abstract. 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) 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 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 cd-index for acyclic digraphs having a balanced linear edge labeling. Mathematics Subject Classification. Primary 06A11, 52B05; Secondary 05E05, 06A08, 16T15, 20F55. Keywords. Alexander duality, Balanced digraph, Bruhat graph, cd-Index, Eulerian poset, Quasisymmetric function, R-labeling.
1. Introduction The cd-index is an important invariant for studying face incidence data of polytopes, and more generally, chain enumeration of Eulerian posets. It is a non-commutative polynomial which removes all the linear redundancies which hold among the flag vector entries [4] as described by the generalized Dehn– Sommerville relations [1]. Ehrenborg and Readdy’s discovery of the inherent coalgebraic structure of the cd-index and the techniques developed in [30] have been applied to settle many fundamental problems, including giving compact proofs of old results [1,10], transparent techniques to compute flag vectors of oriented matroids [9], explicit formulas for the toric h-vector, versions of Stanley’s Gorenstein* conjecture [8,10] leading up to a proof of the conjecture
588
R. Ehrenborg, M. Readdy
itself [27], new non-trivial inequalities among the face incidence data of polytopes [23,24] and extending classical subspace arrangement results to other manifolds [25,35]. There are two new developments in this area. The first is work of Ehrenborg, Goresky and Readdy, who extend flag vector enumeration ideas to Whitney stratified spaces and quasi-graded posets [25,33]. The very notion of enumeration is replaced with the topologically meaningful Euler-enumeration in the case of Whitney stratified spaces, and weighted zeta functions in the case of quasi-graded posets. The Eulerian condition becomes a natural condition involving the Euler characteristic and weighted zeta function, respectively. Unlike the case of polytopes and regular decompositions of spheres, the coefficients of the cd-index can be negative, expanding the nature of questions in the field. The second development is Billera and Brenti’s work on the “complete” cd-index, a nonhomogeneous extension of the cd-ind
Data Loading...
