Diameters of graphs on reduced words of 12 and 21-inflations

DOI10.4310/JOC.2023.V14.N1.A4MaRDI QIDQ2167563zbMATH OpenOpenAlexFDO

Authors Samantha Dahlberg, Young Hwan Kim

Publication date 25 August 2022

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.15758

zbMATH Keywords

braid classescommutation classesdiameterpattern avoidancepermutationsreduced decompositions

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Distance in graphs (05C12) Reflection and Coxeter groups (group-theoretic aspects) (20F55)

Abstract: It is a classical result that any permutation in the symmetric group can be generated by a sequence of adjacent transpositions. The sequences of minimal length are called reduced words, and in this paper we study the graphs of these reduced words, with edges determined by relations in the underlying Coxeter group. Recently, the diameter has been calculated for the longest permutation $nldots21$ by Reiner and Roichman as well as Assaf. In this paper we find inductive formulas for the diameter of the graphs of 12-inflations and many 21-inflations. These results extend to the associated graphs on commutation and long braid classes. Also, these results give a recursive formula for the diameter of the longest permutation, which matches that of Reiner, Roichman and Assaf. Lastly, We make progress on conjectured bounds of the diameter by Reiner and Roichman, which are based on the underlying hyperplane arrangement, and find families of permutations that achieve the upper bound and lower bound of the conjecture. In particular permutations that avoid 312 or 231 have graphs that achieve the upper bound.

Recommendations

• Diameters of graphs of reduced words and rank-two root subsystems
• Diameter of graphs of reduced words and galleries.
• scientific article; zbMATH DE number 1420446
• scientific article; zbMATH DE number 1375161
• Reduced graphs of diameter two
• On diameters of 2-regular graphs
• On the diameter of Kronecker graphs
• On -commuting graphs and their diameters
• Diameters of finite upper half plane graphs
• On the diameter of Kneser graphs

Cited in

(8)

• Diameter of the commutation classes graph of a permutation
• The commutation graph for the longest signed permutation
• Commutation classes of the reduced words for the longest element of \(\mathfrak{S}_{n}\)
• Extending a word property for twisted Coxeter systems
• Diameter of graphs of reduced words and galleries.
• Diameters of graphs of reduced words and rank-two root subsystems
• Diameter of a commutation class on reduced words
• On graphs of sets of reduced words

This page was built for publication: Diameters of graphs on reduced words of \(12\) and \(21\)-inflations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2167563)