New bounds for perfect hashing via information theory (Q1122979): Difference between revisions

Körner and Marton consider the problem of finding bounds for the largest size of a k-separated subset for a family of perfect hash- functions. By extending an information theoretic bounding technique based on graph entropy to more general structures they are able to improve the Fredman-Komlòs [\textit{M. Fredman} and \textit{J. Komlòs}, On the size of separating systems and perfect hash functions, SIAM J. Algebraic Discrete Methods 5, 61-68 (1984; Zbl 0525.68037) bounds in several cases: They give a new lower bound for the size of a 3-separated subset on a 3- element alphabet, namely \[ 1/t\quad \log N(t,3,3)\gtrsim 1/4 \log 9/5 \] and they present better bounds for a subclass of problems which includes a 3-separated subset on a 3-element alphabet as a special case. For all k-separated subsets on k-element alphabets with \(k>3\) they could not improve the Fredman-Komlòs bounds.