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 -