New Bounds for Perfect Hashing via Information Theory

A set of sequences of length t from a b-element alphabet is called k-separated if for every k-tuple of the sequences there exists a coordinate in which they all differ. The problem of finding, for fixed t, b, and k, the largest size N(t, b, k) of a k-separated set of sequences is equivalent to finding the minimum size of a (b, k)-family of perfect hash functions for a set of a given size. We shall improve the bounds for N(t, b, k) obtained by Fredman and Komlós 1].Körner 2] has shown that the proof in 1] can be reduced to an application of the sub-additivity of graph entropy 3]. He also pointed out that this sub-additivity yields a method to prove non-existence bounds for graph covering problems. Our new non-existence bound is based on an extension of graph entropy to hypergraphs.