Min-wise independent families with respect to any linear order

摘要

A set of permutations T on a finite linearly ordered set Omega is said to be k-min-wise independent, k-MWI for short, if Pr(min(pi(X))= pi(x))= 1/vertical bar X vertical bar for every X subset of Omega such that vertical bar X vertical bar = k and for every x is an element of X. (Here pi(x) and pi(X) denote the image of the element x or subset X of Omega under the permutation pi, and Pr refers to a probability distribution on T, 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.