Séminaire Lotharingien de Combinatoire, 89B.6 (2023), 12 pp.

Jesús A. De Loera and William J. Wesley

An Algebraic Perspective on Ramsey Numbers

Abstract. We study the Ramsey numbers R(r,s) through Hilbert's Nullstellensatz. We give a polynomial encoding whose solutions correspond to Ramsey graphs, those that do not contain a copy of K_r or K^-_s. The Ramsey number is reached the first time the system has no solution. We construct Nullstellensatz certificates of this fact whose degrees are equal to the restricted online Ramsey numbers. These results generalize to other numbers in Ramsey theory, such as Rado, van der Waerden, and Hales-Jewett numbers.

Received: November 15, 2022. Accepted: February 20, 2023. Final version: April 1, 2023.

The following versions are available:

PDF (211 K)
TeX version