What number of colorings can guarantee that for every k-element subset there exists a coloring assigns different colors for elements from this subset? Let $M(n, k)$ be a minimal number $m$ such that there exists set $C$ ($|C|=m$) of colorings of n-element set $[n]$ with $k$ colors such that for every $k$-element subset $K$ of $[n]$ there exists coloring $c\in C$ such that $c$ assigns different colors for all elements of $K$.


*

*Is there any research about this object?

*Is there any closed-form formula for $M(n, k)$? May be for small $k$?


It's obvious that $M(n, 2)=\lceil\log_2(n)\rceil$ (simple divide and conquer idea), but $M(n, 3)$ is not so obvious for me.
 A: These are known as Perfect Hash Families. The notation $PHF(N;n,v,k)$ denotes a set $\mathcal H$ (hash functions) with $|\mathcal H|=N$, of $v$-colorings of the base $[n]$, such that for any $X\subset [n]$ with $|X|=k$, there exists at least one hash function which assigns it different colors. Let's denote by $f(n,v,k)$ the smallest $N$ for which a $PHF(N;n,v,k)$ exists. In this notation, you are interested in $f(n,k,k)$.
M. L. Fredman and J. Komlós prove in the paper "On the Size of Separating Systems and Families of Perfect Hash Functions" the following bounds:
$$\frac{v^{k-1}}{(v)_{k-1}}\cdot\frac{\log n}{\log(v-k+2)}\le f(n,v,k)\le \frac{k\log n}{\log\left(1-\frac{(v)_k}{v^k}\right)}$$
where $(v)_k=v(v-1)\cdots (v-k+1)$ is the falling factorial. This bound was improved by J. Körner and K. Marton in "New Bounds for Perfect Hashing via Information Theory" and there is a large literature making sharper bounds for particular families of parameters. Here is a large table of known parameters of realizable perfect hash families maintained by Ryan Dougherty.
