## 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)∼d_{k}( n {down left corner} n 2{down right corner}) as n→∞. We show that d_{3}>1.036 and that as k → ∞, d_{k}∼ π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.