Name
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 ϵ F such that A ⫋ 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 ⌞ n 2 ⌟ ) . Here we study f ( n , k ) for k >2 and show that for any fixed k, f(n,k)∼d k ( n ⌞ n 2 ⌟ ) as n →∞. We show that d 3 >1.036 and that as k → ∞, d k ∼ πk 41 n 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 → ∞ if k grows with n . |
Year | DOI | Venue |
|---|---|---|
1986 | 10.1016/0097-3165(86)90005-1 | J. Comb. Theory, Ser. A |
Keywords | Field | DocType |
k-color sperner theorem | Discrete mathematics,Monochromatic color,Combinatorics,Partition (number theory),Mathematics | Journal |
Volume | Issue | ISSN |
42 | 1 | Journal of Combinatorial Theory, Series A |
Citations | PageRank | References |
4 | 1.82 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jerrold R. Griggs | 1 | 848 | 192.97 |
| Andrew M. Odlyzko | 2 | 1286 | 413.71 |
| James B. Shearer | 3 | 277 | 79.48 |