Katona's Problem
Find the minimum number 
of subsets in a Separating Family for a Set of 
elements, where aSeparating Family is a Set of Subsets in which each pair of adjacent elements is foundseparated, each in one of two disjoint subsets. For example, the 26 letters of the alphabet can be separated by a family ofnine:
The problem was posed by Katona (1973) and solved by C. Mao-Cheng in 1982,
where
is the Ceiling Function. is nondecreasing, and the values for 
, 2, ... are 0, 2, 3, 4,5, 5, 6, 6, 6, 7, ... (Sloane's A007600). The values at which increases are 1, 2, 3, 4, 5, 7, 10, 13, 19, 28, 37, ...(Sloane's A007601), so 
, as illustrated in the preceding example.See also Separating Family
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 et al.). Amsterdam, Netherlands: North-Holland, pp. 285-308, 1973. Sloane, N. J. A. SequencesA007600/M0456and A007601/M0525in ``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.
- Potential Function
- Potential Theory
- Pothenot Problem
- Poulet Number
- Power
- Power Center
- Power (Circle)
- Power Curve
- Powerfree
- Powerful Number
- Power Line
- Power Point
- Power Rule
- Power Series
- Power Set
- Power Spectrum
- Power (Statistics)
- Power Tower
- Power (Triangle)
- P-Polynomial
- p(prime)-Group
- P-Problem
- Practical Number
- Pratt Certificate
- Pratt-Kasapi Theorem