A family ${\cal F}$ of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. For any integer $n>0$, let $S_{n}$ be the family of al permutations on $[1,n]=\{1,2,\ldots, n\}$.
For any integer $k \in [1,n]$ and any real $\varepsilon >0$, we say that a family ${\cal F} \subseteq S_{n}$ of permutations is $\varepsilon$-approximate $k$-restricted min-wise independent} if for any (nonempty) $X \subseteq [1,n]$ such that $||X|| \leq k$ and any $x \in X$, $|\Pr [\min \{\pi(X)\} = \pi(x)]- 1/\card{X}| \leq \varepsilon/|||X||$, when $\pi$ is chosen from
${\cal F}$ uniformly at random (where $||A||$ is the cardinality of a finite set $A$). For the size of families ${\cal F} \subseteq S_{n}$ of $\varepsilon$-approximate $k$-restricted min-wise independent permutations,
the following results are known: For any integer $k\in [1,n]$ and any real
$\varepsilon > 0$,
(constructive upper bound)
$||{\cal F}|| = 2^{4k+0(k)}k^{2 \log \log n/\varepsilon)}$;
(nonconstructive upper bound)
$||{\cal F}} = O(\frac{k^{2}}{\varepsilon^{2}} \log (n/k))$;
(lower bound) $||{\cal F}|| = \Omega(k^{2}(1-\sqrt{8 \varepsilon}))$.
In this paper, we first derive an upper bound for the Ramsey number of the edge coloring with $m \geq 2$ colors of a complete graph $K_{\ell}$ of $\ell$ vertices, and by the linear algebra method, we then derive an improved lower bound, i.e., we show that for any family ${\cal F} \subseteq S_{n}$ of $\varepsilon$-approximate $k$-restricted min-wise independent permutations, $||{\cal F}|| = \Omega\left(k \sqrt{\frac{1}{\varepsilon}\log (n/k)}\right)$.