Exact Ramsey theory: Green-Tao numbers and SAT

Oliver Kullmann

(Swansea)

The field of Ramsey theory offers great opportunities for improving our understanding of solving hard combinatorial instances:
Try solving the problem instances arising when computing (concrete) Ramsey-type numbers, and understand/improve what's happening.

Van der Waerden numbers are obtained when seeking the smallest n such that partitioning the first n numbers into a given number of parts is guaranteed to contain an arithmetic progression of a given length in some part. We have introduced Green-Tao numbers, defined analogously to van der Waerden numbers, but using the first n prime numbers instead of the first n natural numbers. The existence of these numbers is guaranteed by the celebrated Green-Tao theorem (which runs under the slogan ``there are arithmetic progressions of arbitrary size in the primes'').
In my talk I want to report on our first findings regarding these Green-Tao numbers.

This talk should be accessible by "everybody".

See http://arxiv.org/abs/1004.0653v2 for the underlying report.
Thursday 6th May 2010, 14:15
Video Conferencing Room - Far-134
Department of Computer Science