ON SOME PROPERTIES OF MIN-WISE INDEPENDENT FAMILIES AND GROUPS OF PERMUTATIONS

摘要

Informally, a family F is contained in S_n of permutations is k-restricted min-wise independent if for any X is contained in [n] with |X| ≤ k, each x ∈ X has an equal chance of being mapped to the minimum among π(X). In the second section of this paper, the connection of min-wise independent families of permutations and independence on lth minimum is studied. In the third section, we present a method of constructing a (k + 1)-restricted min-wise independent family from a k-restricted min-wise independent family when k is odd. As a corollary, we improve the existing upper bound on the minimum size of a 4-restricted min-wise independent family. In the last section, we consider min-wise independent groups of permutations.