New Bounds For Perfect k-hashing
Costa Simone, Dalai Marco. Arxiv 2020
Let \(C\subseteq \{1,\ldots,k\}^n\) be such that for any \(k\) distinct elements of \(C\) there exists a coordinate where they all differ simultaneously. Fredman and Koml'os studied upper and lower bounds on the largest cardinality of such a set \(C\), in particular proving that as \(n\to\infty\), \(|C|\leq \exp(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'os bound for any \(k\). Then, we develop a different method which gives substantial improvements for \(k=5,6\).
Similar Work