On the Size of Separating Systems and Families of Perfect Hash Functions

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.