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

2022/09/28 by Jesús A. De Loera, De Loera, Jesús A., William J. Wesley +1
Computer Science · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2209.13859

openalex publication_date 2022/09/28 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28

Abstract

In this article we study the Ramsey numbers R(r,s) through Hilbert's Nullstellensatz and Alon's Combinatorial Nullstellensatz. We give polynomial encodings whose solutions correspond to Ramsey graphs of order n, those that do not contain a copy of K_r or K_s. When these systems have no solution and n ≥ R(r,s), we construct Nullstellensatz certificates whose degrees are equal to the restricted online Ramsey numbers introduced by Conlon, Fox, Grinshpun and He. Moreover, we show that these results generalize to other numbers in Ramsey theory, including Rado, van der Waerden, and Hales-Jewett numbers. Finally, we introduce a family of numbers that relate to the coefficients of a certain "Ramsey polynomial" that gives lower bounds for Ramsey numbers.

Related

• Off-diagonal Ramsey numbers
• Reinforced Generation of Combinatorial Structures: Ramsey Numbers
• On Ramsey Numbers
• A coding perspective on the lower bound for diagonal Ramsey numbers
• Recent developments in graph Ramsey theory