3
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.