Correlation for permutations

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 o...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-04
Main Authors: Johnson, J Robert, Leader, Imre, Long, Eoin
Format: Article
Language:English
Subjects:
Correlation analysis
Permutations
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \(\pi\), the event that no point is displaced by more than a fixed distance \(d\) and the event that \(\pi\) 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.
ISSN:2331-8422