# Is there a deterministic algorithm to construct $(n,k)$-universal set of minimum size?

Let $S\subseteq \{0,1\}^n$, $S$ is a $(n,k)$-universal set if for every subset of indices $I$ of size $k$, projecting $S$ to $I$ yield the $2^k$ binary strings (all the possible strings of $I$). $S$ is of minimum size if there is no other $(n,k)$-universal set $S'$ where $|S'|<|S|$.

is there a known algorithm to construct a $(n,k)$-universal set in general and of (close-to) minimum size in particular?

Such constructions appear in papers of Seroussi and Bshouty, Alon, and Naor and Naor. See Bshouty for the latest on this topic.

Suppose there is a simple structure $T$ such that it consists of a set of elements $E$ that each have a one-to-one correspondence with a unique element in $S$. Suppose there is a bijective function $F$ that maps from $T$ to $S$. Then $S$ and $T$ equinumerous and contain the same amount of elements.

By definition, a set $A$ cannot be mapped onto another set $B$ with a bijective function unless the cardinality of B is equal or greater than that of A. Therefore, the cardinality of B, assuming bijection with A, is the least possible if cardinality of B is equal to that of A.

Therefore, we are looking for a function to construct the set of $T$, which consists of the same amount of elements of $S$, as well as the bijective function $F$ that connects $T$ to $S$.

Therefore, we are looking for a set constructor, computable function $C(S)$ that will return $(T, F)$.

I will propose that we should look for a μ-recursive function that takes a set and can compute the number of elements in that set. It will construct a set $T$ such that it will induct elements of the natural numbers into $T$ until the elements of the input set are exhausted, and it will also construct a closed recursive function $R$ that can iteratively search linearly over the set of $T$, adding a new level of recursion for each iteration of the constructor function $C$, and correctly map an element of $T$ to its corresponding element $S$. At the end of construction, $R$ will be equivalent to $F$.

If we know that $S$ is finite, then even if $C$ is not closed recursive, if its termination requirement depends on the number of elements on its input set and the set is of finite size, then $C$ should terminate and will be computable.

Therefore, there does exist an algorithm that can construct $(T, F)$ for a finite set $S$ of size $2^n$ such that $T$ is the same size of $S$ (the minimum) and has a bijective function $F$ to map $T$ to $S$.

• That doesn't answer the question. Presumably we are interested in an efficient algorithm. It's trivial that you can construct effectively a minimum size universal set by enumerating all possibilities. – Yuval Filmus Feb 22 '16 at 22:10