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).