TOPICS
Search

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,

 (abcdefghi) (jklmnopqr) (stuvwxyz); (abcjklstu) (defmnovwx) (ghipqryz); (adgjmpsvy) (behknqtwz) (cfilorux).

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


See also

Katona's Problem

Explore with Wolfram|Alpha

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 "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Separating Family

Cite this as:

Weisstein, Eric W. "Separating Family." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SeparatingFamily.html

Subject classifications