Steklov Institute of Mathematics at St.Petersburg

PREPRINT 12/2004

CONSTRUCTING A $(k+1)$-RESTRICTED MIN-WISE INDEPENDENT fAMILY FROM A $k$-RESTRICTED MIN-WISE INDEPENDENT FAMILY WHEN $k$ IS ODD

This preprint was accepted September 7, 2004

ABSTRACT:
Informally, a family $\F\subseteq S_n$ of permutations is 
$k$-restricted min-wise independent if, for any $X\subseteq[n]$ with
$|X|\leq k$, each $x\in X$ has an equal chance of being mapped to 
the minimum among $\pi(X)$. In this paper
we present a way to construct 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 bounds on the minimal size of $k$-restricted min-wise independent families
for even $k\geq 4$.