Algorithms for bounding Folkman numbers

 Redirect: RIT Scholars content from RIT Digital Media Library has moved from http://ritdml.rit.edu/handle/1850/2765 to RIT Scholar Works http://scholarworks.rit.edu/theses/6903, please update your feeds & links! Title: Algorithms for bounding Folkman numbers Author: Coles, Jonathan 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) k-coloring, 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 prize---claimed by Spencer in 1988. Record URI: http://hdl.handle.net/1850/2765 Date: 2006

Files in this item

Files Size Format View
JColesProposal2004.pdf 119.0Kb PDF View/Open
JColesThesis2004.pdf 418.2Kb PDF View/Open

The following license files are associated with this item: