
Invited speaker:
Stanislaw Radziszowski
Rochester Institute of Technology
Title: On the Most Wanted Folkman Graph
Abstract: We discuss a branch of Ramsey theory concerning Folkman graphs and numbers.
We write G → (a_{1}, ... ,a_{k}; p)^{e} if for every edge
kcoloring of an undirected simple graph G not containing K_{p}, a
monochromatic K_{ai} is forced in color i for some i ∈ {1, ... ,k}.
The edge Folkman number is defined as
F_{e}(a_{1}, ... ,a_{k}; p) = min{V(G) :(a_{1}, ... ,a_{k}; p)^{e} }.
Folkman showed in 1970 that this number exists for p > max(a_{1}, ... ,a_{k}).
F_{e}(3,3;4) involves the smallest parameters for which
the problem is open, namely the question, "What is the smallest
order N of a K_{4}free graph, for which any edge 2coloring
must contain at least one monochromatic triangle?"
It is known that 16 < N (an easy bound), and it is known
through a probabilistic proof by Spencer that N < 3 ∗ 10^{9}.
We suspect that N < 127.
This talk will present the background, overview some related problems,
discuss the difficulties in obtaining better bounds on N, and give some
computational evidence why it is very likely that N < 100.
