On Degrees in the Hasse Diagram of the Strong Bruhat Order

2005/05/02 by Ron M. Adin, Adin, Ron M., Yuval Roichman +1 · 1 citation
Mathematics · #20B30 (Primary) 05C35 (Secondary) #Advanced Algebra and Geometry #Advanced Combinatorial Mathematics #Algebraic structures and combinatorial models #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C35 #msc:20B30

paper · pdf · doi:10.48550/arxiv.math/0505020

14 pages, minor corrections; to appear in Sém. Lothar. Combin

openalex publication_date 2005/05/02 · arxiv created 2006/03/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a permutation π in the symmetric group S_n let the \it total degree be its valency in the Hasse diagram of the strong Bruhat order on S_n, and let the \it down degree be the number of permutations which are covered by π in the strong Bruhat order. The maxima of the total degree and the down degree and their values at a random permutation are computed. Proofs involve variants of a classical theorem of Turán from extremal graph theory.

Citations

• Structure of the Malvenuto-Reutenauer Hopf algebra of permutations (Extended Abstract)

Cited by

• Forest-Like Permutations

Related

• Maximal Degree in the Strong Bruhat Order of Bn
• Inversion arrangements and the weak Bruhat order
• A window to the Bruhat order on the affine symmetric group
• Ricci curvature of Bruhat orders
• Higher Bruhat Orders in Type B