Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

How often are two permutations comparable?


Authors: Adam Hammett and Boris Pittel
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
Published electronically: April 4, 2008
MathSciNet review: 2403696
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] C. BERGE, Principles of Combinatorics, Vol. 72 of Mathematics in Science and Engineering: A Series of Monographs and Textbooks, Academic Press, Inc., New York, 1971. MR 0270922 (42:5805)
  • [2] P. BILLINGSLEY, Probability and Measure, 3$ ^{rd}$ ed., John Wiley & Sons, Inc., New York, 1995. MR 1324786 (95k:60001)
  • [3] A. BJÖRNER, F. BRENTI, Combinatorics of Coxeter Groups, Springer, New York, 2005. MR 2133266 (2006d:05001)
  • [4] A. BJÖRNER, F. BRENTI, An Improved Tableau Criterion for Bruhat Order, Electron. J. Combin. 3 (1996), #R22, 5 pp. (electronic). MR 1399399 (97c:05160)
  • [5] A. BJÖRNER, M. WACHS, $ q$-Hook Length Formulas for Forests, Journal of Combinatorial Theory, Series A 52 (1989), pp. 165-187. MR 1022316 (91e:05013)
  • [6] A. BJÖRNER, 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. MR 777701 (86i:05024)
  • [7] M. B´ONA, Personal communication about an early preprint, August 2006.
  • [8] M. B´ONA, Combinatorics of Permutations, Discrete Mathematics and its Applications, Chapman & Hall/CRC, Boca Raton, 2004. MR 2078910 (2005f:05001)
  • [9] G. BRIGHTWELL, P. TETALI, The Number of Linear Extensions of the Boolean Lattice, Order 20 (2003), pp. 333-345. MR 2079149 (2005d:06002)
  • [10] V. DEODHAR, Some Characterizations of Bruhat Ordering on a Coxeter Group and Determination of the Relative Möbius Function, Inventiones Math. 39 (1977), pp. 187-198. MR 0435249 (55:8209)
  • [11] B. DRAKE, S. GERRISH, M. SKANDERA, Two New Criteria for Comparison in the Bruhat Order, Electron. J. Combin. 11 (2004), #N6, 4 pp. (electronic). MR 2056088
  • [12] C. EHRESMANN, Sur la topologie de certains espaces homogènes, Ann. Math. 35 (1934), pp. 396-443. MR 1503170
  • [13] S. FOMIN, Personal communication at the Michigan University Combinatorics Seminar, April 2005.
  • [14] W. FULTON, Young Tableaux: With Applications to Representation Theory and Geometry, Vol. 35 of London Mathematical Society Student Texts, Cambridge University Press, New York, 1997. MR 1464693 (99f:05119)
  • [15] J. E. HUMPHREYS, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, No. 29, Cambridge University Press, Cambridge, 1990. MR 1066460 (92h:20002)
  • [16] S. JANSON, T. ŁUCZAK, A. RUCIŃSKI, Random Graphs, John Wiley & Sons, Inc., New York, 2000. MR 1782847 (2001k:05180)
  • [17] D. KLEITMAN, J. SHA, The Number of Linear Extensions of Subset Ordering, Discrete Math. 63 (1987), pp. 271-279. MR 885505 (88c:05016)
  • [18] D. KNUTH, Sorting and Searching: The Art of Computer Programming, Vol. III, Addison-Wesley Publishing Company, Inc., Reading, MA, 1973. MR 0445948 (56:4281)
  • [19] A. LASCOUX, M. P. SCHÜTZENBERGER, Treillis et bases des groupes de Coxeter, Electron. J. Combin. 3 (1996), #R27, 35 pp. (electronic). MR 1395667 (98c:05168)
  • [20] V. G. MIKHAILOV, V. A. VATUTIN, Limit Theorems for the Number of Empty Cells in an Equiprobable Scheme for Group Allocation of Particles, Teor. Veroyatnost. i Primenen. 27 (1982), pp. 684-692 (Russian); Theor. Probab. Appl. 27, pp. 734-743 (English transl.). MR 681461 (84c:60020)
  • [21] B. PITTEL, Confirming Two Conjectures About the Integer Partitions, Journal of Combinatorial Theory, Series A 88 (1999), pp. 123-135. MR 1713480 (2000k:11114)
  • [22] B. PITTEL, Random Set Partitions: Asymptotics of Subset Counts, Journal of Combinatorial Theory, Series A 79 (1997), pp. 326-359. MR 1462562 (98h:05021)
  • [23] G. P´OLYA, G. SZEGÖ, Problems and Theorems in Analysis, Springer, New York, 1976.
  • [24] R. STANLEY, Enumerative Combinatorics, Vol. I, Cambridge University Press, Cambridge, 1997. MR 1442260 (98a:05001)
  • [25] L. TAKACS, Combinatorial Methods in the Theory of Stochastic Processes, John Wiley & Sons, Inc., New York, 1967. MR 0217858 (36:947)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05A05, 05A16, 06A07, 60C05, 20B99

Retrieve articles in all journals with MSC (2000): 05A05, 05A16, 06A07, 60C05, 20B99


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

DOI: https://doi.org/10.1090/S0002-9947-08-04478-4
Keywords: Bruhat ordering, weak ordering, permutations, partially ordered sets
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.
Article copyright: © Copyright 2008 American Mathematical Society

American Mathematical Society