Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The \textit{Ramsey number} $R(r,s)$ is the smallest number $n$ such that every graph of order at least $n$ contains either a clique of size $r$ or an independent set of size $s$. Though easy to define, Ramsey numbers are among the most famous combinatorial constants and are difficult to compute, and few nontrivial numbers are known. There are several ways to encode the problem of computing Ramsey numbers using systems of polynomial equations, systems of linear inequalities, and logical formulas. We analyze several algebraic and Boolean encodings of Ramsey numbers. Our results include bounds using Hilbert's Nullstellensatz, cutting planes proof systems, and Boolean formulas. We have several computational explorations, and among them we managed to find new bounds for book and wheel Ramsey numbers using SAT solvers.