Min-wise independent families with respect to any linear order

Peter J. Cameron*, Pablo Spiga

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


A set of permutations L on a finite linearly ordered set Ω is said to be k-min-wise independent, k-MWI for short, if Pr (min (π(X)) = π(x)) = 1/|X| for every X ⊆ Ω such that |X| ≤ k and for every x ∈ X. (Here π(x) and π(X) denote the image of the element x or subset X of Ω under the permutation π, and Pr refers to a probability distribution on L, which we take to be the uniform distribution.) We are concerned with sets of permutations which are k-MWI families for any linear order. Indeed, we characterize such families in a way that does not involve the underlying order. As an application of this result, and using the Classification of Finite Simple Groups, we deduce a complete classification of the k-MWI families that are groups, for k ≥3.

Original languageEnglish
Pages (from-to)3026-3033
Number of pages8
JournalCommunications in Algebra
Issue number10
Publication statusPublished - 1 Oct 2007


  • Linear order
  • Min-wise independent family
  • Permutation group


Dive into the research topics of 'Min-wise independent families with respect to any linear order'. Together they form a unique fingerprint.

Cite this