k-Color Sperner theorems

Jerrold R. Griggs, Andrew M. Odlyzko, James B. Shearer

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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 languageEnglish (US)
Pages (from-to)31-54
Number of pages24
JournalJournal of Combinatorial Theory, Series A
Volume42
Issue number1
DOIs
StatePublished - 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.

Fingerprint

Dive into the research topics of 'k-Color Sperner theorems'. Together they form a unique fingerprint.

Cite this