Journal of Combinatorics

Volume 11 (2020)

Number 2

Properties of the Edelman–Greene bijection

Pages: 249 – 273

DOI: https://dx.doi.org/10.4310/JOC.2020.v11.n2.a2

Authors

Svante Linusson (Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden)

Samu Potka (Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden)

Abstract

Edelman and Greene constructed a bijective correspondence between reduced words of the reverse permutation and standard Young tableaux. We prove that for any reduced word the shape of the region of the insertion tableau containing the smallest possible entries evolves exactly as the upper-left component of the permutation’s (Rothe) diagram. Properties of the Edelman–Greene bijection restricted to 132-avoiding and 2143-avoiding permutations are presented. We also consider the Edelman–Greene bijection applied to non-reduced words.

Keywords

Edelman–Greene correspondence, reduced words, Young tableaux, random sorting networks

The authors were supported by the Swedish Research Council, grant 621-2014-4780.

Received 3 May 2018

Published 14 January 2020