IBM - Personal communication

This web page contains the abstract of my paper:

"Ramsey-Sperner Theory" with Z. Furedi, J. Griggs and A. Odlyzko, Discrete Mathematics, 63(1987), p. 143-152.

Abstract: 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 contained in 2**[n] with |F|>f, for every k-coloring of [n], there exists a chain A(1) strictly contained in ... strictly contained in A(l+1) in F in which the set of added elements, A(l+1)-A(1), is monochromatic.

We survey the known results for l=1. Applying them we prove for any fixed l that there exists a constant c(l,k) such that as n goes to infinity

fl(n,k) is asymptotic to c(l,k)*binomial coefficient n choose [n/2] and c(l,k) is asymptotic to l*sqrt(pi*k/(4*log(k))) as k goes to infinity.

Several problems remain open.

[ IBM Research home page | James B. Shearer's home page | Up ]
[ IBM home page | Order | Search | Contact IBM | Help | (C) | (TM) ]