1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 22 '16 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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