Correlation for permutations

DOI10.1016/J.JCTA.2020.105260zbMATH Open1442.05007arXiv1909.03770OpenAlexW3021539937MaRDI QIDQ778700FDOQ778700

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)

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.

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

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

zbMATH Keywords

permutationsBruhat ordercorrelation inequality

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cites Work

• NON-NULL RANKING MODELS. I
• Combinatorics of Coxeter Groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Correlation inequalities on some partially ordered sets
• Title not available (Why is that?)
• An inequality for the weights of two families of sets, their unions and intersections
• Spatial random permutations and infinite cycles
• Families of Non-disjoint subsets
• Gibbs measures on permutations over one-dimensional discrete point sets

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)