# Enumerating separating subcollections of a set

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?

• OEIS A007600 may have relevant information. – BillyJoe Jan 14 at 11:38
• @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. – JHF Jan 14 at 14:19