Min-Wise Independent Families with Respect to any Linear Order |
| |
Authors: | Peter J Cameron Pablo Spiga |
| |
Institution: | 1. School of Mathematical Sciences , Queen Mary, University of London , London, UK p.j.cameron@qmul.ac.uk;3. School of Mathematical Sciences , Queen Mary, University of London , London, UK |
| |
Abstract: | A set of permutations 𝒮 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 𝒮, 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. |
| |
Keywords: | Linear order Min-wise independent family Permutation group |
|
|