TOPICS
Search

Katona's Problem


Find the minimum number f(n) of subsets in a separating family for a set of n elements, where a separating family is a set of subsets in which each pair of adjacent elements is found separated, each in one of two disjoint subsets. For example, the 26 letters of the alphabet can be separated by a family of nine:

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

The problem was posed by Katona (1973) and solved by C. Mao-Cheng in 1982,

 f(n)=min{2p+3[log_3(n/(2^p))]:p=0,1,2},

where [x] is the ceiling function. f(n) is nondecreasing, and the values for n=1, 2, ... are 0, 2, 3, 4, 5, 5, 6, 6, 6, 7, ... (OEIS A007600). The values at which f(n) increases are 1, 2, 3, 4, 5, 7, 10, 13, 19, 28, 37, ... (OEIS A007601), so f(26)=9, as illustrated in the preceding example.


See also

Separating Family

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.Katona, G. O. H. "Combinatorial Search Problem." In A Survey of Combinatorial Theory (Ed. J. N. Srivasta, F. Harary, C. R. Rao, G.-C. Rota, and S. S. Shrikhande). Amsterdam, Netherlands: North-Holland, pp. 285-308, 1973.Sloane, N. J. A. Sequences A007600/M0456 and A007601/M0525 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Katona's Problem

Cite this as:

Weisstein, Eric W. "Katona's Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/KatonasProblem.html

Subject classifications