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 ε{lunate} F such that A {subset not double equals} 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)=( n {down left corner} n 2{down right corner}). Here we study f(n, k) for k>2 and show that for any fixed k, f(n,k)∼dk( n {down left corner} n 2{down right corner}) as n→∞. We show that d3>1.036 and that as k → ∞, dk∼ πk 41nk. 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 → ∞ if k grows with n.
Original language | English (US) |
---|---|
Pages (from-to) | 31-54 |
Number of pages | 24 |
Journal | Journal of Combinatorial Theory, Series A |
Volume | 42 |
Issue number | 1 |
DOIs | |
State | Published - May 1986 |
Bibliographical note
Funding Information:* Research supported in part by the National Science Foundation, the University of Hawaii at Manoa, and the University of South Carolina Research and Productive Scholarship Foundation. + Research supported in part by Bell Laboratories and by a Miller fellowship at the Univer-sity of California, Berkeley.