Perfect hashing and probability. (English) Zbl 0820.68063
Summary: A simple proof is given of the best-known upper bound on the cardinality of a set of vectors of length \(t\) over an alphabet of size \(b\), with the property that, for every subset of \(k\) vectors, there is a coordinate in which they all differ. This question is motivated by the study of perfect hash functions.
MSC:
| 68Q45 | Formal languages and automata |
| 68R15 | Combinatorics on words |
| 60G35 | Signal detection and filtering (aspects of stochastic processes) |
Keywords:
perfect hash functionsReferences:
| [1] | Körner, Europ. J. Combinatorics 9 pp 523– (1988) · Zbl 0676.68007 · doi:10.1016/S0195-6698(88)80048-9 |
| [2] | DOI: 10.1137/0607062 · Zbl 0603.05034 · doi:10.1137/0607062 |
| [3] | Alon, The Probabilistic Method (1991) |
| [4] | DOI: 10.1137/0605009 · Zbl 0525.68037 · doi:10.1137/0605009 |
| [5] | Hardy, Inequalities (1952) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
