On the Size of Separating Systems and Families of Perfect Hash Functions
Michael L. Fredman, János Komlós · SIAM Journal on Algebraic and Discrete Methods · 1984
This paper presents two applications of an interesting information theoretic theorem about graphs. The first application concerns the derivation of good bounds for the function $Y(b,k,n)$, which is defined to be the minimum size of a family of functions such that for every subset of size k from an n element universe, there exists a perfect hash function in the family mapping the subset into a table of size b. The second application concerns the derivation of good bounds for the function $M(i,j,n)$, which is defined to be the minimum size of an $(i,j)$-separating system.