info prev up next book cdrom email home

Separating Family

A Separating Family is a Set of Subsets in which each pair of adjacent elements are found separated, each in one of two disjoint subsets. The 26 letters of the alphabet can be separated by a family of 9,

\begin{displaymath}
\matrix{
(abcdefghi) & (jklmnopqr) & (stuvwxyz)\cr
(abcjklst...
...x) & (ghipqryz)\cr
(adgjmpsvy) & (behknqtwz) & (cfilorux)\cr}.
\end{displaymath}

The minimal size of the separating family for an $n$-set is 0, 2, 3, 4, 5, 5, 6, 6, 6, 7, 7, 7, ... (Sloane's A007600).

See also Katona's Problem


References

Honsberger, R. ``Cai Mao-Cheng's Solution to Katona's Problem on Families of Separating Subsets.'' Ch. 18 in Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 224-239, 1985.

Sloane, N. J. A. Sequence A007600/M0456 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.




© 1996-9 Eric W. Weisstein
1999-05-26