New bounds for perfect k-hashing

Let C subset of {1, ...,k}(n) be such that for any k distinct elements of C there exists a coordinate where they all differ simultaneously. Fredman and Komlos studied upper and lower bounds on the largest cardinality of such a set C, in particular proving that as n -> infinity, vertical bar C vertical bar <= exp(nk!/k(k)(-1)+o(n)). Improvements over this result were first derived by different authors for k = 4. More recently, Guruswami and Riazanov showed that the coefficient k!/k(k)(-1) is certainly not tight for any k > 3 and provided explicit improvements for k = 5, 6, which are immediately extendable to k > 6 modulo a conjecture on the maxima of certain polynomials.In this paper, we first prove their conjecture, completing the derivation of their new bound for any k. Then, we develop a different method which gives further substantial improvements for k = 5, 6. (C) 2020 Elsevier B.V. All rights reserved.