This web page contains the abstract of my paper:
"k-color Sperner Theorems" with J.R. Griggs and A.M. Odlyzko, Journal of Combinatorial Theory Series A, 4(1986), p. 31-54.
Abstract: A family F of subsets of an n-set S is said to have property X for a k-coloring of S if for all A,B contained in F such that A is not a subset of B, B-A is not monochromatic. Let f(n,k) denote the maximum value of |F| over all families F which have property X with respect to some k-coloring of S. The standard and two-part Sperner Theorems imply that f(n,1)=f(n,2)=binomial coefficient n choose [n/2]. Here we study f(n,k) for k>2 and show that for any fixed k, f(n,k) is asymptotic to (dk * binomial coefficient n choose [n/2]) as n goes to infinity. We show d3>1.036 and that as k goes to infinity dk is asymptotic to sqrt(pi*k/(4*ln(k))). A natural generalization of Sperner's theorem concerning the existence of nice extremal families F is proved. Further, a related linear programming problem is studied, and results are obtained about f(n,k) as n goes to infinity if k grows with n.
IBM Research home page |
James B. Shearer's home page |
[ IBM home page | Order | Search | Contact IBM | Help | (C) | (TM) ]