Advisor: Dr. Stanislaw Radziszowski
Reader: Dr. Chris Homan
Observer: Dr. Rhys Price-Jones

Graduate Coordinator:
Dr. Hans-Peter Bischof

Preproposal (pdf) | Proposal (pdf)

Source code

Graphs (graph6, see Graph formats):

• H_v(2,2,3;4;14)
  
• Maximal H_v(2,2,3;4;14)
  
• Minimal H_v(2,2,3;4;14)
  
• Minimal in R(4,4) H_v(2,2,3;4;14)
  
• Bicritical H_v(2,2,3;4;14)
  

MCCCC 2004 slides
JCMCC paper

Algorithms for Bounding Folkman Numbers

Download Thesis

ABSTRACT

We write G -> (a₁,...,a_k)^v (G -> (a₁,...,a_k)^e) if for every vertex (edge) k-coloring of an undirected simple graph G, a monochromatic K_ai is forced in color i ε {1,...,k}. The vertex Folkman number is defined as F_v(a₁,...,a_k;p) = min{|V(G)| : G -> (a₁,...,a_k)^v, K_p ⊄ G}, p > max{a₁,...,a_k}. Likewise, the edge Folkman number is defined as F_e(a₁,...,a_k;p) = min{|V(G)| : G -> (a₁,...,a_k)^e, K_p ⊄ G}, p > max{a₁,...,a_k}.

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) ≤ 3x10⁹. This number was once the subject of an Erdös prize—claimed by Spencer in 1988.