Size of order-preserving minimal perfect hash family Suppose we have a universe of $u=|U|$ elements. We called a set of $H$ function $(U,m)$ order-preserving minimal perfect hash family (OPMPHF) if  for every subset $M\subset U$ of size $m$  has at least one function $h\in H$ which is an over preserving minimal prefect hash.   It is shown in [1,2] that for every   $(U,m)$-OPMPHF $H$ obeys:

$$H=m! \cdot \left.\binom{u}{m}\middle/\left(\frac{u}{m}\right)^m\right.   $$

Thus, the program length for any order preserving minimal perfect hash function should contain at least $\log_2 |H|$ bits.

In particular, if $m=3,u=8$, we have that $|H|\geq 17.7$.

However, I think I can create as set of  $|H|=6$ functions for such family. For every $2\leq i\leq 7$ we define $f_i(x)$ to be equal $1$ if $x&lt;i$, equal $2$ if $x=i$ and equal $3$ if $x\geq i$. Every function $f_i$ is order-preserving, and for each set $M$ with second element $i$ has a perfect function $f_i$.

Do I miss something in my analysis?

[1] Havas and Majewski, Optimal algorithms for minimal perfect hashing

[2] Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, volume 1. Springer-Verlag, Berlin Heidelberg, New York, Tokyo, 1984
Reference [1] defines order-preserving as follows:


  A hash function is order preserving if it puts entries into the hash table in a prespecified order.


In your case, this means that given any three elements $x,y,z \in \{1,\ldots,8\}$, you want there to be a hash function which maps $x$ to $1$, $y$ to $2$, $z$ to $3$.

In particular, it need not be the case that $x &lt; y &lt; z$.

If you add the assumption that $x &lt; y &lt; z$, then you can remove the $m!$ factor in the lower bound on $H$. The new lower bound states $H \geq 2.95$, that is, $H \geq 3$, which is not tight.