New bounds for perfect k-hashing
share
Let C⊆{1,...,k}^n be such that for any k distinct elements of C there exists a coordinate where they all differ simultaneously. Fredman and Komlós studied upper and lower bounds on the largest cardinality of such a set C, in particular proving that as n→∞, |C|≤(n k!/k^k-1+o(n)). Improvements over this result where 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, although they could only determine explicit improvements for k=5,6. For larger k, their method gives numerical values modulo a conjecture on the maxima of certain polynomials. In this paper, we first prove their conjecture, completing the explicit computation of an improvement over the Fredman-Komlós bound for any k. Then, we develop a different method which gives substantial improvements for k=5,6.
READ FULL TEXT