Combinatorics of diagrams of permutations

Joel Brewster Lewis, Alejandro H. Morales

Published 2014-05-07, updated 2015-08-28Version 3

There are numerous combinatorial objects associated to a Grassmannian permutation $w_\lambda$ that index cells of the totally nonnegative Grassmannian. We study several of these objects and their $q$-analogues in the case of permutations $w$ that are not necessarily Grassmannian. We give two main results: first, we show that certain acyclic orientations, rook placements avoiding a diagram of $w$, and fillings of a diagram of $w$ are equinumerous for all permutations $w$. Second, we give a $q$-analogue of a result of Hultman-Linusson-Shareshian-Sj\"ostrand by showing that under a certain pattern condition the Poincar\'e polynomial for the Bruhat interval of $w$ essentially counts invertible matrices avoiding a diagram of $w$ over a finite field. In addition to our main results, we include at the end a number of open questions.