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

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

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 - http://www.scopus.com/inward/record.url?scp=85098775714&partnerID=8YFLogxK

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

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

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this