One famous result of Stinson, van Trung, and Wei is that PHFN(k,v,t) <= c*(log(2k choose t)-log(k)) where c is a constant independent of k, but dependent on v, t. The proof essentially shows that if we start with 2k columns, and have the expected number of unseparated t-sets be strictly smaller than k, then we can delete one column from each of these unseparated t-sets, and are guaranteed then to have at least k columns. The math continues almost identically to the basic method in Perfect Hash Families (a brief overview).

But note that this method does not rely on having exactly 2k columns – note that if we started with any number of columns m > k, and delete m-k columns, we are still ok. So therefore PHFN(k,v,t) <= c*(log(m choose t) – log(k-m)) where c is the same constant as before.

The question then is to determine what is the “best” choice of m here, since it is a discrete value. One could use Stirling’s approximation and find the minimum of such a function by taking the derivative of it with respect to m.

The function is: m log(m) – t log(t) – (m-t)log(m-t) – log(m-k), and the derivative is log(m) – log(m-t) – 1/(m-k). WolframAlpha cannot find a value of m that has this derivative equal to 0. We could note that t log(t) is much smaller than mlog(m), and approximate t log (t) by 0, but this does not help.

If someone can identify how to find the minimum of this function, that would be of great use!