\magnification=1200
\hsize=4in
\nopagenumbers
\noindent
%
%
{\bf Tom Bohman, Colin Cooper, Alan Frieze}
%
%
\medskip
\noindent
%
%
{\bf Min-Wise Independent Linear Permutations}
%
%
\vskip.5cm
\noindent
%
%
%
%
A set of permutations ${\cal F} \subseteq S_n$ is {\it min-wise
independent} if for any set $X \subseteq [n]$ and any $x \in X$,
when $\pi$ is chosen at random in ${\cal F}$ we have ${\bf P}
\left(\min\{\pi(X)\} = \pi(x)\right) = {{1}\over {|X|}}$. This
notion was introduced by Broder, Charikar, Frieze and Mitzenmacher
and is motivated by an algorithm for filtering near-duplicate web
documents. {\it Linear permutations\/} are an important class of
permutations. Let $p$ be a (large) prime and let ${\cal
F}_p=\{p_{a,b}:\;1\leq a\leq p-1,\,0\leq b\leq p-1\}$ where for
$x\in [p]=\{0,1,\ldots,p-1\}$, $p_{a,b}(x)=ax+b\pmod p$. For
$X\subseteq [p]$ we let $F(X)=\max_{x\in X}\left\{{\bf
P}_{a,b}(\min\{p(X)\}=p(x))\right\}$ where ${\bf P}_{a,b}$ is over
$p$ chosen uniformly at random from ${\cal F}_p$. We show that as
$k,p \to\infty$, ${\bf E}_X[F(X)]={{1}\over {k}}+O\left({(\log
k)^3}\over {k^{3/2}}\right)$ confirming that a simply chosen
random linear permutation will suffice for an average set from the
point of view of approximate min-wise independence.
\bye