2019/09/09 by J. Robert Johnson, Johnson, J. Robert, Imre Leader +3
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Limits and Structures in Graph Theory #Random Matrices and Applications #math.CO #math.PR #msc:05A05 #msc:05D99 #msc:06A07 #msc:60C05
paper · pdf · doi:10.48550/arxiv.1909.03770
19 pages, 3 figures. Minor corrections from previous version
arxiv created 2020/04/21 · arxiv updated 2020/04/22
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 Sn, giving rise to differing notions of up-sets. Our first result shows that, under the strong Bruhat order on Sn, 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.