k-Color Sperner theorems

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. © 1986.