##
How Small Can the Most Wanted Folkman Graph Be ?

###
or searching for a K_{4}-free graph which is not a union of two triangle-free graphs

Stanislaw P. Radziszowski

Department of Computer Science

Rochester Institute of Technology

spr@cs.rit.edu
### ABSTRACT (formatted pdf)

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.

slides in pdf

Colloquia Series page.