Correlation for permutations

DOI10.1016/J.JCTA.2020.105260MaRDI QIDQ778700zbMATH OpenOpenAlexFDO

Authors J. Robert Johnson, Imre Leader, Eoin Long

Publication date 3 July 2020

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.03770

zbMATH Keywords

permutationsBruhat ordercorrelation inequality

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

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

Recommendations

• How often are two permutations comparable?
• On degrees in the hasse diagram of the strong Bruhat order
• Correlation in partially ordered sets
• Some correlation inequalities in finite posets
• scientific article; zbMATH DE number 218835

Cites work

• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 3198427 (Why is no real title available?)
• An inequality for the weights of two families of sets, their unions and intersections
• Combinatorics of Coxeter Groups
• Correlation inequalities on some partially ordered sets
• Families of Non-disjoint subsets
• Gibbs measures on permutations over one-dimensional discrete point sets
• NON-NULL RANKING MODELS. I
• Spatial random permutations and infinite cycles

This page was built for publication: Correlation for permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q778700)