TY - JOUR
T1 - Ramsey-Sperner theory
AU - Füredi, Zoltán
AU - Griggs, Jerrold R.
AU - Odlyzko, Andrew M.
AU - Shearer, James B.
PY - 1987
Y1 - 1987
N2 - Let [n] denote the n-set {1, 2,..., n}, let k, l ≥ 1 be integers. Define fl(n, k) as the minimum number f such that for every family F ⊆ 2[n] with {divides}F{divides}>f, for every k-coloring of [n], there exists a chain A1{subset not double equals}···{subset not double equals}Al+1 in F in which the set of added elements, Al+1-A1, is monochromatic. We survey the known results for l = 1. Applying them we prove for any fixed l that there exists a constant φ{symbol}l(k) such that as n→∞ fl(n,k)∼φ{symbol}l(k)⌊ 1 2n⌋n and φ{symbol}l(k)∼ φk 4logk as k→∞. Several problems remain open.
AB - Let [n] denote the n-set {1, 2,..., n}, let k, l ≥ 1 be integers. Define fl(n, k) as the minimum number f such that for every family F ⊆ 2[n] with {divides}F{divides}>f, for every k-coloring of [n], there exists a chain A1{subset not double equals}···{subset not double equals}Al+1 in F in which the set of added elements, Al+1-A1, is monochromatic. We survey the known results for l = 1. Applying them we prove for any fixed l that there exists a constant φ{symbol}l(k) such that as n→∞ fl(n,k)∼φ{symbol}l(k)⌊ 1 2n⌋n and φ{symbol}l(k)∼ φk 4logk as k→∞. Several problems remain open.
UR - http://www.scopus.com/inward/record.url?scp=38249037211&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38249037211&partnerID=8YFLogxK
U2 - 10.1016/0012-365X(87)90004-5
DO - 10.1016/0012-365X(87)90004-5
M3 - Article
AN - SCOPUS:38249037211
VL - 63
SP - 143
EP - 152
JO - Discrete Mathematics
JF - Discrete Mathematics
SN - 0012-365X
IS - 2-3
ER -