How often are two permutations comparable?
HTML articles powered by AMS MathViewer
- by Adam Hammett and Boris Pittel PDF
- Trans. Amer. Math. Soc. 360 (2008), 4541-4568 Request permission
Abstract:
Two permutations of $\left [ n \right ]$ are comparable in the Bruhat order if one is closer, in a natural way, to the identity permutation, $1 2 \cdots n$, than the other. We show that the number of comparable pairs is of order $\left (n!\right )^2/n^2$ at most, and $\left (n!\right )^2\left (0.708\right )^n$ at least. For the related weak order, the corresponding bounds are $\left (n!\right )^2\left (0.362\right )^n$ and $\left (n!\right )^2\prod _{i=1}^n \left (H\left (i\right )/i\right )$, where $H\left (i\right ):=\sum _{j=1}^i 1/j$. In light of numerical experiments, we conjecture that for each order the upper bound is qualitatively close to the actual number of comparable pairs.References
- C. Berge, Principles of combinatorics, Mathematics in Science and Engineering, Vol. 72, Academic Press, New York-London, 1971. Translated from the French. MR 0270922
- Patrick Billingsley, Probability and measure, 3rd ed., Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1995. A Wiley-Interscience Publication. MR 1324786
- Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, vol. 231, Springer, New York, 2005. MR 2133266
- Anders Björner and Francesco Brenti, An improved tableau criterion for Bruhat order, Electron. J. Combin. 3 (1996), no. 1, Research Paper 22, approx. 5. MR 1399399
- Anders Björner and Michelle L. Wachs, $q$-hook length formulas for forests, J. Combin. Theory Ser. A 52 (1989), no. 2, 165–187. MR 1022316, DOI 10.1016/0097-3165(89)90028-9
- Anders Björner, Orderings of Coxeter groups, Combinatorics and algebra (Boulder, Colo., 1983) Contemp. Math., vol. 34, Amer. Math. Soc., Providence, RI, 1984, pp. 175–195. MR 777701, DOI 10.1090/conm/034/777701
- M. Bóna, Personal communication about an early preprint, August 2006.
- Miklós Bóna, Combinatorics of permutations, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2004. With a foreword by Richard Stanley. MR 2078910, DOI 10.1201/9780203494370
- Graham R. Brightwell and Prasad Tetali, The number of linear extensions of the Boolean lattice, Order 20 (2003), no. 4, 333–345 (2004). MR 2079149, DOI 10.1023/B:ORDE.0000034596.50352.f7
- Vinay V. Deodhar, Some characterizations of Bruhat ordering on a Coxeter group and determination of the relative Möbius function, Invent. Math. 39 (1977), no. 2, 187–198. MR 435249, DOI 10.1007/BF01390109
- Brian Drake, Sean Gerrish, and Mark Skandera, Two new criteria for comparison in the Bruhat order, Electron. J. Combin. 11 (2004), no. 1, Note 6, 4. MR 2056088
- Charles Ehresmann, Sur la topologie de certains espaces homogènes, Ann. of Math. (2) 35 (1934), no. 2, 396–443 (French). MR 1503170, DOI 10.2307/1968440
- S. Fomin, Personal communication at the Michigan University Combinatorics Seminar, April 2005.
- William Fulton, Young tableaux, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, Cambridge, 1997. With applications to representation theory and geometry. MR 1464693
- James E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics, vol. 29, Cambridge University Press, Cambridge, 1990. MR 1066460, DOI 10.1017/CBO9780511623646
- Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847, DOI 10.1002/9781118032718
- Ji Chang Sha and D. J. Kleitman, The number of linear extensions of subset ordering, Discrete Math. 63 (1987), no. 2-3, 271–278. Special issue: ordered sets (Oberwolfach, 1985). MR 885505, DOI 10.1016/0012-365X(87)90016-1
- Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching. MR 0445948
- Alain Lascoux and Marcel-Paul Schützenberger, Treillis et bases des groupes de Coxeter, Electron. J. Combin. 3 (1996), no. 2, Research paper 27, approx. 35 (French). MR 1395667
- V. A. Vatutin and V. G. Mikhaĭlov, Limit theorems for the number of empty cells in an equiprobable scheme for the distribution of particles by groups, Teor. Veroyatnost. i Primenen. 27 (1982), no. 4, 684–692 (Russian, with English summary). MR 681461
- Boris Pittel, Confirming two conjectures about the integer partitions, J. Combin. Theory Ser. A 88 (1999), no. 1, 123–135. MR 1713480, DOI 10.1006/jcta.1999.2986
- Boris Pittel, Random set partitions: asymptotics of subset counts, J. Combin. Theory Ser. A 79 (1997), no. 2, 326–359. MR 1462562, DOI 10.1006/jcta.1997.2791
- G. Pólya, G. Szegö, Problems and Theorems in Analysis, Springer, New York, 1976.
- Richard P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota; Corrected reprint of the 1986 original. MR 1442260, DOI 10.1017/CBO9780511805967
- Lajos Takács, Combinatorial methods in the theory of stochastic processes, John Wiley & Sons, Inc., New York-London-Sydney, 1967. MR 0217858
Additional Information
- Adam Hammett
- Affiliation: Department of Mathematics, The Ohio State University, 231 W. 18th Avenue, Columbus, Ohio 43210
- Email: hammett@math.ohio-state.edu
- Boris Pittel
- Affiliation: Department of Mathematics, The Ohio State University, 231 W. 18th Avenue, Columbus, Ohio 43210
- Email: bgp@math.ohio-state.edu
- Received by editor(s): January 31, 2006
- Published electronically: April 4, 2008
- Additional Notes: The first author was supported in part by NSF grant DMS-0104104.
The second author was supported in part by NSF grants DMS-0104104 and DMS-0406024. - © Copyright 2008 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 360 (2008), 4541-4568
- MSC (2000): Primary 05A05, 05A16, 06A07, 60C05; Secondary 20B99
- DOI: https://doi.org/10.1090/S0002-9947-08-04478-4
- MathSciNet review: 2403696