Abstract:

For an undirected, simple graph G, we write G > (a_1,...,a_k)^v (G > (a_1,...,a_k)^e) if for every vertex (edge) kcoloring, a monochromatic K_(a_i) is forced in some color i in {1,...,k}. The vertex (edge) Folkman number is defined as F_v(a_1,...,a_k;p) = min{V(G) : G > (a_1,...,a_k;p)^v, K_p not in G} F_e(a_1,...,a_k;p) = min{V(G) : G > (a_1,...,a_k;p)^e, K_p not in G} for p > max{a_1,...,a_k}. Folkman showed in 1970 that these numbers always exist for valid values of p. This thesis concerns the computation of a new result in Folkman number theory, namely that F_v(2,2,3;4)=14. Previously, the bounds stood at 10 <= F_v(2,2,3;4) <= 14, proven by Nenov in 2000. To achieve this new result, specialized algorithms were executed on the computers of the Computer Science network in a distributed processing effort. We discuss the mathematics and algorithms used in the computation. We also discuss ongoing research into the computation of the value of F_e(3,3;4). The current bounds stand at 16 <= F_e(3,3;4) <= 3e10^9. This number was once the subject of an Erd s prizeclaimed by Spencer in 1988. 