CS 269S, Winter 2014: Theory Seminar
Bren Hall, Room 1423, 1pm
January 31, 2014:

The Most Wanted Folkman Number

Christopher Wood

In this talk we discuss a branch of Ramsey theory concerning edge Folkman numbers, as well as several computational techniques that have been used to solve problems therein. The edge Folkman number Fe(s,t;q) is the order of the smallest Kq-free graph G such that G -> (s,t)^e, where G->(s,t)^e is true iff for all red and blue edge colorings of G there exists a monochromatic Ks or Kt. Our main focus is on the edge Folkman number Fe(3,3;4). We present relevant background for this particular problem, survey related work and computational techniques for computing Folkman numbers, and finally, discuss ongoing work attempting to prove that the Fe(3,3;4) <= 127.