We discuss a branch of Ramsey theory concerning edge Folkman numbers and how computer algorithms could help to solve some problems therein. We write G -> (a1,...,ak;p) if for every edge k-coloring of an undirected simple graph G not containing K_p, a monochromatic K_ai is forced in color i for some 1 <= i <= k. The edge Folkman number is defined as Fe(a1,...,ak;p) = min{|V(G)| : G -> (a1,...,ak;p)}. Folkman showed in 1970 that this number exists for p > max(a1,...,ak).
In general, much less is known about edge Folkman numbers than the related and more studied vertex Folkman numbers, where we color vertices instead of edges. Fe(3,3;4) involves the smallest parameters for which the problem is open, namely the question, ``What is the smallest order N of a K4-free graph, for which any edge 2-coloring must contain at least one monochromatic triangle?'' This is equivalent to finding the order N of the smallest K4-free graph which is not a union of two triangle-free graphs. It is known that 16 <= N (an easy bound), and it is known through a probabilistic proof by Spencer (later updated by Hovey) that N <= 3*10^9. We suspect that N <= 127. This talk will discuss the difficulties in obtaining better bounds on N, and some computational evidence why it is very likely that even N < 100.
Colloquia Series page.