Optimal linear perfect hash families

Let V be a set of order n and let F be a set of order q. A set S subset of or equal to {phi: V --> F} of functions from V to F is an (n, q, t)-perfect hash family if for all X subset of or equal to V with \X\ = t, there exists dr ES which is injective when restricted to X. Perfect hash families arise in compiler design, in circuit complexity theory and in cryptography. Let S be an (n, q, t)-perfect hash family. The paper provides lower bounds on \S\, which better previously known lower bounds for many parameter sets. The paper exhibits new classes of perfect hash families which show that these lower bounds are realistic. (C) 1998 Academic Press.