A construction method for optimally universal hash families and its consequences for the existence of RBIBDs

We introduce a method for constructing optimally universal hash families and equivalently RBIBDs. As a consequence of our construction we obtain minimal optimally universal hash families, if the cardinalities of the universe and the range are powers of the same prime. A corollary of this result is that the necessary conditions for the existence of an RBIBD with parameters v,k,λ, namely and , are sufficient, if v and k are powers of the same prime. As an application of our construction, we show that the k-MAXCUT algorithm of Hofmeister and Lefmann [A combinatorial design approach to MAXCUT, Random Struct. Algorithms 9 (1996) 163–173] can be implemented such that it has a polynomial running time, in the case that the number of vertices and k are powers of the same prime.