Tight Bounds for Monotone Minimal Perfect Hashing

The monotone minimal perfect hash function (MMPHF) problem is the following indexing problem. Given a set \ (S=\s₁, , s₍\\) of \ (n\) distinct keys from a universe \ (U\) of size \ (u\), create a data structure \ (D\) that answers the following query: \ (equation* RANK (q) = cases rank of q in S & q S\\ arbitrary answer & otherwise. casesequation*\) Solutions to the MMPHF problem are in widespread use in both theory and practice. The best upper bound known for the problem encodes \ (D\) in \ (O (n u) \) bits and performs queries in \ (O (u) \) time. It has been an open problem to either improve the space upper bound or to show that this somewhat odd looking bound is tight. In this paper, we show the latter: any data structure (deterministic or randomized) for monotone minimal perfect hashing of any collection of \ (n\) elements from a universe of size \ (u\) requires \ ( (n) \) expected bits to answer every query correctly. We achieve our lower bound by defining a graph \ (G\) where the nodes are the possible \ (u n\) inputs and where two nodes are adjacent if they cannot share the same \ (D\). The size of \ (D\) is then lower bounded by the log of the chromatic number of \ (G\). Finally, we show that the fractional chromatic number (and hence the chromatic number) of \ (G\) is lower bounded by \ (2^ (n u) \).