Recursive bounds for perfect hashing

Let k≤b be positive integers. A family C of sequences of length t over an alphabet of size b is called k-separated if for any k distinct members of C, there is a coordinate in which they mutually differ. Let N(t,b,k) denote the maximum size of such a family. This function has been studied extensively, mainly in the context of perfect hashing. Here we slightly improve a recent bound of Dyachkov, showing that for all t<k≤b, N(t,b,k)≤tb-(k-1)(t-1). This implies that if k≤b and t is divisible by k-1, then N(t,b,k)≤(k-1)bt/(k-1)-(k-1)2. © 2001 Elsevier Science B.V.