UC Davis

Ramsey numbers and their variants are among the most interesting and well-studied numbers in combinatorics. This dissertation explores them through the lenses of algebraic and Boolean methods.

Many combinatorial problems have natural encodings as systems of polynomial equations where the system is feasible if and only if the original problem has a solution. When a system $f_1 = \dots = f_m = 0$ has no solution over an algebraically closed field, Hilbert's Nullstellensatz guarantees the existence of a certain polynomial identity $\sum_{i=1}^m \beta_i f_i = 1$ called a \emph{certificate}. The \emph{degree} of a certificate is the maximal degree of the $\beta_i$ and is related to the complexity of the underlying problem. For example, if a suitable encoding of a combinatorial problem gives constant degree bounds, then the problem is in P. In Chapter 2, we give a general method to encode a broad class of Ramsey-type problems, including the problems of computing Ramsey, Schur, and van der Waerden numbers, as systems of polynomial equations and construct Nullstellensatz certificates when they have no solution. The degrees of these certificates are given in terms of winning strategies of \emph{Builder-Painter games} which generalize the notion of the \emph{(restricted) online Ramsey numbers}. Additionally, the degrees are strictly smaller than those given by the best known general bounds for these ideals.

Later in Chapter 2 we study the classical Ramsey numbers through Alon's Combinatorial Nullstellensatz and construct ``Ramsey polynomials" that give lower bounds for Ramsey numbers when they are not identically zero. We call the coefficients of these polynomials \emph{ensemble numbers} and investigate their combinatorial meaning.

Our main contributions in Chapter \ref{ChapterRado} deal with computing \emph{Rado numbers}. Given an equation $\E$, the $k$-color Rado number $R_k(\E)$ is the smallest number $n$ such that every $k$-coloring of $\{1,2,\dots, n\}$ contains a monochromatic solution to $\E$. We encode the problem of computing Rado numbers as an instance of the \emph{Boolean satisfiability problem (SAT)} by constructing Boolean formulas $F_n^k(\E)$ that are satisfiable if and only if $R_k(\E) > n$. Using SAT solvers we determine hundreds of new Rado number values. We observe that many equations $\E$ have the property that not all the integers in $[n]$ are used in proving upper bounds $R_k(\E) \le n$. Moreover, for certain families of equations we can describe the integers that \emph{are} used using a single set of polynomials. We exploit this property and use a modified encoding to compute new values for \emph{infinite} families of three-color Rado numbers, namely formulas for $R_3(x-y = bz)$, $R_3(a(x-y) = (a-1)z)$ for $a\ge 3$, and $R_3(a(x-y) = bz)$ for $b \ge 1, a \ge b + 2, gcd(a, b) = 1$.

The \emph{degree of regularity} of an equation $\E$ is the largest number of colors $k$ for which $R_k(\E)$ is finite. We prove several new bounds on the degree of regularity for classes of linear equations, and using this we compute the degree of regularity of $ax+by = cz$ for small values of $a,b,$ and $c$. Moreover, we classify the degree of regularity for some equations of the form $a(x+y) = bz$; this improves on Rado's original result for the degree of regularity of these equations. Finally, we answer a conjecture of Golowich and show that for all $m,k \ge 3$ there are $m$-variable linear equations with degree of regularity at most $k$.

In Chapter \ref{ChapterDiffsequences}, we study the Ramsey properties of integer sequences. A \emph{$D$-diffsequence} is a sequence whose consecutive differences lie in a prescribed set $D$. We focus on the case where $D$ is the set $F$ of Fibonacci numbers. In particular, using combinatorial words and word morphisms, we construct a 4-coloring of $\Z^+$ that avoids 4-term $F$-diffsequences and a 2-coloring of $\Z^+$ that avoids 5-term arithmetic progressions with common difference in $F$. These colorings improve on the best known Ramsey results for the Fibonacci numbers. We also give some related results and experimental data on diffsequences involving Lucas and Perrin numbers.

Lastly, in Chapter \ref{ChapterAdditional} we show how our SAT methods can be applied to other combinatorial problems. Here we give new bounds and exact values for Ramsey numbers involving book and wheel graphs. Furthermore, we compute several exact values of \emph{Tur an numbers} for complete bipartite graphs and two-dimensional analogues of the \emph{Sidon-Ramsey numbers}. We also apply SAT solving to geometric problems involving angles in finite fields and compute maximal sizes of sets that avoid certain angles in $\mathbb{F}_q^n$.

The Appendix contains large tables of data, including a 3500-entry table of two-color Rado numbers and colorings of large sets of integers that avoid certain monochromatic sequences.