# 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, 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

• What is an order-preserving minimal perfect hash? May 20 '20 at 7:15
• An order preserving minimal prefect hash function $f$ for a set $S\subset U$ satisfies the following properties: 1) For each $x,y\in S$ such that $x<y$ we have $f(x)<f(y)$ (order preserving). 2) The function $f:S\to {1,2..,|S|}$ is a bijection (minimal perfect hash). May 21 '20 at 8:00
• Don't leave clarifications in the comments. Instead, please edit the question so that the question is self-contained and reads well for someone who encounters it for the first time. People shouldn't have to read the comments to understand what you are asking.
– D.W.
May 21 '20 at 23:31

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 < y < z$$.
If you add the assumption that $$x < y < 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.