The number of spanning trees of the Bruhat graph

Research output: Contribution to journalArticlepeer-review

10 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 πσ−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.

Original languageEnglish
Article number102150
JournalAdvances in Applied Mathematics
Volume125
DOIs
StatePublished - Apr 2021

Bibliographical note

Publisher Copyright:
© 2020 Elsevier Inc.

Keywords

  • Bruhat graph
  • Partition
  • Spanning tree
  • Symmetric group character

ASJC Scopus subject areas

  • Applied Mathematics

Fingerprint

Dive into the research topics of 'The number of spanning trees of the Bruhat graph'. Together they form a unique fingerprint.

Cite this