Perfect hash families: Probabilistic methods and explicit constructions

An (n, q, t)-perfect hash family of size s consists of a set V of order,t. a set F of order q, and a sequence phi(1), phi(2),....., phi(s) of functions from V to F with the following: property. For all t-subsets X subset of or equal to 1, there exists i epsilon {1,2,.... s} such that phi(i) is injective when restricted to X. An (n, q, t)-perfect hash family of minimal sire is known us optimal. The paper presents a probabilistic existance result for perfect hash families which improves on the well known result of Mehlhorn for many parameter sets. The probabilistic methods are strong enough to establish the size of an optimal perfect hash family in many cases. The paper also gives sever;li explicit constructions of classes of perfect hash families. (C) 2000 Academic Press.