Ramsey Numbers Through the Lenses of Polynomial Ideals and Nullstellensätze

Abstract

We study Ramsey-type numbers via Hilbert's Nullstellensatz and Alon's Combinatorial Nullstellensatz. We give encodings of various types of Ramsey numbers, from the classical graph theory version to the arithmetic Ramsey numbers of Rado, Schur, and van der Waerden, as systems of polynomial equations whose solutions are in bijection to colorings that avoid monochromatic patterns. For example, in the classical graph theory case the solutions correspond to Ramsey graphs of order $n$, those that do not contain a copy of $K_r$ or $\overline{K_s}$. When these systems of equations have no solution for the first time, the Ramsey-type number in question is attained. We construct Hilbert Nullstellensatz certificates whose degrees are equal to the restricted online Ramsey numbers introduced by Conlon, Fox, Grinshpun and He. Similar results apply to many numbers in Ramsey theory, including Rado, van der Waerden, Schur, and Hales-Jewett numbers. Finally, inspired by work of Alon and Tarsi, we introduce a new family of numbers that relate to the coefficients of a certain "Ramsey polynomial" and gives lower bounds for Ramsey numbers. Our work has strong connections to the complexity of Ramsey numbers.