A $(n,k)$-perfect hashing family is a family of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S \in H$ such that $H_S$ is injective on $S$.
There are known (deterministic) builds of such family of size $O(e^{k+log^2k}log n)$, while there is a $\Omega(e^k \cdot \frac{log n}{\sqrt k})$ lower bound , which is almost tight.
I'm looking at a slight variation of this, and require that for every (ordered) sequence $X=<x_1,x_2,...,x_k>$ such that $\forall i\neq j:x_i\in [n],x_i\neq x_j$, there exists some $h_S$ such that $\forall i\in [k]: h(x_i)=i$.
Showing a small (of size $O(k^{k+1} \log n)$) family exists is quite simple:
The probability that such random $h$ satisfies the condition for $X$ is $k^{-k}$, and there are $\frac{n!}{(n-k)!}$ such vectors, so if I pick a random set of $r$ functions the chance that any $X$ was left uncovered is at most (union bound)
$$ (1-k^{-k})^r\frac{n!}{(n-k)!} < (1-k^{-k})^r\cdot n^k < n^ke^{rk^{-k}}$$
Now we can demand that the probability will be strictly smaller than 1 (which means that family of size $r$ exists), we get: $$r > k^{k+1}\text{log}n$$
What is the smallest ordered perfect hashing family we can build deterministically?
