Improved Lower Bounds for Families of e-Approximate fc-Restricted Min-Wise Independent Permutations

摘要

A family 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 Sn be the family of all permutations on [1, n] ={1,2,..., n}. For any integer k such that 1 ≤ k ≤ n and any real e > 0, we say that a family T C Sn of permutations isξ-approximate k-restricted min-wise independent if for any (nonempty) subset X C [1, n) such that ||X|| ≤ k and any element x∈X, |Pr[min{7r(X)} = ir(x)] - ||X||~1] < e/||JT||, when π is chosen from uniformly at random (where ||A|| denotes the cardinality of a finite set A). For the size of families T C Sn of e-approximate restricted min-wise independent permutations, the following results are known: For any integer k such that 1 < k < n and any real e > 0, (constructive upper bound) ||F||=2~4k+0(K)K~2log log (n/ξ); (nonconstructive upper bound) ||:F|| = O(^ lpg(n/fe)); (lower bound) ||F|| = O(K2/ξ2log(n/k) = n(min{k~22~Klog(n/k), log(1/ξ)(log n-log log(1/ξ)/ξ1/2) In this paper, we first derive an upper bound for the Ramsey number of the edge coloring with m > 2 colors of a complete graph Ke of vertices, and by the linear algebra method, we then derive a slightly improved lower bound, i.e., we show that for any family F in contail of S_n of ξ-approximate fc-restricted min-wise independent permutations,||F||=Ω(K1/ξlog(n/k))~2(1/2).