The number of spanning trees of the Bruhat graph

Richard Ehrenborg

doi:10.1016/j.aam.2020.102150

The number of spanning trees of the Bruhat graph

Richard Ehrenborg

Mathematics

Research output: Contribution to journal › Article › peer-review

14 Scopus citations

Abstract

We provide an explicit product formula for the number of spanning trees of the Bruhat graph of the symmetric group, that is, the graph where two permutations π and σ are connected with an edge if πσ⁻¹ is a transposition. We also give the number of spanning trees for the graph where the two permutations are connected if πσ⁻¹ is an r-cycle for r even. For r odd we obtain the similar result for the alternating group.

Original language	English
Article number	102150
Journal	Advances in Applied Mathematics
Volume	125
DOIs	https://doi.org/10.1016/j.aam.2020.102150
State	Published - Apr 2021

Bibliographical note

Publisher Copyright:
© 2020 Elsevier Inc.

Funding

The author thanks Theodore Ehrenborg and Huafei Yan for suggestions that improved the exposition of this note. This work was partially supported by a grant from the Simons Foundation (# 429370 to Richard Ehrenborg). The author thanks Theodore Ehrenborg and Huafei Yan for suggestions that improved the exposition of this note. This work was partially supported by a grant from the Simons Foundation (#429370 to Richard Ehrenborg).

Funders	Funder number
Theodore Ehrenborg and Huafei Yan
Simons Foundation	429370

Keywords

Bruhat graph
Partition
Spanning tree
Symmetric group character

ASJC Scopus subject areas

Applied Mathematics

Access to Document

10.1016/j.aam.2020.102150

Cite this

@article{22dff064c6c74916a24ad81e5ab41964,

title = "The number of spanning trees of the Bruhat graph",

abstract = "We provide an explicit product formula for the number of spanning trees of the Bruhat graph of the symmetric group, that is, the graph where two permutations π and σ are connected with an edge if πσ−1 is a transposition. We also give the number of spanning trees for the graph where the two permutations are connected if πσ−1 is an r-cycle for r even. For r odd we obtain the similar result for the alternating group.",

keywords = "Bruhat graph, Partition, Spanning tree, Symmetric group character",

author = "Richard Ehrenborg",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier Inc.",

year = "2021",

month = apr,

doi = "10.1016/j.aam.2020.102150",

language = "English",

volume = "125",

}

TY - JOUR

T1 - The number of spanning trees of the Bruhat graph

AU - Ehrenborg, Richard

PY - 2021/4

Y1 - 2021/4

N2 - We provide an explicit product formula for the number of spanning trees of the Bruhat graph of the symmetric group, that is, the graph where two permutations π and σ are connected with an edge if πσ−1 is a transposition. We also give the number of spanning trees for the graph where the two permutations are connected if πσ−1 is an r-cycle for r even. For r odd we obtain the similar result for the alternating group.

AB - We provide an explicit product formula for the number of spanning trees of the Bruhat graph of the symmetric group, that is, the graph where two permutations π and σ are connected with an edge if πσ−1 is a transposition. We also give the number of spanning trees for the graph where the two permutations are connected if πσ−1 is an r-cycle for r even. For r odd we obtain the similar result for the alternating group.

KW - Bruhat graph

KW - Partition

KW - Spanning tree

KW - Symmetric group character

UR - https://www.scopus.com/pages/publications/85098775714

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

U2 - 10.1016/j.aam.2020.102150

DO - 10.1016/j.aam.2020.102150

M3 - Article

AN - SCOPUS:85098775714

SN - 0196-8858

VL - 125

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

M1 - 102150

ER -

The number of spanning trees of the Bruhat graph

Abstract

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this