Georgia Institute of Technology College of Sciences

For two graphs, G and F, we write G\longrightarrow F if every 2-coloring of the edges of G results in a monochromatic copy of F. A graph G is k-Folkman if G\longrightarrow K_k and G\not\supset K_{k+1}. We show that there is a constant c > 0 such that for every k \ge 2 there exists a k-Folkman graph on at most 2^{k^{ck^2}} vertices. Our probabilistic proof is based on a careful analysis of the growth of constants in a modified proof of the result by Rodl and the speaker from 1995 establishing a threshold for the Ramsey property of a binomial random graph G(n,p). Thus, at the same time, we provide a new proof of that result (for two colors) which avoids the use of regularity lemma. This is joint work with Vojta Rodl and Mathias Schacht.