1
$\begingroup$

Let $S$ be a (finite) set, and let $C \subseteq 2^S$ be a collection of subsets of $S$. We say that a subcollection $C' \subseteq C$ is separating if for any two elements of $S$ there exists a subset in $C'$ that contains exactly one of the two elements.

For example, any collection of cardinality less than $\log_2 \left\lvert S \right\rvert$ cannot be separating, while any collection of cardinality greater than $2^{\left\lvert S \right\rvert - 1}$ is separating.

Is there an efficient algorithm to construct all separating subcollections given $S$ and $C$?

I am particularly interested in finding separating subcollections of small cardinality. Perhaps this question is equivalent to some other more well-known problem?

Improve this question
$\endgroup$
  • $\begingroup$ OEIS A007600 may have relevant information. $\endgroup$ – BillyJoe Jan 14 at 11:38
  • $\begingroup$ @BillyJoe Thanks. However, it seems that their definition of "separating" differs from mine. For one, they require pairs of elements to be separated both ways: i.e., for $x, y \in S$, there exist subsets $C', C''$ such that $C'$ contains $x$ but not $y$, and $C''$ contains $y$ but not $x$. Moreover, they do not restrict the subsets to be from a particular given collection as I have. $\endgroup$ – JHF Jan 14 at 14:19

Your Answer

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

Browse other questions tagged or ask your own question.