Available in electronic format
Available in print format
Transacrions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)
     

How often are two permutations comparable?

Author(s): Adam Hammett; Boris Pittel
Journal: Trans. Amer. Math. Soc. 360 (2008), 4541-4568.
MSC (2000): Primary 05A05, 05A16, 06A07, 60C05; Secondary 20B99
Posted: April 4, 2008
Retrieve article in: PDF DVI PostScript

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:

[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: 10.1090/S0002-9947-08-04478-4
PII: S 0002-9947(08)04478-4
Keywords: Bruhat ordering, weak ordering, permutations, partially ordered sets
Received by editor(s): January 31, 2006
Posted: 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 of article: Copyright 2008, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google