论文标题
完美$ k $的新边界
New bounds for perfect $k$-hashing
论文作者
论文摘要
令$ c \ subseteq \ {1，\ ldots，k \}^n $使得对于任何$ k $ dintertion $ c $的不同元素都存在一个坐标，它们都会同时不同。弗雷德曼（Fredman）和科姆洛斯（Komlós）研究了上限和下界，这是$ c $的最大基数，特别是证明，作为$ n \ to \ in \ infty $，$ | c | \ leq \ exp \ exp（n k！/k！/k！/k^{k-1}+o（n））$。对此结果的改进，而不同作者首先以$ k = 4 $得出。最近，Guruswami和Riazanov表明，对于任何$ k> 3 $，系数$ k！/k^{k-1} $肯定不会紧张，尽管他们只能确定$ k = 5,6 $的明确改进。对于较大的$ k $，它们的方法给出了数值值模拟某些多项式的最大值。 在本文中，我们首先证明了他们的猜想，完成了对弗雷德曼·科莫斯（Fredman-Komlós）对任何$ k $ bund的改进的明确计算。然后，我们开发了一种不同的方法，该方法可为$ k = 5,6 $提供大量改进。
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ós 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ós bound for any $k$. Then, we develop a different method which gives substantial improvements for $k=5,6$.
