New Bounds For Perfect k-hashing

Costa Simone, Dalai Marco. Arxiv 2020

[Paper]    
ARXIV

Let $C\subseteq \{1,\dots ,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 \mathrm{\infty }$, $|C|\le \exp (nk!/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

• Beating Fredman-komlos For Perfect k-hashing
• Improved Bounds For (bk)-hashing
• Approximate K-flat Nearest Neighbor Search
• A Coloring Of The Square Of The 8-cube With 13 Colors