= Separating set system
{title2=$\forall i\ne j\ \exists A:\ i\in A,\ j\notin A$}
A <set family> on a finite <set> separates ordered pairs if each ordered pair of distinct points has a member containing the first point and omitting the second. If its members are $A_1,\ldots,A_m$, assign each point the <characteristic vector> of its incidences, or equivalently $T_i=\{a:i\in A_a\}$. Separation in both directions says precisely that the $T_i$ form an <antichain> in the <Boolean lattice> on $m$ coordinates. Thus the <Sperner theorem> gives $n\leq\binom m{\lfloor m/2\rfloor}$. Conversely, any <antichain> of $n$ distinct subsets of $[m]$ supplies such a <set family> by transposing its incidence table.
Back to article page
