Abstract
Ramsey theory is known for numbers that are extremely difficult to compute; Erdos famously said that computing the sixth Ramsey number is more difficult than fending off an alien invasion. However, recent advances in SAT solvers have put some of these numbers within reach. Inspired by the work of Heule et al. in computing the fifth Schur number and solving the Pythagorean triples problem, we present a study of the Rado numbers. Given an equation E, the k-color Rado number R_k(E) is the smallest number n such that every k-coloring of {1,2,...,n} contains a monochromatic solution to E. We give hundreds of new exact Rado number values and describe a SAT-based method to produce formulas for three infinite families of three-color Rado numbers.
If time permits, we will also discuss the connections between Ramsey theory and complexity of Nullstellensatz certification. We show that a broad class of “Ramsey-type” problems have encodings whose Nullstellensatz certificate degrees are bounded by analogues of the so-called restricted online Ramsey numbers, which are defined in terms of “Builder-Painter” games.
This work is joint with Yuan Chang and Jesús A. De Loera.