Some Bounds On Separating Hash Families

Let X and Y be finite sets of size n and m. Let F be a family of functions from X to Y with |F|= N. Given positive integers ?1,?2,...,?t,we say that F is a {?1, ?2, ...,?t}- separating hash family, denoted by SHF(N;n,m, {?1,?2,...,}), if for any t pairwise disjoint subsets C1,C2, ...,Ct(?)X with|Ci| = ?i for 1 ? i ? t, there exists some f(?)F such that f(Ci) ? f(Cj) = (?)for 1 < i < j < t.Separating hash families are useful combinatorial structures introduced by D. R. Stinson, T. Trung and R. Wei in 2000. They can be used to construct frameproof codes, secure frameproof codes, codes with the identifiable parent-property and so on.We focus on the bounds for SHF(?1+?2;n,m,{?1,?2}). For the upper bounds of SHF(N; n,m,{?,?}), J. N. Staddon et al. proved n< m[N/w] + 2? ?2. When ?1 = ?2 = ? and N = 2?, M. Bazrafshan and T. Trung improved this bound and showed that n < m2. When ?1 ??2 and N = ?1+?2, many researchers contributed to the bounds for SHF(?1+?2;n,m,{?1,?2}),and the best known result is n ? m2.In this thesis, we shall show an optimal SHF(4;0,4,{2,2}) and use it to prove n? (m - 1)2 + 1 for SHF(2?;n,m{?,?}) with m ? 5. We also improve the known bound for SHF(?1+?2;n,m,{?1,?2}) from n ? m2 to n < m2 -m + 3.