Abstract:

Let f(2,3,4) denote the smallest integer n such that there exists a K₄-free graph of order n having that property that any 2-coloring of its edges yields at least one monochromatic triangle. It is well-known that such a number must exist. For almost twenty years the best known upper bound, given by Spencer, was f(2,3,4) < 3 * 10⁹. Recently, Dudek and Rödl and subsequently Lu showed that f(2,3,4) < 130000 and f(2,3,4) < 10000, respectively. All previous bounds are based on an idea of Goodman. It seems that such methods will not yield substantial further improvement. In this talk we will generalize this idea by giving a necessary and sufficient condition for a graph G to yield a monochromatic triangle for every edge coloring. In particular, for any graph G we construct a graph H such that G is Folkman if and only if the value of the maximum cut of H is less than twice the number of triangles in G. We believe this technique in conjunction with semidefinite programming may be used to find a new upper bound on f(2,3,4). This is work in progress.

This is joint work with Vojtech Rödl.