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

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 $n \dotsc 21$ 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 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.

Keywords

reduced decompositions, permutations, diameter, pattern avoidance, braid classes, commutation classes

2010 Mathematics Subject Classification

Primary 05A05. Secondary 05C12, 20F55.

Full Text (PDF format)

Received 17 February 2021

Accepted 28 January 2022

Published 19 August 2022