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, lambda, namely v = 0 (mod k) and lambda(v - 1) = 0(mod k - 1), 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. (C) 2006 Elsevier B.V. All rights reserved.
universal hashing rbibds resolvable balanced incomplete block designs