On comparability of bigrassmannian permutations. (English) Zbl 1404.05006
Summary: Let \(\mathfrak S_n\) and \(\mathfrak B_n\) denote the respective sets of ordinary and bigrassmannian (BG) permutations of order \(n\), and let \((\mathfrak S_n,\leq)\) denote the Bruhat ordering permutation poset. We study the restricted poset \((\mathfrak B_n,\leq)\), first providing a simple criterion for comparability. This criterion is used to show that that the poset is connected, to enumerate the saturated chains between elements, and to enumerate the number of maximal elements below \(r\) fixed elements. It also quickly produces formulas for \(\beta(\omega)\) (\(\alpha(\omega)\), respectively), the number of BG permutations weakly below (weakly above, respectively) a fixed \(\omega\in\mathfrak B_n\), and is used to compute the Möbius function on any interval in \(\mathfrak B_n\).
We then turn to a probabilistic study of \(\beta=\beta(\omega)\) (\(\alpha=\alpha(\omega)\) respectively) for the uniformly random \(\omega\in\mathfrak B_n\). We show that \(\alpha\) and \(\beta\) are equidistributed, and that \(\beta\) is of the same order as its expectation with high probability, but fails to concentrate about its mean. This latter fact derives from the limiting distribution of \(\beta/n^3\).
We also compute the probability that randomly chosen BG permutations form a 2- or 3-element multichain.
We then turn to a probabilistic study of \(\beta=\beta(\omega)\) (\(\alpha=\alpha(\omega)\) respectively) for the uniformly random \(\omega\in\mathfrak B_n\). We show that \(\alpha\) and \(\beta\) are equidistributed, and that \(\beta\) is of the same order as its expectation with high probability, but fails to concentrate about its mean. This latter fact derives from the limiting distribution of \(\beta/n^3\).
We also compute the probability that randomly chosen BG permutations form a 2- or 3-element multichain.
MSC:
| 05A05 | Permutations, words, matrices |
Software:
ROBBINSReferences:
| [1] | G. Andrews, R. Askey and R. Roy, Special functions, Encyclopedia of Mathematics and its Applications 71, Cambridge University Press, Cambridge, 1999. |
| [2] | L. Balcza, Sum of lengths of inversions in permutations, Discrete Math. 111 (1993), 41-48. · Zbl 0785.05008 |
| [3] | A. Bernini and L. Ferrari, Vincular pattern posets and the M¨obius function of the quasi-consecutive pattern poset, Ann. Combin. 21 (2017), 519-534. · Zbl 1375.05005 |
| [4] | A Bernini, L. Ferrari and E. Steingr´ımsson, The M¨obius function of the consecutive pattern poset, Electron. J. Combin. 18 (2011), #P146. · Zbl 1227.05007 |
| [5] | G. Birkhoff, Rings of sets, Duke Math. J. 3(3) (1937), 443-454. · Zbl 0017.19403 |
| [6] | A. Bj¨orner and F. Brenti, An improved tableau criterion for Bruhat order, Electron. J. Combin. 3 (1996), #R22. · Zbl 0884.05096 |
| [7] | A. Bj¨orner and F. Brenti, Combinatorics of Coxeter Groups, Springer, New York, 2005. · Zbl 1110.05001 |
| [8] | A. Bj¨orner, Orderings of Coxeter Groups, in Combinatorics and Algebra (C. Greene, ed.), Vol. 34 of Contemp. Math., American Mathematical Society, Providence, RI, 1984 pp. 175-195. · Zbl 0594.20029 |
| [9] | A. Bj¨orner, The M¨obius function of factor order, Theor. Comput. Sci. 117 (1993), 91-98. · Zbl 0782.68093 |
| [10] | D. M. Bressoud, Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture, MAA, Cambridge University Press, Cambridge, 1999. · Zbl 0944.05001 |
| [11] | R. Brualdi and M. Schroeder, Alternating sign matrices and their Bruhat order, Discrete Math. 340 (2017), 1996-2019. · Zbl 1366.15024 |
| [12] | V. Deodhar, Some characterizations of Bruhat ordering on a Coxeter group and determination of the relative M¨obius function, Inventiones Math. 39 (1977), · Zbl 0333.20041 |
| [13] | C. Ehresmann, Sur la topologie de certains espaces homog´enes, Ann. of Math. (2) 35 (1934), 396-443. · JFM 60.1223.05 |
| [14] | J. Engbers and A. Hammett, Trivial meet and join within the lattice of monotone triangles, Electron. J. Combin. 21(3) (2014), #P3.13. · Zbl 1325.06005 |
| [15] | W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1 (3rd Ed.), Wiley, New York, 2008. · Zbl 0158.34902 |
| [16] | P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009. · Zbl 1165.05001 |
| [17] | M. Geck and S. Kim, Bases for the Bruhat-Chevalley order on all finite Coxeter groups, J. Algebra 197 (1997), 278-310. · Zbl 0977.20033 |
| [18] | A. Hammett, On comparibility of random permutations, Ph. D. Thesis, The Ohio State University, 2007. |
| [19] | A. Hammett and B. Pittel, How often are two permutations comparable? Trans. Amer. Math. Soc. 360(9) (2008), 4541-4568. · Zbl 1154.05002 |
| [20] | M. Kobayashi, Bijection between bigrassmannian permutations maximal below a permutation and its essential set, Electron. J. Combin. 17 (2010) #N27. · Zbl 1188.05002 |
| [21] | M. Kobayashi, Enumeration of bigrassmannian permutations below a permutation in Bruhat order, Order 28(1) (2011), 131-137. · Zbl 1211.05008 |
| [22] | M. Kobayashi, 3412,4231 patterns produce singular points of essential sets, Saitama Math. J. 28 (2011), 13-23. · Zbl 1270.20039 |
| [23] | M. Kobayashi, More combinatorics of Fulton’s essential set, Int. Math. Forum 8 (2013), 1735-1760. · Zbl 1301.05012 |
| [24] | A. Lascoux and M. P. Sch¨utzenberger, Treillis et bases des groupes de Coxeter, Electron. J. Combin. 3 (1996), #R27. |
| [25] | B. Pittel, Random set partitions: asymptotics of subset counts, J. Comb. Theory Ser. A 79 (1997), 326-359. · Zbl 0895.60008 |
| [26] | B. Pittel, Confirming two conjectures about the integer partitions, J. Comb. Theory Ser. A 88 (1999), 123-135. · Zbl 0937.05008 |
| [27] | B. Pittel, Asymptotic joint distribution of the extremities of a random Young diagram and enumeration of graphical partitions, Preprint (2016), http:// arxiv.org/abs/1603.00923. · Zbl 1390.05016 |
| [28] | J. Propp, The many faces of alternating-sign matrices, Discrete Math. Theor. Comput. Sci. Proc. AA (DM-CCG) (2001), 43-58. · Zbl 0990.05020 |
| [29] | N. Reading, Order dimension, strong Bruhat order, and lattice properties for posets, Order 19 (2002), 73-100. · Zbl 1007.05097 |
| [30] | V. Reiner, A. Woo and A. Yong, Presenting the cohomology of a Schubert variety, Trans. Amer. Math. Soc. 363(1) (2011), 521-543. · Zbl 1213.14091 |
| [31] | R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997. · Zbl 0889.05001 |
| [32] | R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999. · Zbl 0928.05001 |
| [33] | J. R. Stembridge, On the fully commutative elements of Coxeter groups, J. Algebraic Combin. 5(4) (1996), 353-385. · Zbl 0864.20025 |
| [34] | J. R. Stembridge, The enumeration of fully commutative elements of Coxeter groups, J. Algebraic Combin. 7(3) (1998), 291-320. · Zbl 0897.05087 |
| [35] | J. R. Stembridge, Minuscule elements of Weyl groups, J. Algebra 235(2) (2001), 722-743. · Zbl 0973.17034 |
| [36] | A. Weigandt and A. Yong, The Prism tableau model for Schubert polynomials, J. Combin. Theory Ser. A 154 (2018), 551-582. · Zbl 1373.05219 |
| [37] | R. Willenbring, The M¨obius function of generalized factor order, Discrete Math. 313 (2013), 330-347. · Zbl 1259.05009 |
| [38] | D. Zeilberger, Proof of the alternating sign matrix conjecture, Electron. · Zbl 0858.05023 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
