Balanced and Bruhat Graphs

Richard Ehrenborg; Margaret Readdy

doi:10.1007/s00026-020-00510-7

Balanced and Bruhat Graphs

Richard Ehrenborg, Margaret Readdy

Mathematics

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	587-617
Number of pages	31
Journal	Annals of Combinatorics
Volume	24
Issue number	3
DOIs	https://doi.org/10.1007/s00026-020-00510-7
State	Published - Sep 1 2020

Bibliographical note

Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

Funding

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. 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.

Funders	Funder number
Princeton University Mathematics Department
National Science Foundation (NSF)	0902063
Simons Foundation	422467, 206001, 429370

Keywords

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

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00026-020-00510-7

Cite this

@article{b9b03a46dfd94465965c4e582dc71499,

title = "Balanced and Bruhat Graphs",

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.",

keywords = "Alexander duality, Balanced digraph, Bruhat graph, Eulerian poset, Quasisymmetric function, R-labeling, cd-Index",

author = "Richard Ehrenborg and Margaret Readdy",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.",

year = "2020",

month = sep,

day = "1",

doi = "10.1007/s00026-020-00510-7",

language = "English",

volume = "24",

pages = "587--617",

number = "3",

}

TY - JOUR

T1 - Balanced and Bruhat Graphs

AU - Ehrenborg, Richard

AU - Readdy, Margaret

PY - 2020/9/1

Y1 - 2020/9/1

N2 - 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.

AB - 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.

KW - Alexander duality

KW - Balanced digraph

KW - Bruhat graph

KW - Eulerian poset

KW - Quasisymmetric function

KW - R-labeling

KW - cd-Index

UR - http://www.scopus.com/inward/record.url?scp=85089993430&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85089993430&partnerID=8YFLogxK

U2 - 10.1007/s00026-020-00510-7

DO - 10.1007/s00026-020-00510-7

M3 - Article

AN - SCOPUS:85089993430

SN - 0218-0006

VL - 24

SP - 587

EP - 617

JO - Annals of Combinatorics

JF - Annals of Combinatorics

IS - 3

ER -

Balanced and Bruhat Graphs

Abstract

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this