Balanced and Bruhat Graphs

Richard Ehrenborg; Margaret Readdy

doi:10.1007/s00026-020-00510-7

Balanced and Bruhat Graphs

Mathematics

Producción científica: Article › revisión exhaustiva

Resumen

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.

Idioma original	English
Páginas (desde-hasta)	587-617
Número de páginas	31
Publicación	Annals of Combinatorics
Volumen	24
N.º	3
DOI	https://doi.org/10.1007/s00026-020-00510-7
Estado	Published - sept 1 2020

Nota bibliográfica

Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

Financiación

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.

Financiadores	Número del financiador
Princeton University Mathematics Department
National Science Foundation (NSF)	0902063
Simons Foundation	422467, 206001, 429370

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Acceder al documento

10.1007/s00026-020-00510-7

Otros archivos y enlaces

Citar esto

@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 - https://www.scopus.com/pages/publications/85089993430

UR - https://www.scopus.com/pages/publications/85089993430#tab=citedBy

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

Resumen

Nota bibliográfica

Financiación

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto