Combinatorics of diagrams of permutations

Abstract

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östrand by showing that under a certain pattern condition the Poincaré 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.

v3: 29 pages, 11 figures. Addressed minor suggestions from referees, typos fixed, and updated references. v2: 29 pages, 11 figures. Part of the proof of Theorem 2.1 has been replaced by an elegant argument by Axel Hultman, which is now included as Appendix A. v1: 31 pages, 11 figures

References in corpus (2)

• Total positivity, Grassmannians, and networks
• Consequences of the Lakshmibai-Sandhya Theorem: the ubiquity of permutation patterns in Schubert calculus and related geometry

Cited by in corpus (4)

• LLT polynomials, chromatic quasisymmetric functions and graphs with cycles
• Rationally smooth Schubert varieties and inversion hyperplane arrangements
• Rook theory of the finite general linear group
• Inversion arrangements and the weak Bruhat order