Back to Search
Start Over
Correlation for permutations.
- Source :
-
Journal of Combinatorial Theory - Series A . Oct2020, Vol. 175, pN.PAG-N.PAG. 1p. - Publication Year :
- 2020
-
Abstract
- In this note we investigate correlation inequalities for 'up-sets' of permutations, in the spirit of the Harris–Kleitman inequality. We focus on two well-studied partial orders on S n , giving rise to differing notions of up-sets. Our first result shows that, under the strong Bruhat order on S n , up-sets are positively correlated (in the Harris–Kleitman sense). Thus, for example, for a (uniformly) random permutation π , the event that no point is displaced by more than a fixed distance d and the event that π is the product of at most k adjacent transpositions are positively correlated. In contrast, under the weak Bruhat order we show that this completely fails: surprisingly, there are two up-sets each of measure 1/2 whose intersection has arbitrarily small measure. We also prove analogous correlation results for a class of non-uniform measures, which includes the Mallows measures. Some applications and open problems are discussed. [ABSTRACT FROM AUTHOR]
- Subjects :
- *MALVACEAE
*PERMUTATIONS
*MATHEMATICAL equivalence
Subjects
Details
- Language :
- English
- ISSN :
- 00973165
- Volume :
- 175
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series A
- Publication Type :
- Academic Journal
- Accession number :
- 144360601
- Full Text :
- https://doi.org/10.1016/j.jcta.2020.105260