Colloquium

Date: April 21, 2023

Time: 12:40PM - 1:40PM

Location: BLOC 302

Speaker: Jesus De Loera, University of California, Davis

Description: Title: Who discovered Ramsey theory? An algebraic re-examination of Ramsey theory.

Abstract: It is indisputable Ramsey numbers are among the most mysterious and fascinating in Combinatorics. My talk focuses on Arithmetic Ramsey numbers and Diophantine problems, I discuss Rado numbers. These numbers are actually older than the usual graph theory version. For a positive integer k and linear equation E the Rado number R_k(E) is the smallest integer number n such that every k-coloring of [n] it contains a monochromatic solution to the equation E. A very famous example are Schur numbers, which are the Rado numbers for the equation E (X+Y=Z). I will discuss computation, bounds, and verification of Rado numbers and the fascinating history of Ramsey theory connected with names like Hilbert, Schur, van der Waerden, appearing along the way. I will not assume you know anything from the audience but I hope I will show, not just history, but also some new algebraic results. Our work combines discrete geometry, logic, algebraic geometry, an combinatorial number theory to investigate the behavior of Rado numbers. First, we computed many new exact values for Rado numbers using SAT solvers. In particular, we give a method for computing infinite families of Rado numbers, solving a few open questions. Regarding complexity and verification: Suppose someone suggests to you the value of R_k(E) . How can you certify that this value is correct and not a lie? We encode the problem as a system of polynomial equations and show that the degrees of Nullstellensatz certificates are actually bounded above by another Ramsey-number arising in a two-player game. The extremal k-colorings are in fact the solutions of this system which says that any proof that the proposed value of R_k(E) is not correct may require a doubly exponential certificate. At the heart is how combinatorial algebraic geometry relates to Ramsey numbers. This is joint work with Jack Wesley.