The probabilistic bound for perfect hashing is sharp only for binary alphabets
Source: arxiv.org/abs/2611.08230
We investigate the optimal asymptotic rate $R_q$ of perfect $q$-hash codes, a fundamental extremal problem in combinatorics, information theory, and computer science. Let $B_q=-\log_2(1-q!/q^q)/(q-1)$ denote the classical probabilistic lower bound. We prove that $R_q=B_q$ if and only if $q=2$, establishing an explicit strict improvement for every $q\ge3$ and settling the first assertion of a conjecture of Xing and Yuan (Combinatorica 43 (2023), 347--366). More significantly, we show that, for every $η>0$, $R_q\ge B_q+\exp(-(2+η)q)$ for all sufficiently large integers $q$. This improves the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.08230
curl -X POST /api/v1/records/arxiv/2611.08230/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.08230/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'