|
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 are comparable in the Bruhat order if one is closer, in a natural way, to the identity permutation, , than the other. We show that the number of comparable pairs is of order at most, and at least. For the related weak order, the corresponding bounds are and , where . 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
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,
-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
|