Balanced and Bruhat Graphs

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)587-617
Number of pages31
JournalAnnals of Combinatorics
Volume24
Issue number3
DOIs
StatePublished - Sep 1 2020

Bibliographical note

Funding Information:
The authors thank the referee for helpful comments. The first author was partially supported by National Science Foundation Grant 0902063. This work was partially supported by grants from the Simons Foundation (#429370 to Richard Ehrenborg; #206001 and #422467 to Margaret Readdy). Both authors would like to thank the Princeton University Mathematics Department for its hospitality and support during the academic year 2014–2015, and the Institute for Advanced Study for hosting a research visit in Summer 2019.

Funding Information:
The authors thank the referee for helpful comments. The first author was partially supported by National Science Foundation Grant 0902063. This work was partially supported by grants from the Simons Foundation (#429370 to Richard Ehrenborg; #206001 and #422467 to Margaret Readdy). Both authors would like to thank the Princeton University Mathematics Department for its hospitality and support during the academic year 2014?2015, and the Institute for Advanced Study for hosting a research visit in Summer 2019.

Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

Keywords

  • Alexander duality
  • Balanced digraph
  • Bruhat graph
  • Eulerian poset
  • Quasisymmetric function
  • R-labeling
  • cd-Index

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Balanced and Bruhat Graphs'. Together they form a unique fingerprint.

Cite this