标题： 改进的$(b,k)$-哈希界限 显示英文标题

标题： Improved Bounds for $(b,k)$-hashing

摘要： 对于固定的整数$b\geq k$，计算机科学和组合学中一个相关的问题是确定随着$n$增长，最大的集合的渐近增长，使得存在一个具有$n$个函数的$(b, k)$-哈希族。 等价地，确定$\{1,2,\ldots,b\}^n$的最大子集的渐近增长，使得该集合中的任何$k$个不同元素在某个坐标上都彼此不同。 对于一般的$b, k$的重要渐近上界，Fredman 和 Komlós 在 80 年代推导出来，并且 Körner 和 Marton 以及 Arikan 对某些$b\neq k$进行了改进。最近，Guruswami 和 Riazanov 对一般的$b,k$情况得到了更好的界限，而对于$b=k$的小值，Arikan、Dalai、Guruswami 和 Radhakrishnan 以及 Costa 和 Dalai 得到了更强的结果。在本文中，我们既展示了其中一些结果如何扩展到$b\neq k$，又进一步加强了某些特定小值的$b$和$k$的界限。我们使用的方法依赖于将一个优化问题减少到有限数量的情况，这表明通过更精细的论证可以得到进一步的结果，但会增加复杂性，这种复杂性可以通过使用更复杂和优化的算法方法来降低。 显示英文摘要

摘要： For fixed integers $b\geq k$, a problem of relevant interest in computer science and combinatorics is that of determining the asymptotic growth, with $n$, of the largest set for which a $(b, k)$-hash family of $n$ functions exists. Equivalently, determining the asymptotic growth of a largest subset of $\{1,2,\ldots,b\}^n$ such that, for any $k$ distinct elements in the set, there is a coordinate where they all differ. An important asymptotic upper bound for general $b, k$, was derived by Fredman and Koml\'os in the '80s and improved for certain $b\neq k$ by K\"orner and Marton and by Arikan. Only very recently better bounds were derived for the general $b,k$ case by Guruswami and Riazanov while stronger results for small values of $b=k$ were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan and by Costa and Dalai. In this paper, we both show how some of the latter results extend to $b\neq k$ and further strengthen the bounds for some specific small values of $b$ and $k$. The method we use, which depends on the reduction of an optimization problem to a finite number of cases, shows that further results might be obtained by refined arguments at the expense of higher complexity which could be reduced by using more sophisticated and optimized algorithmic approaches.