\documentclass[submission,shortlabels]{FPSAC2023}
\articlenumber{6}


\usepackage{diagbox,tikz}
\usepackage{mathtools}


\newtheorem{theorem}{Theorem}

\newtheorem{problem}[theorem]{Problem}

\newtheorem{lemma}[theorem]{Lemma}

\newtheorem{corollary}[theorem]{Corollary}

\newtheorem{remark}[theorem]{Remark}

\newtheorem{conjecture}[theorem]{Conjecture}

\newtheorem{proposition}[theorem]{Proposition}

\newtheorem{definition}[theorem]{Definition}

\newtheorem{question}[theorem]{Question}
\newtheorem{example}[theorem]{Example}
\newcounter{encoding}
\newtheorem{encoding}[encoding]{Encoding}
\renewcommand{\theencoding}{\Alph{encoding}}
\newcommand{\newproblem}[1]{\begin{problem}#1\end{problem}}

\newcommand{\N}{\mathbb{N}}

\newcommand{\Z}{\mathbb{Z}}

\newcommand{\Q}{\mathbb{Q}}

\newcommand{\R}{\mathbb{R}}

\newcommand{\C}{\mathbb{C}}

\newcommand{\A}{\mathbb{A}}

\newcommand{\inv}{^{-1}}

\newcommand{\del}{\partial}
\newcommand{\e}{\mathbf{e}}

\newcommand{\Ftwobar}{\overline{\mathbb{F}_2}}

\usepackage[backend=bibtex]{biblatex}
\addbibresource{RamseyDraft_v7.bib}

\begin{document}

\title{An Algebraic Perspective on Ramsey Numbers}

\author{Jes\'us A. De Loera\thanks{\href{mailto:deloera@math.ucdavis.edu}{deloera@math.ucdavis.edu}. }\addressmark{1} \and William J. Wesley\thanks{\href{mailto:wjwesley@math.ucdavis.edu}{wjwesley@math.ucdavis.edu}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of California, Davis}

%% put the date of submission here
\received{\today}

\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 $\bar{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. 
    %Finally, we introduce a family of numbers that relate to the coefficients of a certain "Ramsey polynomial" that gives lower bounds on the Ramsey numbers.
}

\keywords{Ramsey theory, Hilbert's Nullstellensatz, polynomial ideals.}

% \author[1]{Jes\'{u}s A. De Loera\thanks{deloera@math.ucdavis.edu} }\author[1]{William J. Wesley\thanks{wjwesley@math.ucdavis.edu}}
% \affil[1]{Department of Mathematics, University of California, Davis\\1 Shields Ave\\Davis, CA 95616}

\maketitle


\section{Introduction} 
Ramsey numbers are some of the most interesting and mysterious combinatorial numbers \cite{GrahamRothschildSpencer}. In its simplest, most popular form, the \textit{Ramsey number} $R(r,s)$ is the smallest positive integer $n$ such that every 2-coloring of the edges of $K_n$ contains a 
copy of $K_r$ in the first color or $K_s$ in the second color. Ramsey numbers can be generalized by allowing more than two colors and graphs other than $K_r$ and $K_s$. The number $R(G_1,G_2,\dots,G_k)$ is the smallest positive integer $n$ such that every $k$-coloring of the edges of $K_n$ contains a copy of $G_i$ in color $i$ for some $i$. If $G_i = K_{r_i}$ for all $i$, we simply write $R(r_1,r_2,\dots,r_k)$. All of these numbers are finite by Ramsey's theorem \cite{Ramsey}.  The goal of this article is to uncover further structure and complexity of Ramsey numbers through algebraic-geometric means. 

Our paper introduces algebraic interpretations of $R(r,s)$ and related numbers and graphs using polynomial ideals, varieties, and Nullstellensatz identities (see \cite{CoxLittleOShea} for an introduction). We tie the values and complexity of $R(r,s)$ to systems of  \emph{polynomial equations}. We show that these encodings give interesting information in the computational complexity of Ramsey numbers and Ramsey graphs. The precise models appear in \cref{PolynomialSection}. Before we state our main results, let us recall some relevant prior context and results:

Computing exact values for Ramsey numbers is a challenge. In fact there are only nine values of $R(r,s)$ with $3 \le r \le s$ whose exact values are known, and the only known nontrivial Ramsey numbers with more than two colors are $R(3,3,3) = 17$ and $R(3,3,4)$ = 30 \cite{R333Equals17,R334Equals30}. Ramsey numbers as small as $R(5,5)$ remain unknown, and the best known bounds are $43\le R(5,5) \le 48$. See \cite{ExooR55LowerBound,AngeltveitMcKayR55UpperBound}. The numbers $R(G_1,G_2)$ are known for some families of graphs, but many cases remain open (see, for example, \cite{RamseySurvey} for a survey of small Ramsey numbers and their best known bounds). The best known asymptotic lower and upper bounds for diagonal Ramsey numbers $R(s,s)$ are given in \cite{SpencerRamseyLB} and \cite{SahRamseyUB}, respectively. 

While we know in practice computing Ramsey numbers is extremely difficult (and considered harder than fighting a war with an alien civilization), it is not clear what is the appropriate computational complexity class to show hardness of computing Ramsey numbers $R(r,s)$. For example, the closely related \emph{arrowing decision problem} asks whether given three graphs $F, G, H$ is there is a red-blue edge-coloring of $F$ that contains neither a red $G$
 or a blue $H$? This decision problem was shown to be in co-NP for fixed choices of $G,H$ \cite{BurrRamseyComplexity}. Later Schaefer \cite{SchaeferRamseyComplexity} showed that in general it is in the polynomial hierarchy to answer this queries, but it is not clear what to do with this complexity question when $F,G,H$ are complete graphs $K_N,K_r,K_s$ because there is only one value $R(r,s)$ for each input $N,r,s$, hence it is not clear how it can be hard for any of the usual classes like NP. See details in \cite{SchaeferRamseyComplexity,BurrRamseyComplexity, Haanpaa00computationalmethods}.
 
 
 In recent years, Pak and collaborators \cite{PakComplexityEnumCombinatorics,Ikenmeyer+Pak,PakCombinatorialInterpretation} have proposed another way to measure complexity is by looking at counting sequences. We propose that their point of view could be another way to assert hardness of $R(r,s)$ by counting of Ramsey graphs: \emph{Ramsey $(r,s)$-graphs} are graphs with no red clique of size $r$, and no independent set of size $s$. Clearly, the number of vertices of a Ramsey $(r,s)$-graph is less than the Ramsey number $R(r,s)$. We are interested in the number of Ramsey $(r,s)$-graphs on $n$ vertices denoted by $RG(n,r,s)$. What is the complexity of counting the sequence of numbers $\{RG(n,r,s)\}_{n=1}^\infty$? From Ramsey's theorem this sequence consists of $R(r,s)-1$ positive numbers and then an infinite tail of zeroes. We give some examples of $RG(n,r,s)$ in the columns of the table below, which are computed using the \#SAT solver {\scshape relsat} \cite{Relsat}, following the work of successful computations in Ramsey theory using SAT solvers in, for example, \cite{SchurFive} and \cite{WJW_Rado_ISSAC} (see also the database at  \cite{McKayRamseyGraphs}). The hardness of $R(r,s)$ can then be rephrased as the question of whether the counting function  $RG(n,r,s)$ is in $\#P$. 
 

%  \textcolor{blue}{
%  For example, the sequence $a_n = RG(n,3,3)$ is $a_1 = 1, a_2 = 2, a_3 = 6, a_4 = 18, a_5 = 12$, and $a_n = 0$ for $n \ge 6$. The sequence $b_n = RG(n,3,4)$ is $b_1 = 1, b_2 = 2, b_3 = 7, b_4 = 40, b_5 = 322, b_6 = 2812, b_7 = 13842, b_8 = 17640$, and $b_n = 0$ for $n \ge 9$.  
{\small
 \begin{center}
 \begin{tabular}{c|c|c|c|c|c|c}
 $n$&$RG(n,3,3)$&$RG(n,3,4)$&$RG(n,3,5)$ & $RG(n,3,6)$ & $RG(n,3,7)$ & $RG(n,4,4)$\\
 \hline
     % 1 & 1 & 1 & 1 & 1 & 1 & 1\\
     2 & 2 & 2 & 2 & 2 & 2 & 2\\
     3 & 6 & 7 & 7 & 7 & 7 & 8 \\
     4 & 18 & 40 & 41 & 41 & 41 & 62\\
     5 & 12 & 322 & 387 & 388 & 388 & 892\\
     6 & 0 & 2812 & 5617 & 5788 &5789 & 22484\\
     7 & 0 & 13842 & 113949 & 133080 & 133500 & 923012\\
     8 & 0 & 17640 & 2728617 & 4569085 & 4681281 & 55881692
\\
     9 & 0 & 0 & 55650276 & 220280031 & 245743539 & 4319387624\\
 \end{tabular}
 \end{center}
} 
% \begin{theorem}\label{multipoly}
% The Ramsey number $R(r,s)$ is at most $n$ if and only if there is no solution to the following system over $\C$, where $K_n=(V,E)$ is the complete graph on $n$ vertices. Moreover, the number of solutions to this system is equal to the number of graphs of order $n$ that avoid copies of $K_r$ and $K_s$, namely the number of Ramsey graphs $RG(n,r,s)$.  

% \begin{align*}\prod_{e\in E(S)} x_e &=0 &&{\forall S\subseteq V,\ |S| = r,}\\  \prod_{e\in E(S)} (1-x_e) &= 0 && {\forall S\subseteq V,\ |S| = s,} \\
% x_e^2-x_e &=0 &&\forall e\in E.
% \end{align*}
% \end{theorem}

\subsection*{Our Contributions:}

In \cref{PolynomialSection}, we reintroduce the sequence $\{RG(n,r,s)\}_{n=1}^\infty$  as the number of solutions of certain zero-dimensional ideals over the polynomial ring $\overline{\mathbb{F}_2}[x_1,\dots,x_n].$ The solutions are indicator vectors that yield all Ramsey graphs (note, here they are not counted up to symmetry or automorphism classes). Some simple properties of $RG(n,r,s)$, such as the fact that $RG(n,r,s) \le RG(n,r+1,s)$, follow immediately from \cref{binEdge2}.

\begin{theorem}\label{binEdge2}
The Ramsey number $R(G_1,\dots,G_k)$ is at most $n$ if and only if there is no solution to the following system over $\overline{\mathbb{F}_2},$ where $K_n=(V,E)$ is the complete graph on $n$ vertices. Moreover, when the system has solutions, the number of solutions to this system is equal to the number of graphs of order $n$ that avoid copies of $G_i$ in color $i$. In particular, when $k=2$, $G_1 = K_r$, and $G_2 = K_s$, this is the number of Ramsey graphs $RG(n,r,s)$.
\begin{align} \label{thebest}
p_{H,i} := \prod_{e\in E(H)} x_{i,e} &=0 &&{\forall i, 1\le i \le k,\quad \forall  H\subseteq K_n,\ H \cong G_i},  \\
q_e := 1+\sum_{i=1}^k x_{i,e}&= 0 &&{\forall e \in E}, \\
u_{i,j,e} := x_{i,e}x_{j,e} & = 0 &&\forall e\in E,\ \forall i,j,\ i\neq j.
\end{align}

 When $k = 2$, $G_1 = K_r$, and $G_2 = K_s$, the \emph{Ramsey ideal} $RI(n,r,s)$ is ideal of the polynomial ring $\Ftwobar[ x_{1,e},x_{2,e}]_{e\in E(K_n)}$ generated by the polynomials $p_H$, $q_e$ and $u_{i,j,e}$. Then we have 
%  Note that 
% if $m \ge R(r,s)$, then we have $$ RI(1,r,s) \subseteq RI(2,r,s) \subseteq \dots \subseteq RI(m,r,s) = \left<1\right>.$$
% And that $RI(n,r,s)=\left<1\right>$ precisely when $n\geq R(r,s).$
$$RI(n,r,s) \supseteq RI(n,r+1,s) \supseteq  \dots \supseteq RI(n,n,s) \supseteq RI(n,n+1,s) = RI(n,n+2,s) = \dots$$
and 
$$RI(n,r,s) \supseteq RI(n,r,s+1) \supseteq  \dots \supseteq RI(n,r,n) \supseteq RI(n,r,n+1) = RI(n,r,n+2) = \dots$$
\end{theorem}

% \textcolor{blue}{***Addition to proof here; will move once we check/discuss the statements in the theorem***}

% The containments in the first chain follow from the fact that for every $n$, every subgraph $H$ of $K_n$ is also a subgraph of $K_{n+1}$. By Hilbert's Nullstellensatz, we have $RI(n,r,s) = \left<1\right>$ if and only if the generators of $RI(n,r,s)$ have no common zeroes if and only if $n\ge R(r,s)$. 


%In \cref{PolynomialSection} we also discuss two alternative ways of encoding the problem of finding Ramsey numbers using polynomials. 

% \begin{itemize}
%     \item polynomials
%     \item polyhedra, and
%     \item logical formulas.
% \end{itemize}

%We also encode the problem of computing the Ramsey number $R(r,s)$ as systems of polynomial equations in \cref{PolynomialSection}. For each $n$, the systems have no solution if and only if $R(r,s) \ge n$. 

A key interesting consequence of \cref{binEdge2} is that the very first value of $n$ for which the system of equations has no solution is equal to the Ramsey number. 
 One important result for our purposes is the famous \emph{Hilbert's Nullstellensatz}, which states that a system of polynomial equations $f_1 =\dots = f_m = 0$ over an algebraically closed field $K$ has no solution if and only if there exist coefficient polynomials $\beta_1,\dots,\beta_m$ such that \begin{equation}\label{NullCert}
\sum_{i=1}^m \beta_i f_i = 1.
\end{equation}

We call such an identity \eqref{NullCert} a \textit{Nullstellensatz certificate}. The \textit{degree} of a certificate is the largest degree of the polynomials $\beta_i$. Note that in our case the existence of a Nullstellensatz certificate is equivalent to an upper bound on the Ramsey number. The strong connection between combinatorial problems and the Hilbert Nullstellensatz has been investigated in, for example,  \cite{BussPitassi_InductionPrinciple,MarguliesOnnPasechnik_Nullstellensatz_Partition,deloera_lee_margulies_onn_2009,NulLA,NullstellensatzGrobnerChordal,DeLoeraLeeMalkinMargulies_computingInfeasibility_Nullstellensatz,LiLowensteinOmar,DeLoeraLeeMarguliesMiller_Matroids_Polynomials}. Here we show a surprising connection of Ramsey numbers to Nullstellensatz certificates.


In \cref{RamseyNullUpperBound} we give a general construction for Nullstellensatz certificates of Ramsey number upper bounds using the polynomial encoding from \cref{binEdge2}. In other words, assuming the number of vertices of a Ramsey ideal is $n$ and $n\ge R(G_1,\dots,G_k)$, we give upper bounds for the degrees of the Nullstellensatz certificates. Surprisingly our construction of 
Nullstellensatz certificates for the Ramsey ideals yields certificate degrees given by the \textit{restricted online Ramsey numbers} $\tilde{R}(G_1,\dots,G_k;n)$, first introduced by Conlon et al. in \cite{RestrictedOnlineRamseyNumbers_Conlon_et_al}. These numbers are defined in terms of the following \emph{Builder-Painter game}. Each turn Builder selects one edge $e$ of $K_n$, and Painter selects a color in $[k]$ and colors $e$ with this color. Builder wins the game once a monochromatic $G_i$ in color $i$ is constructed for some $i$. The number $\tilde{R}(G_1,\dots,G_k;n)$ is the minimum number of edges Builder needs to guarantee a victory. We also use the simplified notation $\tilde R(r_1,\dots,r_k;n)$ for $\tilde R(K_{r_1},\dots,K_{r_k};n)$. It is trivial that $\tilde R(G_1,\dots,G_k) \le \binom{R(G_1,\dots,G_k)}{2}$, but it was shown in \cite{RestrictedOnlineRamseyUpperBound} that in the case of 2-color classical Ramsey numbers that $\tilde R(r,r;n) \le \binom{n}{2}-\Omega(n\log n)$ for $n = R(r,r)$. While this degree bound is linear in the number of variables, $k\binom n 2$, it is an improvement over the upper bounds given in, for instance, \cite{Kollar,Lazard}.  

%it was shown in \cite{Conlon_Online_Ramsey} that the inequality $\tilde{R}(K_r,K_r)\le \binom{R(r,r)}{2}$ is strict for infinitely many $r$. More precisely, there is a constant $c > 1$ such that $\tilde R(K_r,K_r) \le c^{-r}\binom{R(r,r)}{2} $ for infinitely many $r$. However, it is still unknown whether $\lim_{r\to \infty} \frac{\tilde R(K_r,K_r)}{\binom{R(r,r)}2} = 0$. 

% \textcolor{red}{Make theorem 2 more general for non-complete graphs; make specific case of classical Ramsey 2-color; elucidate difference between restricted and nonrestricted versions; make notation more consistent with $R(r,s)$ and $\tilde R(r,s)$}

\begin{theorem}\label{RamseyNullUpperBound}
If $n\ge R(G_1,\dots,G_k)$, then there is an explicit Nullstellensatz certificate of degree $\tilde{R}(G_1,\dots, G_k;n)-1$ that the statement $R(G_1,\dots,G_k)> n$ is false using the encoding in \cref{binEdge2}. In particular, in the case of 2-color classical Ramsey numbers, this implies that if $n \ge R(r,s)$, then there exists a Nullstellensatz certificate of degree $\tilde R(r,s;n)-1$ that the statement $R(r,s) > n$ is false. 
\end{theorem}
\renewcommand{\P}{\mathcal P}
The proof of \cref{RamseyNullUpperBound} does not rely on the graph-theoretic properties of Ramsey numbers, and in fact it applies to the whole of Ramsey theory. In particular, we can modify the encoding in \cref{binEdge2} to suit several well-known problems in Ramsey theory (see, for example, \cite{GrahamRothschildSpencer,LandmanRobertson}). We express these problems using the general framework below. 

\begin{definition}
Let $k$ be a positive integer, and let $\{S_n\}$ be a sequence of sets. For $c$ in $[k]$, the set of colors, let $\P_n^c$ be a subset of $S_n$. A triple $A:= (\{S_n\},\{\P_n^c\};k)$ is a Ramsey-type problem if the following hold: 
\begin{enumerate}[(i)]
    \item $S_i \subseteq S_{i+1}$ for $i \ge 1$, 
    \item $\P^c_i \subseteq \P^c_{i+1}$ for $i \ge 1$, $1\le c \le k$,
    \item There exists an integer $N$ such that for all $i \ge N$ and every $k$-coloring of $S_i$ there is a color $c$ and some element $X \in \P^c_i$ where each element of $X$ is assigned color $c$. 
\end{enumerate}
The smallest such $N$ is called the Ramsey-type number for $A$, and is denoted $R(A)$.
\end{definition}

We see that in the problem of computing classical Ramsey numbers $R(r,s)$, we have $S_n = E(K_n) = \{ (i,j) : 1 \le i < j \le n\}$. The families $\P_n^1$ and $\P_n^2$ consist of all the sets of edges of induced subgraphs of $K_n$ containing $r$ and $s$ vertices, respectively. As another example, the problem of computing \emph{Schur numbers} asks for the smallest $n$ such that every $k$-coloring $[n]$ contains a monochromatic solution to the equation $x+y = z$. In this case we have $S_n = [n]$, and for all $c$ we have $\P_n^c = \{ \{x,y,z\} : \{x,y,z\} \subseteq [n], x+y = z\}$. 
% have an associated \emph{Ramsey-type} number where  For example, in finding lower bounds for the $k$-color Schur numbers $S(k)$, one asks for the largest $n$ where there is a $k$-coloring of $[n]$ that avoids monochromatic solutions to the equation $x+y = z$. 



% For example, the problem of computing Schur numbers asks for the smallest $n$ such that every $k$-coloring of $\{1,2,\dots, n\}$ has a monochromatic solution to the equation $x+y = z$. The problem of computing van der Waerden numbers asks for the smallest $n$ such that every $k$-coloring of $\{1,2,\dots,n\}$ contains a monochromatic arithmetic progression of a given length. In these cases $S_n = \{1,2,\dots, n\}$ and $\P$ is respectively the set of monochromatic solutions to $x+y=z$ with $x,y,z\in \{1,2,\dots,n\}$ and monochromatic arithmetic progressions (of a given length) in $\{1,2,\dots,n\}$.  

As we see in \cref{PolynomialSection}, the encoding in \cref{binEdge2} can be modified to give bounds for many other Ramsey-type numbers, including Schur, Rado, van der Waerden, and Hales--Jewett numbers \cite{GrahamRothschildSpencer,LandmanRobertson}. We can define numbers analogous to the restricted online Ramsey numbers for Ramsey-type problems in terms of another Builder-Painter game. We define this game for a fixed $n$ as follows.

% Let $S$ be a set of objects, let $k \ge 1$ be a positive integer, and let $\P$ be a family of partial $k$-colorings of $S$. If every $k$-coloring of $S$ contains an element of $\P$, we say that $\P$ is a $k$-\emph{Ramsey family} for $S$.

For each turn, Builder selects one object from $S_n$ and Painter assigns it a color in $[k]$. Builder wins once there is a color $c$ and an element $X \in \P_n^c$ where every element of $X$ is assigned color $c$. Define the number $\tilde R_k(\P_n^1,\dots, \P_n^k;S_n)$ to be the smallest number of turns for which Builder is guaranteed a victory. In this notation, the restricted online Ramsey number $\tilde R(r,s;n)$ is equal to $\tilde R_2(\P_n^1,\P_n^2;S_n)$  with $\P_n$ and $S_n$ defined as above for the Ramsey number $R(r,s)$. \cref{NullDegree_general_case} generalizes \cref{binEdge2,RamseyNullUpperBound}. 
% $\P:= \left( \left\{K_n[U] : U \in \binom{V(K_n)}{r}\right\}  \times \{1\} \right)  \cup \left( \left\{K_n[U] : U \in\binom{V(K_n)}{s}\right\} \times \{2\} \right) $,
\begin{theorem}\label{NullDegree_general_case}
    Let $A = (\{S_n\},\{\P^c_n\};k)$ be a Ramsey-type problem. Then for each $n$, the Ramsey-type number for $A$ is strictly greater than $n$ if and only if the following system of equations has no solution over $\Ftwobar$. 
\begin{align*} p_{X,c}:=\prod_{s \in X} x_{c,s} &=0 &&{\forall X \in \P_n^c},\  1\le c \le k  \\
q_s:=1+\sum_{i=1}^k x_{i,s}&= 0 &&{\forall s \in S_n}, \\
u_{i,j,s}:=x_{i,s}x_{j,s} & = 0 &&\forall s\in S_n,\ \forall i,j,\ 1\le i<j\le k.
\end{align*}
    
    If $n\ge R(A)$, then the minimal degree of a Nullstellensatz certificate for this system is at most $\tilde R_k(\P_n^1,\dots,\P_n^k;S_n) - 1$. Moreover, the number of solutions to this system is equal to the number of $k$-colorings of $S_n$ such that for every color $c$, each set $X \in \P_n^c$ contains an object that is not assigned color $c$. 
\end{theorem}

% \begin{theorem}\label{NullDegree_general_case}
%   Let $\{S_n\}$ be a family of finite sets, and let $k$ be a positive integer. Let $\P = \P_{n,k}$ be a family of partial $k$-colorings of $S_n$. There exists a system of polynomial equations that has no solution if and only if $\P$ is a $k$-Ramsey family for $S_n$. The degree of a minimal Nullstellensatz certificate for this system has degree at most $\tilde R_k(\P;S_n)-1$.
% \end{theorem}

For example, in the case of Schur numbers, the number of solutions to this system is exactly the number of $k$-colorings of $[n]$ that do not contain any monochromatic solutions to $x+y = z$. In \cref{PolynomialSection} we give some examples of values of $\tilde R(r,s;n)$ and $\tilde R(\P_n^1,\dots,\P_n^k;S_n)$ and discuss the Nullstellensatz certificates for the associated polynomial systems. 


\vskip .3cm
% Our second contribution is about  Alon's Combinatorial Nullstellensatz method.
% This is a popular technique where combinatorial problems are encoded by a single polynomial $f(x_1,\dots,x_n)$, and the combinatorial property of interest is true depending on whether $f$ vanishes or not at certain testing points. This approach has been used with great success in many situations (see, for example,  \cite{AlonCombinatorialNullstellensatz,GuthPolynomialMethod,ListColoringWithRequests,WongZhu_Graph23Choosable,KarolyiNagy_ProofOfZeilbergerBressoud,BrooksViaAlonTarsi,SauermannWigderson_PolynomialsMultiplicity} and the references therein). 

% Here we show that lower bounds for Ramsey numbers can be obtained by showing that a certain \emph{Ramsey polynomial} $f_{r,s,n}$ is not identically zero. Its coefficients are new combinatorial numbers $E_{n,k,r,H}$ which we call \emph{ensemble numbers}. We show that $E_{n,k,r,H}$ equals the number of ways to choose two distinct edges from $k$-tuples of $r$-cliques inside $K_n$ such that, every edge in a subgraph $H$ is chosen an odd number of times and every edge in its complement $\bar{H}$ is chosen an even number of times. We give a detailed example computing a value of $E_{n,k,r,H}$ in \cref{PolynomialSection}.  

% \usetikzlibrary{graphs,graphs.standard}


% \begin{tikzpicture}
%   \graph { subgraph K_n [n=5,clockwise,radius=2cm] };
% \end{tikzpicture}
% \end{document}

% \cref{CombinatorialNullstellensatzTheorem} shows that the numbers $E_{n,k,r,H}$ can be used to find lower bounds for the diagonal Ramsey number $R(r,r)$, and it is an analogue of Theorem 7.2 in \cite{AlonCombinatorialNullstellensatz}. 

% Using the Combinatorial Nullstellensatz of Alon \cite{AlonCombinatorialNullstellensatz}, we introduce combinatorial numbers $E_{n,k,r,H}$ that are related to the computation of Ramsey numbers. 

% \begin{theorem}\label{CombinatorialNullstellensatzTheorem}
% 	If $$\sum_{k \text{ odd}} 2^k \left(\binom{r}{2}^2-\binom{r}{2}\right)^{\binom{r}{2}-k} E_{n,k,r,H} \neq\sum_{k \text{ even}} 2^k \left(\binom{r}{2}-\binom{r}{2}^2\right)^{\binom{r}{2}-k} E_{n,k,r,H}$$ for some $H$, then $R(r,r)>n$. 
% \end{theorem}

%4
% In \cref{PolyhedraSection} we give encodings of the problem of determining $R(r,s)$ using systems of linear inequalities. We also discuss the \emph{cutting planes proof system}, which was introduced by Chv\'atal in \cite{ChvatalEdmonds,ChvatalCuttingPlaneProofs} following the study of cutting plane algorithms in integer programming by Gomory in \cite{GomoryOutlineOfAlgorithm}. The complexity of cutting planes proofs for the problem of determining $R(r,s)$ was studied in \cite{LauriaRamsey}. Here we study the complexity of cutting planes proofs for the related problem of determining the maximum number of edges in graphs that do not contain $(s+1)$-cliques. Recall that Tur\'an's theorem \cite{Turan} states that the maximum number of edges in any graph that does not contain a clique of size $s+1$ is at most $\left(1-\frac1s\right)
% \frac{n^2}2.$ The Tur\'an graph $T(n,s)$ contains the most edges among such graphs. In \cref{TuranCP} we analyze the cutting planes proof complexity of proving the bounds in Tur\'an's theorem. 
% \begin{theorem}\label{TuranCP}
% Let $V = [n]$, and let $T(n,s)$ denote the Tur\'{a}n graph. Using the initial inequalities \begin{align*}
%     \sum_{e\in \binom{S}{2}} x_e \le \binom{s+1}2 -1,\  \forall S\in \binom{V}{s+1},
% \end{align*}
% there is a cutting planes proof of rank $O(n)$ and length $O(n2^n)$ of the inequality $$\sum_{e\in \binom{V}{2} }x_e \le |E(T(n,s))|$$ for all $n\ge s+1$.
% \end{theorem}

% The Boolean satisfiability problem (SAT) is the problem of determining whether a Boolean formula has a satisfying assignment. Recently SAT solvers have been instrumental in solving difficult combinatorial problems such as Keller's conjecture and computing the Ramsey-type Schur numbers \cite{KellerConjecture,SchurFive}. Formulas encoding the problem of computing a Ramsey number are used as benchmarks for SAT solvers \cite{SATHandbook_1stEd}. In \cref{SATSolving} we extend this method to encode the problem of computing the general Ramsey numbers $R(G_1,G_2)$ as an instance of SAT. We produce formulas $\phi_{G_1,G_2,n}$ whose satisfying assignments correspond to 2-colorings of $K_n$ that do not contain a copy of $G_1$ in the first color or copy of $G_2$ in the second color. These satisfying assignments therefore certify the lower bound $R(G_1,G_2) > n$. It is also possible to certify the upper bounds $R(G_1,G_2) \le n$ through a SAT solver-produced proof of unsatisfiability of $\phi_{G_1,G_2,n}$ (see \cite{DRAT_and_Symmetry_breaking}).
% In general, showing a formula is unsatisfiable is more difficult than finding a satisfying assignment, and we did not compute any new upper bounds in this paper. However, our computations using SAT solvers yielded new lower bounds for Ramsey numbers involving the book graphs $B_n$ and wheel graphs $W_n$.  

% \begin{theorem}\label{SATSolvingBookWheelBounds} $R(B_4,B_5) = R(B_3,B_6) = 19$, $R(W_5,W_7) \ge 15.$
	
% \end{theorem}
% In \cref{Future Directions} we conclude with some open questions. 

\section{Ramsey and Hilbert's Nullstellensatz} \label{PolynomialSection}

% \subsection{Handelman Decompositions}
% Let $G = (V,E)$ be a graph on $n$ vertices. Assign the variable $x_e$ the value 1 if the edge $e$ is present in $G$, and 0 otherwise. Define \begin{equation}\label{frs}
% f_{r,s} :=\sum_{S\subseteq V, |S| = r}\prod_{e\in E(S)} x_e + \sum_{S\subseteq V, |S| = s}\prod_{e\in E(S)} (1-x_e).
% \end{equation} Then $f_{r,s}$ counts the number of cliques of size $r$ plus the number of independent sets of size $s$ in $G$. 

% The graphs of order $n$ correspond to the vertices of the hypercube $H_n:=[0,1]^{\binom n2}$. Therefore the Ramsey number $R(r,s)$ is the smallest $n$ such that the minimum of $f_{r,s}$ over the vertices $\{0,1\}^{\binom n2}$ is at least 1. In fact, since $f_{r,s}$ is multilinear, it is also harmonic, and by the maximum principle for harmonic functions, the minimum of $f$ is attained on the boundary of $[0,1]^{\binom n2}$. Moreover, by multilinearity, the minimum is attained at a point in $H_n$. {\color{red}[This is from https://mathoverflow.net/questions/210653/algorithms-for-calculating-r5-5-and-r6-6]}. Thus it suffices to certify that $f_{r,s} -1 \ge 0$ on $H_n$. 

% The following theorem due to Handelman shows that if a polynomial $g$ is strictly positive on a polytope $P$, then there exists a decomposition in terms of the inequalities that define $P$ that certifies the nonnegativity of $g$ on $P$. 

% \begin{theorem}[Handelman, \cite{Handelman}]
% 	Let $P = \{C_1\ge 0 ,\dots,C_k \ge 0\}$ be a polytope, where each inequality $C_i \ge 0$ is linear. Let $g(\mathbf{x})$ be a (strictly) positive polynomial on $P$. Then there is a finite subset $\mathcal I \subset \N^k$ such that $$g(\mathbf x) = \sum_{(i_1,\dots,i_k) \in \mathcal I} \lambda_{(i_1,\dots,i_k)} C_1^{i_1}\cdots C_k^{i_k},$$ where $\lambda_{(i_1,\dots,i_k)} >0$. 
% \end{theorem}
% We call such an identity a \textit{Handelman decomposition}, and we let $d = \max_{\mathcal I} \sum_{j=1}^k i_j$ be the \text{degree} of the decomposition. The following algorithm gives a procedure to compute Handelman decompositions: 

% Initially set $d = 1$, and let $P = \{C_1\ge 0 ,\dots,C_k \ge 0\}$. 

% Step 1: Write $$g(\mathbf{x}) = \sum_{(i_1,\dots,i_k): \sum_{j=1}^k i_j \le d} \lambda_{(i_1,\dots,i_k)} C_1^{i_1}\cdots C_k^{i_k}.$$


% Step 2: Expand each side and extract a system of equations by comparing the coefficients of the monomials with variables in $x_1,\dots, x_n$



% Step 3: Add the constraints $\lambda_{(i_1,\dots,i_k)} \ge 0$ and solve the resulting linear program. 


% Step 4: If the LP is infeasible, increment $d$ and repeat steps 1-4. 


% The inequalities $\{x_e\ge 0, 1-x_e \ge 0\}_{e\in \binom{[n]}{2}}$ define $H_n$. The following proposition describes a decomposition using these inequalties that certifies the positivity of $f_{r,2}$ on $H_r$. 

% \begin{proposition}
% 	For $|V| = \binom r 2 = R(r,2)$, there exists a Handelman decomposition that certifies $f_{r,2} - 1 \ge 0$ on $H_r$ with $d = \binom r2$. 
% \end{proposition}
% \begin{proof}
% 	Let $n = \binom r2$, and label the edge variables $x_1, \dots, x_{n}$.
% 	%	S_1 = \sum_{j=2}^n(1-x_1)(1-x_j)$, $S_2 = \sum_{j=3}^n x_1(1-x_2)(1-x_j)$,$\dots, 
	
% 	Define $S_k = \sum_{j = k+1}^n \left(\prod_{i=1}^{k-1} x_i\right) (1-x_k)(1-x_j)$.
	
% 	We claim that 
% 	$\sum_{k=1}^\ell S_k = n-1 - \sum_{i=1}^n x_i + \left(\prod_{i=1}^{\ell} x_i\right)(\ell+1-n+\sum_{i=\ell+1}^n x_i)$ by induction. The base case is clear. For the inductive step we have 
% 	\begin{align*}
% 	\sum_{k=1}^{\ell+1} S_k &= n-1 - \sum_{i=1}^n x_i + \left(\prod_{i=1}^{\ell} x_i\right)(\ell+1-n+\sum_{i=\ell+1}^n x_i) + \sum_{j = \ell+2}^n \left(\prod_{i=1}^{\ell} x_i\right) 
% 	(1-x_{\ell+1})(1-x_j) \\ 
% 	&= n-1 - \sum_{i=1}^n x_i + \left(\prod_{i=1}^{\ell} x_i\right)(\ell+1-n+x_{\ell+1}+\sum_{i=\ell+2}^n (x_i+(1-x_{\ell+1})(1-x_i)) ) \\
% 	&= n-1 - \sum_{i=1}^n x_i + \left(\prod_{i=1}^{\ell} x_i\right)(x_{\ell+1}-x_{\ell+1}\sum_{i=\ell+2}^n (1-x_i) ) \\
% 	&= n-1 - \sum_{i=1}^n x_i + \left(\prod_{i=1}^{\ell} x_i\right)(x_{\ell+1}-x_{\ell+1}\sum_{i=\ell+2}^n (1-x_i) ) \\
% 	&= n-1 - \sum_{i=1}^n x_i + \left(\prod_{i=1}^{\ell+1} x_i\right)(\ell+2-n+\sum_{i=\ell+2}^n x_i ) \\
% 	\end{align*}
% 	as desired. 
% 	Then $\sum_{k=1}^{n-1}S_k = f_{r,2} -1$. 
% \end{proof}

% Attempts to compute a decomposition (using SCIP) that certifies $f_{3,3} -1\ge 0$ failed for $d=3,4$. Attempts with $d=5$ failed due to lack of memory. 

% \subsection{ Sums of squares methods}
% A polynomial $p(x)$ is a \textit{sum of squares} if it can be written $p(x) = \sum_{i=1}^k q_i(x)^2$ for some polynomials $q_i(x)$. Such an identity is a certificate of the nonnegativity of $p$. Therefore if $f_{r,s} -\epsilon$ can be written as a sum of squares for any $\epsilon>0$, then we have $R(r,s) \ge N$. 

% For each $N$, we wish to find an optimal lower bound for $f_{r,s}$ over the hypercube. In other words, we wish to solve the following problem:

% \begin{align*}
% &\text{minimize } f_{r,s}(x) \\
% &\text{subject to } 0\le x_e\le 1 & \forall e\in E.
% \end{align*} 
% The SOSTOOLS MATLAB package attempts to find a decomposition of the form $$f_{r,s} - \epsilon = \sigma_0(x) + \sum_{i} \sigma_i(x) g_i(x) + \sum_{i_1,i_2} \sigma_{i_1,i_2}(x)g_{i_1}(x)g_{i_2}(x)+\cdots$$ where the $\sigma_j$ are sums of squares and the $g_j$ are the inequalities that define the hypercube. Maximizing $\epsilon$ gives a lower bound for $f_{r,s}$ over the hypercube. 

% We obtained the lower bound $f_{3,3}\ge 1.25$ on the hypercube $\{0,1\}^{\binom62}$, which shows $R(3,3)\le 6$. 

% TO BE FINISHED.

In this section we give several encodings of the problem of finding an upper bound for $R(r,s)$ in terms of the feasibility of a system of polynomial equations.  In the simplest version of the encoding, the variables correspond to edges in the graph $K_n$, and the solutions of the system correspond to graph colorings that avoid monochromatic copies of $K_r$ and $K_s$. If the system is infeasible for some $n$, then no such coloring exists, hence $R(r,s) \le n$. 

%The corresponding Nullstellensatz therefore certifies this upper bound.
% We use polynomials to encode $R(r,s)$ using 


Many combinatorial problems can be encoded as a system of polynomial equations, including colorings, independence sets, partitions, etc. (see, e.g., \cite{BussPitassi_InductionPrinciple,BayerThesis,DeLoera_GrobnerBasesGraphColorings,deloera_lee_margulies_onn_2009, NullstellensatzGrobnerChordal,HillarWindfeldt,Lovasz_StableSetsAndPolynomials,MarguliesOnnPasechnik_Nullstellensatz_Partition}).
A Nullstellensatz certificate for such a combinatorial polynomial system is therefore a proof that a combinatorial theorem is true. We are interested on bounding the Nullstellensatz degree for our Ramsey systems.

There are known general ``algebraic geometers'' upper bounds for the degree of a Nullstellensatz certificate, so the above procedure terminates, even when these bounds are exponential and sharp in general \cite{Kollar}. 
However, the exponential bounds should not be bad news for combinatorialists. 
First, it has been shown \cite{Lazard} that for ``combinatorial ideals", the bounds are much better, linear in the number of variables. Over finite fields there are degree bounds that are independent of the number of variables \cite{GreenTao_PolynomialsFiniteFields}, and a recent paper \cite{MoshkowitzYu_FiniteFieldNullstellensatz} gives substantial improvements to these bounds. The bounds we give in \cref{RamseyNullUpperBound,NullDegree_general_case} for our systems of equations are better than the above bounds. Moreover, it has been documented that in practice the degrees of Nullstellensatz certificates of NP-hard problems (e.g., non-3-colorability), tend to be small ``in practice" (see, for example, \cite{MarguliesThesis,LiLowensteinOmar,DeLoeraLeeMalkinMargulies_computingInfeasibility_Nullstellensatz} and the references therein), especially when the polynomial encodings are over finite fields. Note also that when we know the degree of the Nullstellensatz certificate, one can compute explicit coefficients of the Nullstellensatz certificate using a linear algebra system derived by equating the monomials of the identity. This has been exploited in practical computation with great success, see \cite{NulLA,DeLoeraLeeMalkinMargulies_computingInfeasibility_Nullstellensatz,LiLowensteinOmar}. 



% \begin{lemma}\label{Null1Poly}
% We have $R(r,s) \le N$ if and only if there is no solution to the following system over $\C$, where $K_N=(V,E)$ is the complete graph on $N$ vertices:

% \begin{align*}\sum_{S\subseteq V, |S| = r}\prod_{e\in E(S)} x_e + \sum_{S\subseteq V, |S| = s}\prod_{e\in E(S)} (1-x_e) &= 0 \\
% x_e^2-x_e &=0 \quad\forall e\in E
% \end{align*}
% \end{lemma}
% The following proposition gives lower bounds for the degree of a certificate of $R(r,r)\ge N$.
% \begin{proposition}
% 	The degree of a Nullstellensatz certificate using Proposition \ref{Null1Poly} for $R(r,r)\ge N$ is at least $\binom r2$ if $r$ is even and $r>2$. 
% \end{proposition}

% \begin{proof}Denote a hypothetical certificate of degree $d$ by \begin{equation}\label{bigEq}\left(c_0+\sum_{k= 1}^d\sum_{\mathbf{e}\in E^k} c_{\mathbf e}x_{\mathbf e}\right)P(r,s) + \sum_{e\in E} \left(b^e_0+\sum_{k=1}^d\sum_{\mathbf e \in E^k}b^e_{\mathbf e}x_{\mathbf{e}}\right)(x_e^2-x_e)=1\end{equation}
% {\color{red} Note $E^k$ isn't strictly correct; want to disregard order}

% Let $[x_\e]$ denote the coefficient of $x_\e$, and note that $[1] = 1$, and $[x_\e] = 0$ for all $\e$. Suppose $d = \binom r2-1$. We claim that $c_\e = 0$ for all $\e$. 

% Suppose $\e \in E^d$. Now consider $\mathbf{f} \in E^{\binom r2}$ that represents a clique whose vertices are disjoint from the vertices in $\e$ Then the only way to obtain the variable $x_\e x_\mathbf{f}$ on the LHS of \ref{bigEq} by multiplying $c_\e x_\e$ and the $x_\mathbf{f}$ from $P(r,s)$. Then $c_\e = [x_\e x_\mathbf{f}] = 0$. Now we may apply this argument iteratively to show that $c_\e = 0$ for $\e \in E^{d-1}, \dots, E^2, E.$

% Now, since all the $c_\e = 0$, we observe that for all $e$, we have $[x_e^{\binom r2 +1}] = b^e_{e^d}$ and $[x_e^k] = b^e_{e^{k-2}} - b^e_{e^{k-1}}$ for $2\le k \le \binom{r}{2}$. This implies that $b^e_{e^k} = 0$ for $k \ge 2$. Now we have that $[x_e] = -\binom {N-2}{r-2} c_0$, so $c_0 = 0$. But we have $ \binom r 2c_0 = [1] =1$, a contradiction. 
% \end{proof}

% The following proposition modifies the encoding in Lemma \ref{Null1Poly}, increasing the number of equations in the system, but possibly lowering the degrees of certificates. 

We now prove \cref{binEdge2} of our encoding for Ramsey numbers over $\Ftwobar$ below. 

\begin{proof}[Proof of \cref{binEdge2}]
Suppose there is a solution $\mathbf{x}$ to the system over $\Ftwobar$. For each edge $e$ of $K_n$ and each color $i$, the system has a variable $x_{i,e}$. The polynomials $u_{i,j,e}$ guarantee that for a given $e$, at most one variable $x_{i,e}$ is nonzero. From the polynomials $q_e$, we then see that exactly one index $i$ such that $x_{i,e} = 1$, and let $\phi(\textbf{x})$ be the coloring $\chi$ where $\chi(e)$ is this index. Color each edge $e$ of $K_n$ with the color $\chi(e)$. In the equations involving the polynomials $p_H$, for each subgraph $H$ of $K_n$ with $H \cong G_i$, there is at least one edge $e$ in $H$ with $x_{i,e} = 0$. Therefore $\chi(e) \neq i$, so there is no monochromatic copy of $G_i$ in color $i$. 

Conversely, if we have a coloring $\chi$ of the edges of $K_n$ with no monochromatic $G_i$ in color $i$, then let $\psi(\chi)$ be the solution $\textbf{x}$ where $x_{i,e}$ is 1 if $\chi(e) = i$ and 0 otherwise. One can check easily that $\textbf{x}$ satisfies the system of equations. 
The maps $\phi$ and $\psi$ are inverses of each other, and so the number of solutions to the system is equal to the number of colorings of $K_n$ with no monochromatic $G_i$ in color $i$.  

For the first chain of ideals, observe that for a fixed $i$, the polynomial $\prod_{e\in E(H)}x_{i,e}$ divides $\prod_{e\in E(H')}x_{i,e}$ if and only if $H$ is a subgraph of $H'$. Since every copy of $K_{r+1}$ in $K_n$ contains a copy of $K_r$ as a subgraph, in the ideal $RI(n,r+1,s)$, every polynomial of the form $\prod_{e\in E(H')}x_{i,e}$ with $H' \cong K_{r+1}$ is divisible by a generator $\prod_{e\in E(H)}x_{i,e}$ of $RI(n,r,s)$ with $H \cong K_r$. The ideals in the chain are equal for $r > n$ since in this case $K_r$ is not a subgraph of $K_n$. The proof for the second chain of ideals is similar. 
\end{proof}


% \begin{proof}[Proof of \cref{multipoly}]
% The system has one variable $x_e$ for each edge $e$ in $K_n$. The equations $x_e^2-x_e = 0$ force each variable to take on values in $\{0,1\}$. A variable $x_e$ taking on the value 1 corresponds to the edge $e$ being present in a graph, and $x_e$ taking on the value 0 corresponds to $e$ being absent. The first set of equations forces that in any subgraph on $r$ vertices, at least one edge $e$ in that subgraph must have $x_e$ = 0, i.e., there are no cliques of size $r$. Similarly, the second set of equations guarantees that there are no independent sets of size $s$. Therefore the solutions to the above system correspond to the graphs that do not contain a $K_r$ or a $\overline{K_s}$.
% \end{proof}

% {\bf NOW WE DO WE CALL THEM RAMSEY IDEALS, please adjust...MOVED CHAIN TO BE PART THEOREM 1 ADJUST PROOF OF THEOREM 1}

% \textcolor{blue}{I don't know where to put this since we don't really mention these ideals again}
% \textcolor{red}{For fixed integers $m,n,r,$ and $s$ with $m \ge n$, we let $I_n(r,s)$ be the ideal of the polynomial ring $R[x_1,\dots, x_m]$ generated by the polynomials in Encoding  \ref{multipoly}. If $m \ge R(r,s)$, then we have $$ I_1(r,s) \subseteq I_2(r,s) \subseteq \dots \subseteq I_m(r,s) = \<1\>.$$}


Before we prove \cref{RamseyNullUpperBound}, we show a special case as a warm-up example. There is a simple certificate of the fact that $R(r,2) \le r$. 


\begin{example} \label{nullR2}
	For all $r$, there exists a Nullstellensatz certificate of degree $\binom r2 -1$ of the statement $R(r,2)\le r$. 
\end{example}
\begin{proof}
	Label the edges of $K_r$ from 1 to $n = \binom{r}{2}$. The following identity is a certificate that $R(r,2)\le r$. Polynomials in parentheses are part of the system of equations in \cref{binEdge2}.	
% 	$$1 = 1(1-x_1)+x_1(1-x_2)+x_1x_2(1-x_3)+\cdots +x_1\cdots x_{n-1}(1-x_n)+x_1\cdots x_n .$$
	\begin{align*} 1 &= (1+x_{1,1}+x_{2,1})+x_{1,1}(1+x_{1,2}+x_{2,2})+x_{1,1}x_{1,2}(1+x_{1,3}+x_{2,3})+\dots\\ &\quad+x_{1,1}x_{1,2}\cdots x_{1,n-1}(1+x_{1,n}+x_{2,n})\\
	&\quad+x_{2,1}+x_{1,1}(x_{2,2})+x_{1,1}x_{1,2}(x_{2,3})+\dots+x_{1,1}x_{1,2}\cdots x_{1,n-1}(x_{2,n})\\&\quad+(x_{1,1}\cdots x_{1,n}) \qedhere
	\end{align*}
\end{proof}
% We remark that Encoding \ref{multipoly} also works over $\overline{\mathbb{F}_2}$, and in this case we do not need the equations $x_e^2-x_e = 0$. The certificate in Example \ref{nullR2} is also a certificate over $\overline{\mathbb{F}_2}$.

% We attempted to compute minimal degree Nullstellensatz certificates for Ramsey numbers using the NulLA algorithm and Encoding \ref{multipoly}. We were able to compute a degree 4 certificate using the encoding over $\C$ and a degree 3 certificate using the encoding over $\overline{\mathbb{F}_2}$ for the statement $R(3,3)\le 6$. We were unsuccessful in computing certificates for larger nontrivial Ramsey numbers. 


% \subsection{Roots of unity edge coloring encoding}
% We have $R(r,s) \le N$ if and only if there is no solution to the following system over $\C$, where $K_N=(V,E)$ is the complete graph on $N$ vertices:

% \begin{align*} \prod_{e\in E(S)} (x_e-1) &=0 &&{\forall S\subseteq V, |S| = r}\\  \prod_{e\in E(S)} (x_e+1) &= 0 && {\forall S\subseteq V, |S| = s} \\
% x_e^2-1 &= 0 &&{\forall e \in E}
% \end{align*}

% This generalizes to an arbitrary number of colors in the following way: $R(r_1,r_2,\dots, r_k)\le N$ if and only if there is no solution to the following system over $\C$, where $K_N=(V,E)$ is the complete graph on $N$ vertices and $\zeta_k$ is a primitive $k$-th root of unity:

% \begin{align*} \prod_{e\in E(S)} (x_e-\zeta_k^i) &=0 &&{\forall S\subseteq V, |S| = r_i, 1\le i\le k}\\  
% x_e^k-1 &= 0 &&{\forall e \in E}
% \end{align*}


 
% \begin{encoding}\label{binEdge} The Ramsey number $R(r_1,\dots,r_k)$ is at most $n$ if and only if there is no solution to the following system over $\overline{\mathbb{F}_2},$ where $K_n=(V,E)$ is the complete graph on $n$ vertices:

% \begin{align*} \prod_{e\in E(S)} x_{i,e} &=0 &&{\forall i, 1\le i \le k,\quad \forall S\subseteq V,\ |S| = r_i},  \\
% 1+\sum_{i=1}^k x_{i,e}&= 0 &&{\forall e \in E}, \\
% x_{i,e}x_{j,e} & = 0 &&\forall e\in E,\ \forall i,j,\ 1\le i<j\le k.
% \end{align*}

% \end{encoding}
% In this encoding, coloring an edge with color $i$ corresponds to setting $x_{i,e} = 1$. The last two sets of equations guarantee that for each edge $e$, there is precisely one $i$ such that $x_{i,e} = 1$. The last set of equations in Encoding \ref{binEdge} is not strictly necessary for the statement of the encoding, but these equations ensure that solutions to the system of equations correspond to graphs that avoid cliques of size $r_i$ in color $i$. Encoding \ref{binEdge} can be generalized to encode the Ramsey numbers $R(G_1,\dots,G_k)$. 

% \begin{encoding}\label{binEdge2}
% The Ramsey number $R(G_1,\dots,G_k)$ is at most $n$ if and only if there is no solution to the following system over $\overline{\mathbb{F}_2},$ where $K_n=(V,E)$ is the complete graph on $n$ vertices:

% \begin{align*} \prod_{e\in E(H)} x_{i,e} &=0 &&{\forall i, 1\le i \le k,\quad \forall H\subseteq K_n,\ H \cong G_i},  \\
% 1+\sum_{i=1}^k x_{i,e}&= 0 &&{\forall e \in E}, \\
% x_{i,e}x_{j,e} & = 0 &&\forall e\in E, \forall i,j, 1\le i<j\le k.
% \end{align*}

% \end{encoding}
In the proof of \cref{RamseyNullUpperBound}, we show how to translate a strategy for Builder into a Nullstellensatz certificate. This method can be used to construct a certificate for all (known) upper bounds for $R(G_1,\dots,G_s)$. Notably, better strategies for Builder yield lower degree certificates. In \cref{nullR2}, this is not a concern since the order in which Builder selects edges does not matter, and in fact $\tilde R(r,2;r) = \binom{r}2$. Painter simply colors every edge Builder selects the first color, and Builder wins when all $\binom r 2$ edges are selected. 
% The idea behind Example \ref{nullR2} is that we can consider edges in a fixed order, and begin constructing a candidate certificate with the polynomial $1+x_{1,1}+x_{2,1}$. The term $x_{2,1}$ can be canceled out immediately since it is part of the original system of equations. To cancel out $x_{1,1}$, we can add the polynomial $x_{1,1}(1+x_{1,2}+x_{2,2})$, and then we have the ``leftover terms" $x_{1,1}x_{1,2}+x_{1,1}x_{2,2}$. We can cancel out $x_{1,1}x_{2,2}$ since it is divisible by $x_{2,2}$, a polynomial in the system of equations, and then cancel $x_{1,1}x_{1,2}$ by adding $x_{1,1}x_{1,2}(1+x_{1,3}+x_{2,3})$, and so on. We can generalize this procedure to the systems for $R(G_1,\dots,G_k)$. Begin constructing a certificate with the polynomial $1+\sum_{i=1}^k x_{i,e_1}$ for an initial edge $e_1$. Consider edges in order, and cancel any nonconstant terms by multiplying them with the polynomial $1+\sum_{i=1}^k x_{i,e}$ for the next edge $e$. Once all of the edges have been considered, after simplifying we obtain a polynomial whose nonconstant terms correspond to the edge $k$-colorings of $K_n$. If $n \ge R(G_1,\dots,G_k)$, then each of these terms is divisible by an original polynomial in the system, and can be canceled. The resulting Nullstellensatz certificate has degree $\binom{n}2-1$. 

  The proofs of \cref{RamseyNullUpperBound,NullDegree_general_case} are similar, and in fact \cref{RamseyNullUpperBound} follows from \cref{NullDegree_general_case}, but for the sake of concreteness we begin with \cref{RamseyNullUpperBound}. 


% \begin{proof}
% 	Number the edges in $K_n$ from 1 to $\binom{n}{2}$. For every edge $j$, let $s_j = 1+\sum_{i=1}^kx_{i,j}$. Each $s_j$ is one of the equations in Encoding \ref{binEdge}. Let $t_1 = s_1$, and recursively define $t_{m+1} :=t_m+ (t_m-1)s_{m+1}.$ It follows by induction that \begin{equation}t_{m} = 1+ \sum_{i_1,\dots,i_m\in [k]} \prod_{j=1}^m x_{i_j,j}.\label{tm equation}\end{equation}
% 	Note that $t_m$ is a polynomial of degree $m$. The $k^m$ nonconstant monomials in $t_m$ correspond to the $k^m$ ways to $k$-color the edges $1$ to $m$. Fix $m = \binom{n}{2}$, and let $U$ be the set of nonconstant monomials of $t_m$. Since $n\ge R(r_1,\dots,r_k)$, every $k$-coloring of $K_n$ contains a monochromatic clique, so every term $u\in U$ is divisible by some product $p_u$ of the form $\prod_{e\in E(S)} x_{i,e}$ from the first set of equations in Lemma \ref{binEdge}. Then we have
	
% 	\begin{equation}\label{finalCertificate} t_m + \sum_{u\in U} \left(\frac{u}{p_u}\right) p_u = 1.
% 	\end{equation}
	
% 	Since $t_m$ is a sum of the $s_j$, \eqref{finalCertificate} is a Nullstellensatz certificate of degree $\binom{n}{2}-1$. 
% \end{proof}


\begin{proof}[Proof of \cref{RamseyNullUpperBound}]
% For each subset $S\subset V$ and color $i\in [k]$, let $g_{S,i} := \prod_{e\in E(S)} x_{i,e}$. For each edge $e$ of $K_n$, let $h_e = 1+\sum_{i=1}^k x_{i,e}$. Number the edges of $K_n$ from 1 to $\binom{n}{2}$. We will construct polynomials $p_t$ whose nonconstant monomials correspond to possible states of the game between Builder and Painter.

% Suppose, without loss of generality, that Builder selects edge 1 first. Let $p_1 = h_1$. The monomials $x_{i,1}, 1\le i\le k$ correspond to Painter's $k$ choices for coloring edge 1.     

% Recursively define $p_{j+1}$ as follows: If $p_j$ has a nonconstant monomial $m$, if $m$ corresponds to a coloring that contains some monochromatic clique $S$ in color $i$, then $g_{S,i}$ divides $m$, and set $p_{j+1}:= p_j + \left(\frac{m}{g_{S,i}}\right)g_{S,i}$. Otherwise, let $e$ be the next edge Builder should select in an optimal strategy, and set $p_{j+1}:=p_j + mh_e.$ 

% If $p_j$ does not have a nonconstant monomial $m$, then $p_j = 1$, and by construction $p_j$ is a sum of multiples of the $g_{S,i}$ and $h_e$, which are polynomials in the system of equations in Encoding \ref{binEdge}. Therefore the procedure that constructed $p_j$ gives a Nullstellensatz certificate. Since $p_j$ was constructed by following Builder's optimal strategy at each step, the maximal degree of the polynomials $\{p_1,\dots,p_j\}$ is $\tilde{R}(K_1,\dots, K_k;n)$, and so the degree of this certificate is $\tilde{R}(K_1,\dots, K_k;n) -1$.
% \end{proof}
% {\color{blue} We label the polynomials in Encoding \ref{binEdge} as follows. For each subset $S\subseteq V$ and color $i\in [k]$, let $g_{S,i} := \prod_{e\in E(S)} x_{i,e}$. For each edge $e$ of $K_n$, let $h_e = 1+\sum_{i=1}^k x_{i,e}$. Number the edges of $K_n$ from 1 to $\binom{n}{2}$. We will describe an algorithm to construct a Nullstellensatz certificate of the form 
% \begin{equation}\label{Thm2Cert}\sum_{i=1}^k \sum_{S\in \binom{V}{r_i}} \beta_{S,i}g_{S,i} +\sum_{e\in E} \gamma_e h_e = 1. 
% \end{equation}

% Let $d:= \tilde R(K_1,\dots,K_k;n)$. Suppose Builder selects the edge $e_1$ first. Initialize $\beta_{S,i}$ to 0 for all $S$ and $i$, and initialize $\gamma_e$ to 0 for all edges $e$ except $e_1$, and set $\gamma_{e_1} := 1$. 

% Let $A$ be the set of all possible states of the game between Builder and Player where Builder selects edge $e_1$ first. Each state in $A$ is a set of edge-color pairs that Builder has selected and Painter has colored. For example, $\{(e_1,1),(e_3,2),(e_6,3),(e_8,2)\} \in A$. For each state $a\in A$, define $\phi(a)$ to be the monomial $\prod_{(e,c) \in a} x_{c,e}$. 

% A game $t$ between Builder and Player is a sequence $(e_{i_1},c_1),\dots,(e_{i_m},c_m)$ of edges $e_{i_j}$ selected by Builder and colors $c_j$ selected by Painter. Let $t_j = \{(e_{i_1},c_1),\dots,(e_{i_j},c_j)\}\in A$ denote the game state after the first $j$ turns.  Let $T$ be the set of all possible games where Builder selects $e_1$ first and follows an optimal strategy. Without loss of generality, we may suppose $e_{i_1} = e_1$ for all games in $T$. If Builder is following an optimal strategy, then $m\le d$. For each game $t$ in $T$ do the following: For $1\le j \le m-1$, set $\gamma_{e_{i_{j+1}}}\gets  \gamma_{e_{i_{j+1}}}+\phi(t_j).$ Let $S$ denote the set of vertices in the monochromatic clique formed at the end of $t$, and let $c$ be the color of this clique. Then $g_{S,c}$ divides $\phi(t_m)$, and set $\beta_{S,c} \gets \beta_{S,c} + \frac{\phi(t_m)}{g_{S,c}}$. 

% We claim that this procedure results in a Nullstellensatz certificate. Consider the expression that results after expanding each $\beta_{S,i}g_{S,i}$ and $\gamma_e h_e$ in the left-hand side of the equation \ref{Thm2Cert} (without any further cancellation or simplification). Each term in this expression is either 

% \begin{enumerate}[i)]
%     \item The constant 1. 
%      \item A nonconstant term resulting from multiplying a monomial $\phi(t_j)$ in $\gamma_e$ and a variable $x_{i,e}$ in $h_e$, for some $e$.
%     \item A nonconstant term resulting from multiplying a monomial $\phi(t_j)$ in $\gamma_e$ and the 1 in $h_e$, for some $e$.
%     \item A nonconstant term resulting from multiplying a monomial in some $\beta_{S,i}$ with $g_{S,i}$. 
% \end{enumerate}

% If a monomial $p$ is of type ii), then it can be written $\phi(t_j)x_{i,e}$, and it is of the form $\phi(t'_{j+1})$ for some game $t'$. If $t'_{j+1}$ is not the final game state, then by the above procedure, $\phi(t'_{j+1})$ is a summand of $\gamma_{e_{i_{j+2}}}$. Therefore $p$ is canceled by a corresponding monomial $p' = \phi(t'_{j+1})\cdot 1  = p$ of type iii). Otherwise, $t'_{j+1}$ is the final game state, and $p$ is divisible by $g_{S,i}$ for some $S$ and $i$. Then $p$ will be canceled by a monomial $p' = \frac{\phi(t'_{j+1})}{g_{S,i}}\cdot g_{S,i} = p$ of type iv).
% }

%  Label the polynomials in Encoding \ref{binEdge2} as follows. For each subgraph $H\subseteq G$ and color $i\in [k]$, let $p_{H,i} := \prod_{e\in E(H)} x_{i,e}$. For each edge $e$ of $K_n$, let $q_e = 1+\sum_{i=1}^k x_{i,e}$. 

Number the edges of $K_n$ from 1 to $\binom{n}{2}$. A $t$-turn game state $g$ is a set $\{(e_{i_1},c_1),(e_{i_2},c_2),\dots,(e_{i_t},c_t)\}$ of pairs of edges $e_{i_j}\in E$ chosen by Builder and colors $c_j\in [k]$ chosen by Painter. A game is complete if there is some color $c \in [k]$ where Painter has colored a monochromatic $G_c$ in color $c$. Let $d:= \tilde R(G_1,\dots,G_k;n)$. If Builder follows an optimal strategy for choosing edges, then the game lasts at most $d$ turns, that is $t\le d$. 

For a $t$-turn game state $g$, define the monomial $\pi(g)$ to be $\pi(g):= \prod_{j=1}^t x_{c_j,e_{i_j}}.$ Similarly, for any monomial  $f = \prod_{j=1}^t x_{c_j,e_{i_j}}$ with distinct $e_{i_j}$, let $\sigma(f)$ denote the game state $\{(e_{i_1},c_1),(e_{i_2},c_2),\dots,(e_{i_t},c_t)\}$. We will describe an algorithm to construct a Nullstellensatz certificate of the form 
\begin{equation}\label{Thm2Cert}\sum_{i=1}^k \sum_{H \cong G_i} \beta_{H,i}p_{H,i} +\sum_{e\in E} \gamma_e q_e = 1. 
\end{equation}

Denote the left-hand side of \cref{Thm2Cert} by $L$. For each $i \in [k]$, initialize $\beta_{H,i}$ to 0 for all $H \cong G_i$. Initialize $\gamma_e$ to 0 for all edges $e$ except $e_1$, and set $\gamma_{e_1} := 1$. Then repeat the following:

\begin{enumerate}
    \item Expand and simplify $L$ so that $L$ is a sum of monomials. If $L = 1$, then we are done. Otherwise, at least one term in $L$ is a nonconstant monomial $f$. 
    \item If $\sigma(f)$ is a completed game state, then $p_{H,i}$ divides $f$ for some color $i$ and $H \cong G_i$. Then set $\beta_{H,i} \gets \beta_{H,i}+\frac{f}{p_{H,i}}.$ This results in $L\gets L+f$, which cancels the original $f$ in the certificate since it is an expression over $\Ftwobar$, which has characteristic 2.
    \item If $\sigma(f)$ is not a completed game state, then let $e$ be an edge that Builder should choose in an optimal strategy from the game state $\sigma(f)$. Set $\gamma_{e}\gets \gamma_{e} + f.$ Since $fq_e = f+\sum_{i=1}^k fx_{i,e}$, we obtain $L\gets L+f+\sum_{i=1}^k fx_{i,e}$. This results in the cancellation of $f$ in $L$, but adds $k$ additional terms (one for each of Painter's $k$ choices for coloring $e$) to $L$. Note that if $\sigma(f)$ is a $t$-turn game state, then $\sigma(fx_{i,e})$ is a $(t+1)$-turn game state for all $i$.  
\end{enumerate}
By the symmetry of $K_n$, it is arbitrary which edge Builder selects first. Therefore each nonconstant term that appears in $L$ corresponds to a game state where Builder (but not necessarily Painter) has followed an optimal strategy. Since terms that correspond to completed games are cancelled out in step 3, this procedure terminates, resulting in a Nullstellensatz certificate. Because Builder follows an optimal strategy, the maximal degree of any term in any $\gamma_e$ is $d-1$, so the degree of the certificate is $d-1$. 
\end{proof}

 To illustrate the importance of Builder's strategy in this method, observe that one can construct a degree 7 certificate for the statement $R(3,3)\le 6$ using the following strategy: For the first five turns, Builder selects each edge incident to some vertex $v$. No matter how Painter colors these edges, three must be colored the same color. Call these edges $vw_1,vw_2,vw_3$. For the next three turns, Builder selects the edges $w_1w_2,w_1w_3$, and $w_2w_3$, and Painter must construct a monochromatic triangle. However, if Builder plays poorly and selects, for example, the edges \sloppy{$(1,2),(2,3),(3,4),(4,5),(5,6),(1,6),(1,4),(2,5),$ and $(3,6)$}, then no matter what Painter does there are \emph{no} monochromatic triangles, and this leads to a higher degree certificate.
 
 The proof of \cref{RamseyNullUpperBound} shows that the polynomials can ``simulate" a tree of Builder-Painter games. However, in general the degrees of certificates can be strictly smaller than the bounds given in \cref{RamseyNullUpperBound}. For example, by a computational search, it can be shown that $\tilde R(3,3;6) = 8$. However, there exists a Nullstellensatz certificate of degree 5 using the encoding in \cref{binEdge2}, which is better than the bound given in \cref{RamseyNullUpperBound}. 
Due to space constraints we skip  the proof of \cref{NullDegree_general_case} but it can be found in \cite{WJW_JDL_RamseyNullstellensatz}.

% \begin{proof}[Proof of \cref{NullDegree_general_case}]
% Let $A=(\{S_n\}, \{\P_n^c\};k)$ be a Ramsey-type problem. 
% A $t$-turn game state $g$ after $t$ is a set $\{(s_{i_1},c_1),(s_{i_2},c_2),\dots,(s_{i_t},c_t)\}$ of objects $s \in S_n$ chosen by Builder and colors $c_j\in [k]$ chosen by Painter. A game is complete if there is a color $c \in [k]$ and some element $X \in \P_n^c$ where Painter has colored all the elements of $X$ color $c$. Let $d:= \tilde R_k(\P_n;S_n)$. If Builder follows an optimal strategy for choosing edges, then the game lasts at most $d$ turns, that is $t\le d$.

% For a game state $g_t$, define the monomial $\pi(g_t)$ to be $$\pi(g_t):= \prod_{j=1}^t x_{c_j,s_{i_j}}.$$ Similarly, for any monomial  $f = \prod_{j=1}^t x_{c_j,s_{i_j}}$ with distinct $s_{i_j}$, let $\sigma(f)$ denote the game state $\{(s_{i_1},c_1),(s_{i_2},c_2),\dots,(s_{i_t},c_t)\}$. 

% We will describe an algorithm to construct a Nullstellensatz certificate of the form 
% \begin{equation}\label{Thm2CertGeneral}\sum_{(X,c) \in \P_n} \beta_{X,c}p_{X,c} +\sum_{s\in S_n} \gamma_s q_s = 1. 
% \end{equation}

% Denote the left-hand side of Equation \ref{Thm2CertGeneral} by $L$. Initialize $\beta_{X,c}$ to 0 for all $(X,c) \in \P_n$. Let $s^*$ be an object that Builder selects first in an optimal strategy. Initialize $\gamma_{s^*}$ to 1 and $\gamma_s$ to 0 for all other $s \in S_n$. Then repeat the following:

% \begin{enumerate}
%     \item Expand and simplify $L$ so that $L$ is a sum of monomials. If $L = 1$, then we are done.
%     \item Otherwise, at least one term in $L$ is a nonconstant monomial $f$. 
%     \item If $\sigma(f)$ is a completed game state, then $p_{X,c}$ divides $f$ for some $(X,c) \in \P_n$. Then set $$\beta_{X,c} \gets \beta_{X,c}+\frac{f}{p_{X,c}}.$$ This results in $L\gets L+f$, which cancels the original $f$ in the certificate since it is an expression over $\Ftwobar$, which has characteristic 2.
%     \item If $\sigma(f)$ is not a completed game state, then let $s$ be an object that Builder should choose in an optimal strategy from the game state $\sigma(f)$. Set $$\gamma_{s}\gets \gamma_{s} + f .$$ Since $fq_s = f+\sum_{i=1}^k fx_{i,s}$, we obtain $L\gets L+f+\sum_{i=1}^k fx_{i,e}$. This results in the cancellation of $f$ in $L$, but adds $k$ additional terms (one for each of Painter's $k$ choices for coloring $s$) to $L$. Note that if $\sigma(f)$ is a $t$-turn game state, then $\sigma(fx_{i,s})$ is a $(t+1)$-turn game state for all $i$.  
% \end{enumerate}
% For each nonconstant monomial $f$ that appears in $L$, its corresponding game state $\sigma(L)$ is one where Builder (but not necessarily Painter) has followed an optimal strategy.  Since terms that correspond to completed games are cancelled out in step 3, this procedure terminates and results in a Nullstellensatz certificate. Because Builder follows an optimal strategy, the maximal degree of any term in any $\gamma_s$ is at most $d-1$, so the degree of the certificate is at most $d-1$. 
% \end{proof}


As an application of \cref{NullDegree_general_case}, let $\mathcal{E}$ be a linear equation, and let $R_k(\mathcal E)$ denote the $k$-color \emph{Rado number} for $\mathcal E$, the smallest $n$ such that every $k$-coloring of $[n]$ contains a monochromatic solution to $\mathcal E$. Let $X_{n,\mathcal E}$ be the set of all solutions over $[n]$ to $\mathcal E$. Let $\P_n^c := X_{n,\mathcal E}$ for all $c$. If $R_k(\mathcal E)$ exists, then $(\{[n]\},\{\P_n^c\};k)$ is a Ramsey-type problem, and we have the following corollary. 

\begin{corollary} \label{Corollary_BuilderPainter}
Let $\mathcal E$ be the linear equation $\sum_{j=1}^t a_i y_i = a_0 $ with a finite Rado number $R_k(\mathcal E)$. Let $X_{n,\mathcal E} = \{(m_1,\dots, m_t): \sum_{j=1}^t a_j m_j = a_0,\ 1\le m_j \le n \}$ be the set of solutions over $[n]$ to $\mathcal E$. Then for every $n$, the following system has no solution over $\Ftwobar$ if and only if $n \ge R_k(\mathcal E)$. 
\begin{align*}
   \prod_{j=1}^t x_{i,m_j} &= 0 & \forall (m_1,\dots, m_t) \in X_{n,\mathcal E},\ 1\le i \le k,\\
   1+ \sum_{i=1}^k x_{i,m} &= 0 & 1\le m \le n, \\
   x_{i,m}x_{j,m} & = 0 & 1 \le m \le n , 1\le i < j \le k. 
\end{align*}

The degree of a minimal Nullstellensatz certificate for this system has degree at most $\tilde R_k(X_{n,\mathcal E},\dots,X_{n,\mathcal E};[n])-1.$
\end{corollary}

As an example, let $\mathcal E$ denote the equation $x+3y = 3z$, and let $X_{9,\mathcal E}$ be the solutions to $\mathcal E$ over $[9]$ as above. It is known that  $R_2(\mathcal E) = 9$ \cite{LandmanRobertson}. However, Builder can select, in order, the integers 4,6,9,3, and 7 to win the Builder-Painter game in at most 5 turns: since $(6,4,6)$ is a solution, 4 and 6 must be different colors, and then since $(9,6,9)$ and $(3,3,4)$ are solutions, 4 and 9 must be one color and 3 and 6 are the other color. But then $(3,6,7)$ and $(9,4,7)$ are solutions, so there is a monochromatic solution no matter which color Painter selects for 7. Therefore $\tilde R_2(X_{9,\mathcal E},X_{9,\mathcal E};[9]) \le 5$, and the minimal degree of a Nullstellensatz certificate for the system of equations in \cref{Corollary_BuilderPainter} is at most 4. In fact, some computations show the minimal degree is 2.

Similarly, the encoding in \cref{binEdge2} for the Schur number $S(2) = R_2(x+y=z)$ also gives an example of Nullstellensatz certificates that are smaller than the ones given by games. It is well-known that $S(2) = 5$, and from the encoding in \cref{NullDegree_general_case}, we have $S(2) \le 5$ if and only if the following system of equations has no solutions over $\Ftwobar$.
\begin{align*}
    &1+x_{1,i}+x_{2,i} = 0, &&1\le i \le 5, \\
    &\hspace{18pt} \begin{aligned}
    x_{i,1}x_{i,2} &= 0,   &&\hspace{17pt}x_{i,2}x_{i,4} = 0,\\ 
    x_{i,1}x_{i,3}x_{i,4}&= 0,   &&x_{i,1}x_{i,4}x_{i,5}= 0, \ \ x_{i,2}x_{i,3}x_{i,5} = 0. \\
    \\
    \end{aligned}&&\left.\begin{aligned} \\ \\  \end{aligned} \right\rbrace
   i = 1,2
 \end{align*}

% \begin{align*}
%     &1+x_{1,i}+x_{2,i} = 0, &&1\le i \le 5, \\
%     &\hspace{18pt} \begin{aligned}
%     x_{i,1}x_{i,2} &= 0, && \\
%     x_{i,1}x_{i,3}x_{i,4}&= 0, \\
%     x_{i,1}x_{i,4}x_{i,5}&= 0,\\
%     x_{i,2}x_{i,4} &= 0,\\
%     x_{i,2}x_{i,3}x_{i,5} &= 0.\\
%     \end{aligned}&&\left.\begin{aligned} \\ \\ \\ \\ \\\end{aligned} \right\rbrace
%   i = 1,2
%  \end{align*}

A computer search shows that the number $\tilde R_2(X_{5,x+y=z},X_{5,x+y=z};[5]) = 5$, where $X_{5,x+y=z}$ is the set of positive integer solutions to $x+y= z$ in $[1,5]$. We computed a degree 3 Nullstellensatz certificate for the above system of equations, which is an improvement on the bound in \cref{NullDegree_general_case}. We omit the certificate here for space considerations, but it can be found in \cite{WJW_JDL_RamseyNullstellensatz}. Moreover, by \cref{NullDegree_general_case} there are similar consequences for van der Waerden numbers, Hales--Jewett numbers, and essentially any other  Ramsey-type quantity. We are unable to include them here due to space, but we invite readers to see more in \cite{WJW_JDL_RamseyNullstellensatz}.

% {The \emph{van der Waerden number} $w(t,k)$ is the smallest $n$ such that every $k$-coloring of $[n]$ contains a monochromatic $t$-term arithmetic progression \cite{GrahamRothschildSpencer}. Let $AP_{n,t}$ denote the set of all $t$-term arithmetic progressions in $[n]$. Then setting $\P_n^c := AP_{n,t}$ for all $c$, then  $(\{[n]\},\{\P_n^c\};k)$ is a Ramsey-type problem as well. 



% \begin{corollary}
% For every $n$, the following system has no solution over $\Ftwobar$ if and only if $n \ge w(t,k)$. 
% \begin{align*}
%   \prod_{j=1}^t x_{i,m_j} &= 0 & \forall (m_1,\dots, m_t) \in AP_{n,t},\ 1\le i \le k,\\
%   1+ \sum_{i=1}^k x_{i,m} &= 0 & 1\le m \le n, \\
%   x_{i,m}x_{j,m} & = 0 & 1 \le m \le n , 1\le i < j \le k. 
% \end{align*}

% The minimal degree of a Nullstellensatz certificate for this system is at most $$\tilde R_r(AP_{n,k},\dots,AP_{n,k};[n])-1.$$
% The number of solutions to this system is the number of $k$-colorings of $[n]$ that contain no $t$-term monochromatic arithmetic progressions. 
% \end{corollary}
% We give one last consequence of \cref{NullDegree_general_case}. For fixed parameters $t$ and $n$, a \emph{combinatorial line} is a sequence of points $v^1,\dots, v^t$, where $v^i \in [t]^n$ such that for every coordinate $j$, the sequence $(v^i_j)_{i=1}^t$ is either constant or $v^i_j = i$ for all $i$. The \emph{Hales--Jewett number $HJ(t,k)$} is the smallest number $n$ such that every $k$-coloring of $[t]^n$ contains a monochromatic combinatorial line \cite{GrahamRothschildSpencer}. Let $L_{t,n}$ denote the set of all combinatorial lines on $t^n$. If we set $\P_n^c = L_{t,n}$ for all $c$, then $(\{[t]^n,\{\P_n^c\};k)$ is a Ramsey-type problem. 

% \begin{corollary}
% For every $n$, the following system has no solution over $\Ftwobar$ if and only if $n \ge HJ(t,k)$. 
% \begin{align*}
%   \prod_{j=1}^t x_{i,v^j} &= 0 & \forall (v^1,\dots, v^t) \in L_{t,n},\ 1\le i \le k,\\
%   1+ \sum_{i=1}^k x_{i,v} &= 0 & v\in [t]^n, \\
%   x_{i,v}x_{j,v} & = 0 & v\in[t]^n , 1\le i < j \le k.
% \end{align*}
% The number of solutions to this system is the number of $k$-colorings of $[t]^n$ that do not contain any monochromatic combinatorial lines. 
% \end{corollary}





%If Builder follows the strategy of first selecting 5 edges incident to some vertex $v$, then three edges $vw_1,vw_2,vw_3$ must be the same color. Then Builder can select the edges $w_1w_2,w_1w_3$, and $w_2w_3$, and Painter must color a monochromatic triangle, so $\tilde R(3,3;6)\le 8$. To show that $\tilde R(3,3;6) \ge 8$, we need to show that Painter has a strategy to prevent Builder from winning in 7 or fewer turns. Consider the following strategy: for each edge $e$ selected by Builder, Painter colors $e$ red unless one of the following cases occurs: 

%\begin{itemize}
%    \item Coloring $e$ red creates a red triangle.
%    \item Coloring $e$ red creates a vertex $v$ with red degree at least 3 and Builder can win in at most 7 turns total by selecting edges between the red neighbors of $v$.
%    \item Coloring $e$ red creates an induced copy of $C_4$ where two adjacent edges are colored red and the others are colored blue. 
%\end{itemize}
%An exhaustive search of all possible orders Builder can select 7 edges of $K_6$ %confirms this strategy prevents Builder from winning in 7 turns. 
%\textcolor{blue}{Should we make this a theorem?} 




% These examples illustrate that the Nullstellensatz is in fact more powerful than the Builder-Painter game. Indeed, we can interpret this additional power combinatorially in terms of yet another game, which we call \textcolor{red}{[maybe there's a better name?]} the multiple instances Builder game. 

% Fix a number of colors $k$, a set of objects $S$, and a subset $\P$ of the partial $k$-colorings of $S$. Unlike the Builder-Painter game, the multiple instances Builder game has only one player, Builder. Builder has a \emph{collection} $\mathcal C$ of games (here a game is defined to be a partial $k$-coloring of $S$), and wins by constructing a partial coloring from $\P$ for each $G\in \mathcal C$. Builder can modify $\mathcal C$ by the following operations:

% \begin{itemize}
%     \item \textbf{Coloring:}  Select a game $G$ from $\mathcal C$, then select an uncolored object $s \in S$. Then $G$ is replaced by $k$ games $G_i,\dots,G_k$, whose colored objects are identical to those in $G$, except that $s$ is assigned color $i$. 
%     \item \textbf{Uncoloring:} Select games $G_1,\dots, G_k$ whose objects are identically colored except for one object $s$, which is assigned color $i$ in $G_i$. Builder may then replace $G_1,\dots,G_k$ with the game $G$ where $s$ is uncolored. 
%     \item \textbf{Switching:}  Select a game $G$ and object $s$ assigned color $i$. Builder may replace $G$ by the games $G_0, G_1,\dots, G_{\hat i},\dots, G_k$, where $G_j$ is the game identical to $G$ where $s$ is assigned color $j$ if $1\le j \le k$ and uncolored if $j = 0$. 
%     \item \textbf{Removal: }If a game $G$ contains a partial coloring in $\P$, then Builder may remove it from $\mathcal C$. 
%     \item \textbf{Duplicate Elimination:} If two distinct games $G$ and $G'$ are identical, then Builder may remove them both from $\mathcal C$. 
% \end{itemize}
% These operations correspond to the polynomial operations that can be done to construct a Nullstellensatz certificate. An upper bound for the degree of this certificate is the maximum number of edges colored in any game removed from $\mathcal C$. 
% Suppose Builder and Painter are following an optimal strategy and Builder selects a sequence of edges $e_1,\dots, e_{d}$ and Painter selects a sequence of colors $c_1,\dots,c_d$. 
%% This proof needs to be rewritten

% Using a similar idea, we can prove a simple lower bound for the degree of a certificate using the encoding in Lemma \ref{binEdge}. 
% \begin{proposition}
% 	The degree of any certificate for $R(r,s)\ge N$ using the encoding in Lemma \ref{binEdge} is at least $\binom{\min\{r_1,\dots,r_k\}}{2}-1$.
% \end{proposition}

% \begin{proof}
% 	Since 1 must appear in a certificate, we must have a polynomial $1+\sum_{i=1}^kx_{i,e_1}$. The only way to eliminate $x_{1,e}$ is to multiply $x_{1,e}$ by another polynomial $1+\sum_{i=1}^kx_{i,e_1}$ and add. We must eventually ``cancel" a monochromatic clique in the sum, and this requires a certificate of degree at least $\binom{\min\{r_1,\dots,r_k\}}{2}-1$. 
% \end{proof}


% In general, if $n$ objects are being colored, then a Nullstellensatz certificate of degree $n-1$ is sufficient to enumerate all possible colorings in a ``coloring polynomial". Then if $n$ is large enough, each nonconstant term $t$ in the coloring polynomial will be divisible by a monomial $m$ in the original system of equations, and so these terms may be easily canceled out by adding the term $(t/m)m$ to the certificate. 

% \section{Ramsey and Alon's Combinatorial Nullstellensatz}\label{section_CN}

% In this section we introduce a way to encode the problem of finding a lower bound for $R(r,s)$ in terms of properties of a single polynomial. We also define a family of numbers $E_{n,k,r,H}$ whose values can provide bounds for $R(r,r)$. The following theorem of Alon, the ``Combinatorial Nullstellensatz," has been used to solve many problems in combinatorics and graph theory (see, for example, \cite{AlonCombinatorialNullstellensatz,ListColoringWithRequests,BrooksViaAlonTarsi,GuthPolynomialMethod,WongZhu_Graph23Choosable,KarolyiNagy_ProofOfZeilbergerBressoud} and the references therein). 
% \begin{theorem}[Alon, \cite{AlonCombinatorialNullstellensatz}] \label{CN}
% 	Let $F$ be a field, and let $f\in F[x_1,\dots,x_n]$. Let $\deg(f) = \sum_{i=1}^n t_i$ with each $t_i$ a nonnegative integer, and suppose the coefficient of $\prod_{i=1}^n x_i^{t_i}$ is nonzero. Then if $S_1,\dots, S_n$ are subsets of $F$ with $|S_i|>t_i$, then there exist $s_1\in S_1, \dots, s_n \in S_n$ such that $f(s_1,\dots, s_n) \neq 0$.
% \end{theorem}
% Here we apply the Combinatorial Nullstellensatz to show that lower bounds for Ramsey numbers can be obtained by showing that a certain polynomial is not identically zero. Consider the following polynomial, where $K_n = (V,E)$ is the complete graph on $n$ vertices:

% \begin{equation}\label{CNPoly}
% f(x) = f_{r,s,n}(x)= \left(\prod_{S\subset V,\ |S| = r} \left(\sum_{e\in E(S)} x_e -\binom{r}{2}\right)\right) \left(\prod_{S\subset V,\ |S| = s} \left(\sum_{e\in E(S)} x_e +\binom{s}{2}\right)\right).
% \end{equation}

% Every 2-coloring of the edges of $G$ corresponds to an assignment $c:\{x_e\}_{e\in E} \to \{-1,1\}$. If an edge $e$ is colored with the first color, then we set $c(x_e) =1$, and if $e$ is colored with the second color, then $c(x_e) = -1$. Then $f(c(x)) = 0$ if and only if $G$ contains an $r$-clique in the first color or an $s$-clique in the second color. Therefore if $f(c(x_1),\dots,c(x_{|E|})) = 0$ for all colorings $c$, then $R(r,s)\le n$. 

% Since we only consider the values of $f$ on $\{-1,1\}^{|E|},$ we may instead consider the multilinear representative of $f$ in the ideal $\left< x_e^2-1\right>_{e\in E}$. This representative can be obtained by deleting each variable with an even exponent from each term in $f$. By \cref{CN}, this representative is the zero polynomial if and only if $R(r,s) \le |V|$.


% In the proof of \cref{CombinatorialNullstellensatzTheorem}, we focus on the case when $r=s$ and study the polynomial $f_{r,r,n}$. Before proving \cref{CombinatorialNullstellensatzTheorem}, we give an example of a value of an ensemble number $E_{n,k,r,H}$, which are coefficients of the multilinear representative of $f_{r,r,n}$. We recall the definition of $E_{n,k,r,H}$ below. 

% We call a collection of $k$ $r$-cliques a \emph{$(k,r)$-ensemble}. For each clique in the ensemble, we select exactly two edges, and if each edge in $H$ is selected an odd number of times and each edge of $\bar H$ is selected an odd number of times, then we call this a \emph{valid covering} of a subgraph $H$. The ensemble number $E_{n,k,r,H}$ is the total number of valid coverings of $H$ counted from all $(k,r)$-ensembles of $K_n$.

% If $H$ is the graph on five vertices with edge set $\{(1,2),(1,5)\}$, then $E_{5,3,3,H} = 8.$ The figure below depicts all eight ways.  Each graph has an associated $(3,3)$-ensemble $\mathcal{E}$, and each 3-clique in $\mathcal{E}$ is assigned a distinct color $c\in \{\text{red,green,blue}\}$. The two edges from that 3-clique are colored $c$. Edges colored with more than one color are drawn as multiple edges. In the upper left figure, for example, the associated ensemble is $\{\{1,2,3\},\{1,3,4\},\{1,4,5\}$. The edges $(1,2)$ and $(1,3)$ were chosen from the clique $\{1,2,3\}$, the edges $(1,3)$ and $(1,4)$ were chosen from the clique $\{1,3,4\}$, and the edges $(1,4)$ and $(1,5)$ were chosen from the clique $\{1,4,5\}$. The edges of $H$ are chosen exactly once, and all other edges are chosen zero or two times. Note that for some $(3,3)$-ensembles, such as $\{\{1,2,3\},\{1,2,4\},\{3,4,5\}\}$, it is impossible to choose edges in $H$ an odd number of times. 

%possibly move to section w/thm
%explain why some triangles don't work/include example 
%add caption to explain which triangles are chosen 


% Suppose $C_4$ has the edge set $\{(1,2),(2,3),(3,4),(1,4)\}$. One way to cover each of these edges exactly once is by choosing the cliques $\{1,2,3\}$ and $\{1,3,4\}$ in $K_n$ and the edges $(1,2)$ and $(2,3)$ from the first clique and $(3,4)$ and $(1,4)$ from the second clique. The other way is to choose the cliques $\{1,2,4\}$ and $\{2,3,4\}$ and the edges $(1,2)$ and $(1,4)$ from the first clique and the edges $(2,3)$ and $(3,4)$ from the second clique (see diagram below).

% \begin{center}
% 	\begin{tikzpicture}

% \node at (-1.25,1.25) {1};
% \node at (1.25,1.25) {2};
% \node at (1.25,-1.25) {3};
% \node at (-1.25,-1.25) {4};


% \draw[red][thick] (-1,1)--(1,1); 
% \draw[red][thick] (-1,-1)--(-1,1);
% \draw[blue][thick] (1,1)--(1,-1);
% \draw[blue][thick] (-1,-1)--(1,-1);
% \draw[fill=black] (-1,1) circle (2pt); 
% \draw[fill=black] (1,1) circle (2pt);
% \draw[fill=black] (-1,-1) circle (2pt);
% \draw[fill=black] (1,-1) circle (2pt);


% \begin{scope}[shift={(5,0)}]
	
% 	\node at (-1.25,1.25) {1};
% 	\node at (1.25,1.25) {2};
% 	\node at (1.25,-1.25) {3};
% 	\node at (-1.25,-1.25) {4};
	
	
% 	\draw[blue][thick] (-1,1)--(1,1); 
% 	\draw[red][thick] (-1,-1)--(-1,1);
% 	\draw[blue][thick] (1,1)--(1,-1);
% 	\draw[red][thick] (-1,-1)--(1,-1);
% 	\draw[fill=black] (-1,1) circle (2pt); 
% 	\draw[fill=black] (1,1) circle (2pt);
% 	\draw[fill=black] (-1,-1) circle (2pt);
% 	\draw[fill=black] (1,-1) circle (2pt);
% \end{scope}
% 	\end{tikzpicture}
% \end{center}

% \usetikzlibrary{shapes.geometric}
% \begin{center}
% \begin{tikzpicture}[mystyle/.style={draw,shape=circle,fill=none},scale = 0.85]
% \def\ngon{5}
% \node[regular polygon,regular polygon sides=\ngon,minimum size=3cm] (p) {};
% \foreach\x in {1,...,\ngon}{\node[mystyle] (p\x) at (p.corner \x){\x};}
% \foreach\x in {1,...,\numexpr\ngon-1\relax}{
%   \foreach\y in {\x,...,\ngon}{
%     %\draw (p\x) -- (p\y);
%   }
% }
% \draw [blue,transform canvas={xshift=1.5pt}] (p1) -- (p4); 
% \draw [red, transform canvas={xshift=-1.5pt}] (p1) -- (p4);
% \draw [blue] (p1) -- (p5); 
% \draw [red, transform canvas={xshift=+1.5pt}] (p1) -- (p3);
% \draw [green] (p1) -- (p2); 
% \draw [green, transform canvas={xshift=-1.5pt}] (p1) -- (p3);

% \begin{scope}[shift ={(5,0)}]
% \def\ngon{5}
% \node[regular polygon,regular polygon sides=\ngon,minimum size=3cm] (p) {};
% \foreach\x in {1,...,\ngon}{\node[mystyle] (p\x) at (p.corner \x){\x};}
% \foreach\x in {1,...,\numexpr\ngon-1\relax}{
%   \foreach\y in {\x,...,\ngon}{
%     %\draw (p\x) -- (p\y);
%   }
% }
% \draw [blue,transform canvas={xshift=-1.5pt}] (p1) -- (p3); 
% \draw [red, transform canvas={xshift=-1.5pt}] (p1) -- (p4);
% \draw [blue] (p1) -- (p5); 
% \draw [red, transform canvas={xshift=+1.5pt}] (p1) -- (p3);
% \draw [green] (p1) -- (p2); 
% \draw [green, transform canvas={xshift=1.5pt}] (p1) -- (p4);
% \end{scope}
% \begin{scope}[shift ={(10,0)}]
% \def\ngon{5}
% \node[regular polygon,regular polygon sides=\ngon,minimum size=3cm] (p) {};
% \foreach\x in {1,...,\ngon}{\node[mystyle] (p\x) at (p.corner \x){\x};}
% \foreach\x in {1,...,\numexpr\ngon-1\relax}{
%   \foreach\y in {\x,...,\ngon}{
%     %\draw (p\x) -- (p\y);
%   }
% }
% \draw [blue,transform canvas={xshift=1.5pt}] (p5) -- (p3); 

% \draw [blue] (p1) -- (p5); 
% \draw [red, transform canvas={xshift=-1.5pt}] (p5) -- (p3);
% \draw [red, transform canvas={xshift=1.5pt}] (p2) -- (p3);
% \draw [green] (p1) -- (p2); 
% \draw [green, transform canvas={xshift=-1.5pt}] (p2) -- (p3);
% \end{scope}


% \begin{scope}[shift ={(15,0)}]
% \def\ngon{5}
% \node[regular polygon,regular polygon sides=\ngon,minimum size=3cm] (p) {};
% \foreach\x in {1,...,\ngon}{\node[mystyle] (p\x) at (p.corner \x){\x};}
% \foreach\x in {1,...,\numexpr\ngon-1\relax}{
%   \foreach\y in {\x,...,\ngon}{
%     %\draw (p\x) -- (p\y);
%   }
% }
% \draw [blue,transform canvas={xshift=1.5pt}] (p5) -- (p4); 

% \draw [blue] (p1) -- (p5); 
% \draw [red, transform canvas={xshift=-1.5pt}] (p5) -- (p4);
% \draw [red, transform canvas={xshift=1.5pt}] (p2) -- (p4);
% \draw [green] (p1) -- (p2); 
% \draw [green, transform canvas={xshift=-1.5pt}] (p2) -- (p4);

% \end{scope}

% \begin{scope}[shift ={(0,-5)}]
% \def\ngon{5}
% \node[regular polygon,regular polygon sides=\ngon,minimum size=3cm] (p) {};
% \foreach\x in {1,...,\ngon}{\node[mystyle] (p\x) at (p.corner \x){\x};}
% \foreach\x in {1,...,\numexpr\ngon-1\relax}{
%   \foreach\y in {\x,...,\ngon}{
%     %\draw (p\x) -- (p\y);
%   }
% }
% \draw [blue,transform canvas={xshift=1.5pt}] (p5) -- (p3); 

% \draw [blue] (p1) -- (p5); 
% \draw [red, transform canvas={xshift=-1.5pt}] (p5) -- (p3);
% \draw [red, transform canvas={yshift=1.5pt}] (p2) -- (p5);
% \draw [green] (p1) -- (p2); 
% \draw [green, transform canvas={yshift=-1.5pt}] (p2) -- (p5);

% \end{scope}

% \begin{scope}[shift ={(5,-5)}]
% \def\ngon{5}
% \node[regular polygon,regular polygon sides=\ngon,minimum size=3cm] (p) {};
% \foreach\x in {1,...,\ngon}{\node[mystyle] (p\x) at (p.corner \x){\x};}
% \foreach\x in {1,...,\numexpr\ngon-1\relax}{
%   \foreach\y in {\x,...,\ngon}{
%     %\draw (p\x) -- (p\y);
%   }
% }
% \draw [blue,transform canvas={xshift=1.5pt}] (p5) -- (p4); 

% \draw [blue] (p1) -- (p5); 
% \draw [red, transform canvas={xshift=-1.5pt}] (p5) -- (p4);
% \draw [red, transform canvas={yshift=1.5pt}] (p2) -- (p5);
% \draw [green] (p1) -- (p2); 
% \draw [green, transform canvas={yshift=-1.5pt}] (p2) -- (p5);
% \end{scope}
% \begin{scope}[shift ={(10,-5)}]


% \def\ngon{5}
% \node[regular polygon,regular polygon sides=\ngon,minimum size=3cm] (p) {};
% \foreach\x in {1,...,\ngon}{\node[mystyle] (p\x) at (p.corner \x){\x};}
% \foreach\x in {1,...,\numexpr\ngon-1\relax}{
%   \foreach\y in {\x,...,\ngon}{
%     %\draw (p\x) -- (p\y);
%   }
% }
% \draw [blue,transform canvas={yshift=-1.5pt}] (p5) -- (p2); 

% \draw [blue] (p1) -- (p5); 
% \draw [red, transform canvas={xshift=1.5pt}] (p2) -- (p3);
% \draw [red, transform canvas={yshift=1.5pt}] (p2) -- (p5);
% \draw [green] (p1) -- (p2); 
% \draw [green, transform canvas={xshift=-1.5pt}] (p2) -- (p3);
% \end{scope}
% \begin{scope}[shift ={(15,-5)}]
% \def\ngon{5}
% \node[regular polygon,regular polygon sides=\ngon,minimum size=3cm] (p) {};
% \foreach\x in {1,...,\ngon}{\node[mystyle] (p\x) at (p.corner \x){\x};}
% \foreach\x in {1,...,\numexpr\ngon-1\relax}{
%   \foreach\y in {\x,...,\ngon}{
%     %\draw (p\x) -- (p\y);
%   }
% }
% \draw [blue,transform canvas={yshift=1.5pt}] (p5) -- (p2); 

% \draw [blue] (p1) -- (p5); 
% \draw [red, transform canvas={xshift=1.5pt}] (p2) -- (p4);
% \draw [red, transform canvas={yshift=-1.5pt}] (p2) -- (p5);
% \draw [green] (p1) -- (p2); 
% \draw [green, transform canvas={xshift=-1.5pt}] (p2) -- (p4);
% \end{scope}

% \end{tikzpicture}
% \end{center}
% We now prove \cref{CombinatorialNullstellensatzTheorem}.
% \begin{proof}[Proof of \cref{CombinatorialNullstellensatzTheorem}]
% 	We will use the symbol $\equiv$ to denote equivalent representatives in the ideal $I:=\left<x_e^2-1\right>_{e\in E}$. Consider the product of the two terms in $f$ that arise from a fixed $r$-subset $S$ of $V$. Expanding this product and using the relations $x_e^2 \equiv 1$ gives $$\left(\sum_{e\in E(S)}x_e  - \binom r2\right)\left(\sum_{e\in E(S)}x_e  + \binom r2\right) \equiv \left(\sum_{\{e,e'\}\in \binom{E(S)}{2}}2x_ex_{e'} +\binom
% 	r2 -\binom r2^2\right). $$
% 	Taking the product of these terms over all $r$-subsets of $V$ gives 
	
% 	\begin{equation}\label{CNEq2} f(x) \equiv \prod_{S\subset V,\ |S| = r} \left(\sum_{\{e,e'\}\in \binom{E(S)}{2}}2x_ex_{e'} +\binom
% 	r2 -\binom r2^2\right).
% 	\end{equation}
	
%  After expanding the product, we may write $f$ as a sum of monomials of the form $\prod_{e\in E} x_e^{b_e}$. Two monomials of this form are equivalent modulo $I$ if and only if the parity of $b_e$ is the same for all edges $e$. If $H$ is a subgraph of $G$, it follows that every monomial that satisfies the condition that $b_e$ is odd if and only if $e \in E(H)$ is equivalent to the squarefree monomial $m_H:=\prod_{e\in E(H)}x_e$. Therefore, $f$ is equivalent to a sum of the form\begin{equation}\label{CNEq3}
%       f \equiv \sum_{H \subseteq G} a_H m_H.
%  \end{equation}
%  We now calculate the coefficients $a_H$ in terms of $E_{n,k,r,H}$.
 
% 	In the expansion of the right-hand side of \eqref{CNEq2}, we have the following combinatorial interpretation of the terms. Each term in the product corresponds to an $r$-subset $S$ of $V$. For each $S$, the term represents a choice of picking either a pair of edges (one of the $2x_ex_{e'}$ terms in the sum), or zero edges (the term $\binom{r}{2} -\binom{r}{2}^2$) from $E(S)$.
% 	Therefore the coefficient $a_H$ is 
% 	\begin{equation}\label{CNProof1}a_H = \sum_{k=0}^{\binom n r} 2^k \left(\binom{r}{2}^2-\binom{r}{2}\right)^{\binom{r}{2}-k} E_{n,k,r,H}.\end{equation}
% 	If $a_H$ is nonzero for some graph $H$, then the multilinear representative of $f$ is nonzero, and by \cref{CN} there exists a coloring of $K_n$ that makes $f$ nonzero, and in this case it follows that $R(r,r)>n$. Setting the expression $\eqref{CNProof1}$ to be not equal to zero and rearranging terms by the parity of $k$ concludes the proof.  
% \end{proof}

% As an example, we give the values of $E_{n,k,r,H}$ for $n=5,r=3$, and $H$ a graph of order five with an even number of edges. We denote by $G_1$ the graph with edge set $\{\{1,2\},\{1,3\},\{2,3\},\{1,4\}\}$ and $G_2$ the graph with edge set $\{\{1,2\},\{2,3\},\{3,4\},\{3,5\}\}$.
% \begin{center}
% \begin{tabular}{c|ccccccccccc}
% \backslashbox{$H$}{$k$} & 0 &1 &2&3&4&5&6&7&8&9&10 \\\hline 
% $\overline {K_5}$ & 1 & 0 & 0 &20&30&132&220&540&585&460&60\\
% $P_3 \cup \overline{K_2}$ &0&1&2&8&44&106&280&496&612&413&86\\

% $K_2\cup K_2\cup K_1$ &0&0&4&12&28&124&276&484&628&404&88\\

% $K_{1,4}$&0&0&3&4&36&132&242&588&516&428&99 \\

% $G_1$& 0&0&2&8&32&120&292&504&592&392&106 \\

% $G_2$&0&0&1&10&34&114&292&510&590&390&107 \\

% $P_5$&0&0&1&8&40&112&282&520&592&384&109 \\ 

% $C_4 \cup K_1$&0&0&2&8&28&136&272&504&612&376&110 \\

% $K_2 \cup K_3$&0&0&0&12&36&108&292&516&588&388&108 \\ 
% $\overline{K_{1,4}}$&0&0&0&8&24&120&328&504&552&392&120\\
	
% $\overline{G_1}$& 0&0&0&6&30&118&318&514&554&386&122\\
	
% $\overline{G_2}$&0&0&0&4&36&116&308&524&556&380&124\\
	
% $\overline{P_5}$&  0&0&0&4&32&132&288&524&576&364&128\\
	
% $\overline{C_4\cup K_1}$& 0&0&0&4&36&116&308&524&556&380&124\\

% $\overline{K_2 \cup K_3}$& 0&0&0&4&36&108&348&444&636&340&132\\

% $\overline{P_3\cup \overline{K_2}}$&0&0&0&0&24&128&344&512&520&384&136\\ 
	
% $\overline{K_2 \cup K_2\cup K_1}$&0&0&0&0&20&144&324&512&540&368&140\\
	
% $K_5$& 0&0&0&0&0&144&400&480&480&400&144 \\
% \end{tabular}
% \end{center}
% Unfortunately, we were unable to find any nontrivial patterns in the above data, and it appears to be difficult to compute the numbers $E_{n,k,r,H}$ in general.


% \section{Polyhedra and Cutting Planes} \label{PolyhedraSection}

% The \textit{cutting planes} proof system is a method to derive inequalities satisfied by the integral solutions to a system of linear equations \cite{ChvatalEdmonds,ChvatalCuttingPlaneProofs}. We begin with a system of linear inequalities $Ax \le b$, and we may derive new inequalities by the following inference rules: 
% \begin{itemize}
%  \item Boolean axioms: $0 \le x_i$, $x_i \le 1$, $\forall x_i$, 
% \item Initial axioms: $\sum_{i=1}^n a_i x_i \le b_i$, 
% \item Combination: $\sum_{i=1}^n\alpha_i x_i \le \beta_i$, $\sum_{i=1}^n \alpha_i' x_i \le \beta_i ' \vdash  \sum_{i=1}^n (\gamma\alpha_i +\gamma' \alpha_i')x_i \le \gamma \beta +\gamma'\beta'$  $(\gamma,\gamma' \ge 0)$,
% \item Division and rounding: $\sum_{i=1}^n \alpha_i x_i \le \beta \vdash \sum_{i=1}^n \frac {\alpha_i}{\gamma} x_i \le \lfloor \frac \beta\gamma\rfloor $  $(\gamma>0, \gamma\mid \alpha_i)$. 
% \end{itemize}
% The linear system $Ax\le b$ has no integer solutions if and only if it is possible to derive the inequality $0\le -1$ in the cutting planes proof system. We measure the \emph{length} of a cutting planes proof by the number of lines, and we also define the \emph{rank} of a proof as follows. 

% \begin{definition}
% 	The \emph{rank} $r_I$ of an inequality $I$ is defined as follows: \begin{itemize} 
% 		\item $r_I = 0$ if $I$ is an initial or Boolean axiom, 
% 		\item $r_I = \max(r_{I_1},r_{I_2})$ if $I$ is obtained by the combination of $I_1$ and $I_2$, 
% 		\item $r_I = r_{I'} +1$ if $I$ is obtained from $r_{I'}$ by division and rounding.
% 	\end{itemize}
% The rank of a proof is the maximal rank among inequalities in the proof. 
% \end{definition}

% The problem of finding a Ramsey number $R(r,s)$ can be framed as determining the integral solutions to a system of linear inequalities.
% \begin{encoding} \label{RamseyCuttingPlanesEncoding}
% 	The Ramsey number $R(r,s)$ is at most $n$ if the following system of inequalities has no integral solution:
	
% 	\begin{align*}
% 	\sum_{e\in \binom S2} x_e \le \binom{r}{2}-1, &\qquad \forall S\in\binom{[n]}r, \\\
% 	 1\le \sum_{e\in \binom S2} x_e, &\qquad \forall S\in\binom{[n]}s,\\
% 	 0\le x_e\le 1, &\qquad \forall e \in \binom{[n]}{2}.\\
% 	\end{align*}
% \end{encoding}

% The integer solutions in Encoding \ref{RamseyCuttingPlanesEncoding} correspond to graphs that avoid copies of $K_r$ and $\overline {K_s}$. 

% Using Encoding \ref{RamseyCuttingPlanesEncoding}, we were able to find graphs that do not contain a copy of $K_r$ or $\overline {K_s}$ for the following Ramsey numbers using the solver SCIP:

% \begin{center}
% \begin{tabular}{c|c|c}
% 	Ramsey number & $n$ & Computation time (seconds)\\
% 	\hline
% 	$R(3,3)$ & 5 &0 \\
% 	$R(3,4)$ & 8 &0 \\
% 	$R(3,5)$ & 13 & 2 \\
% 	$R(3,6)$ & 17 & 43 \\
% 	$R(4,4)$ & 17 & 100\\
% 	$R(3,7)$ & 21 & 2811\\
% \end{tabular}

% \end{center}
% We note that $R(3,7) = 23$, and we were unable to get the problem instance for 22 vertices to load in SCIP. Moreover, SCIP was able to show that the systems for $r=3, s = 3, n= 6$ and $r=3,s=4, n=9$ were infeasible. This was a slight improvement over using NulLA in the previous section, but still far from determining any new Ramsey number upper bounds. \subsection{Tur\'an's theorem}

% While the problem of finding graphs that avoid copies of $K_r$ and $\overline K_s$ is difficult, the problem of finding graphs that must avoid only $K_r$ is trivial. A more interesting problem is to determine the maximal number of edges among graphs that do not contain a copy of $K_r$. The \textit{Tur\'an graph} $T(n,r)$ is the complete $r$-partite graph on $n$ vertices whose parts are as nearly equal in size as possible. The following theorem of Tur\'an is a well-known result in extremal graph theory, and says that the graphs $T(n,r)$ are optimal. 

% \begin{theorem}[Tur\'an, \cite{Turan}] \label{TuranThm}
% 	A graph with $n$ vertices that does not contain a clique of size $s+1$ has at most $$\left(1-\frac1s\right)\frac{n^2}{2}$$ edges. Moreover, the Tur\'an graph $T(n,s)$ contains the maximal number of edges among $(s+1)$-clique-free graphs. 
% \end{theorem}

% In the proof of \cref{TuranCP} we describe a simple way to derive an upper bound for the number of edges in a $(s+1)$-clique-free graph using the cutting planes proof system. By \cref{TuranThm}, this bound is tight. Before proving \cref{TuranCP}, we state the following lemma, which gives a formula for the number of edges in a Tur\'an graph. 
% \begin{lemma} \label{TuranEdgeCount}
% 	Let $n = ms+r$, with $0\le r \le s-1$. Then the number of edges in the $s$-partite Tur\'an graph $T(n,s)$ is precisely $\frac{(s-1)(n^2-r^2)}{2s}+\binom{r}{2}$.
% \end{lemma}

% % \begin{proof} {\color{red}The following proof is due to Brian Scott (see https://math.stackexchange.com/questions/1213226/deriving-the-number-of-edges-in-a-tur\%C3\%A1n-graph)}
	
% % 	There are $r$ parts of size $m+1$ and $s-r$ parts of size $m$. Then the number of edges is 
% % 	\begin{align*}\binom n2 - (s-r)\binom m2 - r\binom{m+1}2 &= \frac{n^2-r-2mr-m^2s}{2}\\
% % 	&= \frac{n^2-r^2-2mr-m^2s}{2} +\binom{r}{2}\\
% % 	&= \frac{s(n^2-r^2)-ms(2r-ms)}{2s}+\binom{r}{2}\\
% % 	&= \frac{s(n^2-r^2)-(n-r)(n+r)}{2s}+\binom{r}{2}\\
% % 	&= \frac{(s-1)(n^2-r^2)}{2s}+\binom{r}{2}.
% % 	\end{align*}
% % \end{proof}


% A detailed proof of Lemma \ref{TuranEdgeCount} can be found in \cite{TuranEdges}. We are now ready to prove \cref{TuranCP}.
% \begin{proof}[Proof of \cref{TuranCP}]
% We proceed by induction and use the bounds for the number of edges in subgraphs of order $k$ to derive the desired bounds for the number of edges in subgraphs of order $k+1$. For the base case $n = s+1$, we have $ r =1$, and so by Lemma \ref{TuranEdgeCount}, the number of edges in $T(s+1,s)$ is $\frac{(s-1)((s+1)^2-1)}{2s} = \frac{(s-1)(s+2)}{2} = \binom{s+1}{2}-1$. 

% Let $S_{k+1}$ be a $(k+1$)-subset of $V$, and suppose we have derived the inequality \begin{equation}\label{TuranInductionBound}
%     \sum_{e\in \binom{S_k}{2} }x_e \le |E(T(k,s))|
% \end{equation}for all $k$-subsets $S$ of $V$. 

% To obtain the desired bound for $S_{k+1}$, we add the $k+1$ inequalities \eqref{TuranInductionBound} for each of the $k+1$ subsets of size $k$ contained in $S_{k+1}$. Each variable $x_e$ in the sum appears in exactly $k-1$ inequalities, so the result is $(k-1)\sum_{e \in \binom{S_{k+1}}{2}} x_e \le (k+1)|E(T(k,s))|$. After division by $k-1$ and rounding, we obtain $$\sum_{e \in \binom{S_{k+1}}{2}} x_e \le 
% \left\lfloor\frac{k+1}{k-1}|E(T(k,s))|\right\rfloor.$$

% It remains to show that $\left\lfloor\frac{k+1}{k-1}|E(T(k,s))|\right\rfloor = |E(T(k+1,s))|.$ Suppose $r<s+1$. Then we have 
% \begin{align*}
% \left\lfloor \frac{k+1}{k-1}|E(T(k,s))| \right\rfloor &=\left\lfloor \frac{k+1}{k-1}\left(\frac{(s-1)(k^2-r^2)}{2s}+\binom{r}{2}\right) \right\rfloor \\
% &= \left\lfloor \frac{k^3s-k^3+k^2s+kr^2-krs-k^2+r^2-rs}{2s(k-1)} \right\rfloor \\
% &= \left\lfloor \frac{k^3s - kr^2s - k^3 + k^2s + kr^2 - 2krs + r^2s - k^2 + r^2}{2s(k-1)} \right\rfloor+\binom{r+1}{2}\\
% &=\left\lfloor \frac{(s-1)(k^3 - kr^2 + k^2 - 2kr + r^2 - 2k + 2r)+2r^2-2kr+(2k-2r)(s-1)}{2s(k-1)} \right\rfloor\\&\hspace{30pt}+\binom{r+1}{2}\\
% &= \left\lfloor \frac{(s-1)(k-1)((k+1)^2-(r+1)^2)+2r^2-2kr+(2k-2r)(s-1)}{2s(k-1)} \right\rfloor+\binom{r+1}{2} \\
% &=\left\lfloor
% \frac{2r^2-2kr+(2k-2r)(s-1)}{2s(k-1)}\right\rfloor
% +\frac{(s-1)((k+1)^2-(r+1)^2)}{2s}+\binom{r+1}{2}\\
% &=\left\lfloor
% \frac{(k-r)(s-1-r)}{s(k-1)}\right\rfloor + |E(T(k+1,s))|\\
% &= |E(T(k+1,s))|.
% \end{align*}

% In the third to last line, we used the fact that $\frac{(s-1)((k+1)^2-(r+1)^2)}{2s} = \frac{(s-1)(k-r)(k+r+2)}{2s}$ is always an integer. Since $k-r$ is a multiple of $s$, then if $s$ is odd then $(s-1)(k-r)$ is a multiple of $2s$. If $s$ is even, then $k$ and $r$ have the same parity, so $k+r+2$ is even and $(k-r)(k+r+2)$ is a multiple of $2s$. 
% To see the last line, note that $0<\frac{(k-r)(s-1-r)}{s(k-1)}<1$. This is clear if $r \neq 0$. If $r=0$, then we have $0<\frac{k(s-1)}{(k-1)s} <1$ since $k>s$. 



% Now if $r = s-1$, then $k+1$ is a multiple of $s$, and the third to last line becomes 

% \begin{align*}\left\lfloor
% \frac{2r^2-2kr+(2k-2r)(s-1)}{2s(k-1)}\right\rfloor
% +\frac{(s-1)(k+1)^2}{2s}-\frac{(s-1)(s^2)}{2s}+\binom{s}{2}
% &= \frac{(s-1)(k+1)^2}{2s} \\
% &= |E(T(k+1),s)|.
% \end{align*}

% To count the number of lines in the cutting planes proof, notice that to derive the bound for $S_k$ we require $k-1$ lines to add the $k$ inequalities for the $k$ subsets of $S_k$ containing $k-1$ elements, plus 1 additional line for a division and rounding step. Therefore the total number of lines to derive the bound for $V$ is $\sum_{k> s+1} k\binom{n}{k} = \sum_{k> s+1} n\binom{n-1}{k-1} = O(n2^{n})$. Let $r_k$ be the rank of the inequality \eqref{TuranInductionBound}. Adding the inequalities for all the $S_k$ preserves the rank, and we use one division and rounding step to obtain the inequality for $S_{k+1}$. Therefore $r_{k+1} = r_k+1$, and since the inequalities for $S_{s+1}$ have rank 0, the inequalities for $V$ have rank $n-s-1$.
% \end{proof}
% \section{Boolean Formulas}
 
% \begin{proposition}
%     For every $k \ge 0$, there exists an unsatisfiable formula $\phi_k$ such that the minimal degree of a Nullstellensatz certificate of the unsatisfiability of $\phi_k$ using Encoding \ref{Encoding2SAT} is $k -1$. 
% \end{proposition}
% \begin{proof}
% Let $\phi_k$ denote the formula $$ (y \vee x_1) \wedge (\bar x_1 \vee x_2) \wedge (\bar x_2 \vee x_3) \wedge \dots \wedge (\bar x_{k-1} \vee x_k) \wedge (\bar x_k \vee \bar y ) \wedge (\bar y \vee x_{k+1}) \vee (\bar x_{k+1} \vee x_{k+2}) \vee \dots \vee (x_{2k} \vee \bar y).$$ Using Encoding \ref{Encoding2SAT}, we have that $\phi$ is satisfiable if and only if the following system of equations has a solution. 

% \begin{align*}
%     (1-y)(1-x_1) &= 0, \\
%     x_1(1-x_2) &= 0, \\
%     x_2(1-x_3) & = 0, \\
%     &\vdots \\
%     x_{k-1}(1-x_k) &= 0,\\
%     x_k y & = 0, \\
%     (1-y)(1-x_{k+1}), \\
%     x_{k+1} & 
% \end{align*}
% \end{proof}
% \label{SATSolving}
% A \textit{literal} is a variable $x_i$ or its negation $\bar{x}_i$. A \text{clause} is a disjunction of literals, and a formula is in \textit{conjunctive normal form} (CNF) if it is a conjunction of clauses. A CNF formula is satisfiable if there is a true/false assignment to the literals that makes every clause true. The \textit{Boolean satisfiability problem} (SAT) is the problem of determining whether a given formula is satisfiable. Many problems can be encoded in terms of the satisfiability of CNF formulas, and modern SAT solvers take a CNF formula as input and try to determine whether that formula is satisfiable. More information about techniques used in SAT solving can be found in \cite{SATHandbook_1stEd}. 

% In this section we consider the Ramsey numbers $R(G_1,G_2)$, and the following encoding encodes the problem of computing $R(G_1,G_2)$ as an instance of SAT.  
 
% \begin{encoding}\label{Ramsey CNF}
% 	The number $R(G_1,G_2)$ is at most $n$ if the formula $\phi_{G_1,G_2,n}$ is unsatisfiable, where $(V,E) = K_n$ and 
% 	$$\phi_{G_1,G_2,n} :=\left(\bigwedge_{H\subset K_N, H\cong G_1} \bigvee_{e\in E(H)} \bar x_e \right)\wedge \left(\bigwedge_{H\subset K_N, H\cong G_2} \bigvee_{e\in E(H)} x_e\right).$$
% 	Moreover, if $\phi_{G_1,G_2,n}$ is satisfiable, then $R(G_1,G_2) \ge n+1$. 
% \end{encoding}
% The \textit{book graph} $B_n$ is the graph $K_2+\overline{K_n}$. The numbers $R(B_m,B_n)$ are known for several families of $m,n$, but many cases are unknown (see \cite{RamseySurvey}). The upper bounds $R(B_4,B_5) \le 19$ and $R(B_3,B_6)\le19$ were established in \cite{BookUpperBounds}. 

% The \textit{wheel graph} is the graph $K_1 + C_{n-1}$. In \cite{BookUpperBounds} it is shown that $R(W_5, W_7)\le 16$, and the previously known best lower bound was $R(W_5,W_7)\ge 13.$ \cref{SATSolvingBookWheelBounds} shows that the bounds for the book graphs are tight and improves the lower bound for $R(W_5,W_7)$ by two. 


% \begin{proof}[Proof of \cref{SATSolvingBookWheelBounds}] The following adjacency list describes a graph of order 18 that contains no $B_4$ or $\overline {B_5}$: 
% \begin{center}
% \begin{tabular}{c|c}
% 	$v$& neighbors of $v$\\
% 	\hline
% 1&2, 8, 9, 12, 14, 15, 17, 18\\
% 2& 1, 5, 7, 10, 12, 14, 16, 17\\
% 3& 4, 5, 7, 8, 9, 12, 13, 17\\
% 4& 3, 6, 7, 10, 11, 12, 15, 16\\
% 5& 2, 3, 7, 8, 9, 11, 16, 18\\
% 6& 4, 8, 9, 11, 13, 14, 15, 16\\
% 7& 2, 3, 4, 5, 13, 14, 15, 18\\
% 8& 1, 3, 5, 6, 11, 14, 15, 17\\
% 9& 1, 3, 5, 6, 12, 13, 16, 18\\
% 10& 2, 4, 11, 12, 13, 16, 17, 18\\
% 11& 4, 5, 6, 8, 10, 12, 14, 18\\
% 12& 1, 2, 3, 4, 9, 10, 11, 14 \\
% 13&3, 6, 7, 9, 10, 14, 17, 18\\
% 14& 1, 2, 6, 7, 8, 11, 12, 13\\
% 15& 1, 4, 6, 7, 8, 16, 17, 18\\
% 16& 2, 4, 5, 6, 9, 10, 15, 17\\
% 17& 1, 2, 3, 8, 10, 13, 15, 16\\
% 18& 1, 5, 7, 9, 10, 11, 13, 15
% \end{tabular}
% \end{center}
% The following adjacency list describes a graph of order 18 that contains no $B_3$ or $\overline B_6$: 
% \begin{center}
% \begin{tabular}{c|c}
% 		$v$& neighbors of $v$\\
% 	\hline
% 1&2, 3, 6, 7, 10, 11, 18\\
% 2& 1, 6, 8, 9, 10, 12, 16\\
% 3& 1, 7, 12, 14, 15, 16, 18\\
% 4& 5, 6, 7, 10, 12, 13, 17\\
% 5& 4, 6, 9, 13, 14, 16, 18\\
% 6& 1, 2, 4, 5, 11, 12, 14 \\
% 7&1, 3, 4, 8, 10, 14, 17\\
% 8& 2, 7, 11, 13, 14, 16, 17 \\
% 9&2, 5, 10, 14, 15, 17, 18\\
% 10& 1, 2, 4, 7, 9, 13, 15\\
% 11& 1, 6, 8, 13, 15, 17, 18\\
% 12& 2, 3, 4, 6, 15, 16, 17\\
% 13& 4, 5, 8, 10, 11, 15, 16\\
% 14& 3, 5, 6, 7, 8, 9, 15\\
% 15& 3, 9, 10, 11, 12, 13, 14\\
% 16& 2, 3, 5, 8, 12, 13, 18\\
% 17& 4, 7, 8, 9, 11, 12, 18\\
% 18& 1, 3, 5, 9, 11, 16, 17
% \end{tabular}
% \end{center}

% The following adjacency list describes a graph of order 14 that contains no $W_5$ or $\overline{W_7}$:
% \begin{center}
% \begin{tabular}{c|c}
% 	$v$& neighbors of $v$\\
% 	\hline
% 1&3, 6, 7, 9, 10, 11, 12\\
% 2&4, 6, 8, 10, 11, 12\\
% 3&1, 6, 7, 9, 11, 12\\
% 4&2, 5, 6, 7, 9, 11, 12\\
% 5&4, 7, 8, 9, 10, 12\\
% 6&1, 2, 3, 4, 7, 14 \\
% 7&1, 3, 4, 5, 6, 8, 13, 14\\
% 8&2, 5, 7, 13, 14 \\
% 9&1, 3, 4, 5, 10, 13, 14\\
% 10& 1, 2, 5, 9, 13, 14\\
% 11& 1, 2, 3, 4, 12, 13, 14\\ 
% 12& 1, 2, 3, 4, 5, 11, 13, 14\\
% 13& 7, 8, 9, 10, 11, 12, 14\\
% 14& 6, 7, 8, 9, 10, 11, 12, 13\\
% \end{tabular}
% \end{center}

% Figure \ref{fig:threeGraphs} gives drawings of (isomorphic copies of) each of the three graphs. All three graphs were found using the solver Satch \cite{Satch}. Satch and another solver, CaDiCaL \cite{BiereFazekasFleuryHeisinger-SAT-Competition-2020-solvers}, were unable to find a graph on 15 vertices containing no copies of $W_5$ or $\overline{W_7}$  in over 12 days of computation time. 

% \begin{figure}
%     \centering
%     \includegraphics[scale=0.3]{Book45_critical_graph_nolabels.png}
%     \includegraphics[scale=0.3]{Book36_critical_graph_redrawn_nolabels.png}
%     \includegraphics[scale=0.3]{Wheel57_critical_graph_nolabels.png}
%     \caption{From left to right, a graph that contains no $B_4$ or $\overline{B}_5$, a graph that contains no $B_3$ or $\overline{B}_6$, a graph that contains no $W_5$ or $\overline{W}_7.$}
%     \label{fig:threeGraphs}
% \end{figure}
% \end{proof}


% % \begin{theorem} \label{SATSolvingWheelBounds}
% % $R(W_5,W_7)\ge 15$
% % \end{theorem}
% % \begin{proof}

% % \end{proof}



% \subsection{Rado numbers}

% We note that Encoding \ref{binEdge} and the proof of \cref{RamseyNullUpperBound} apply to other coloring problems in Ramsey theory. We can define an analogous Builder-Painter game for other problems and construct a certificate in the same way by following Builder's optimal strategy. As an example of encoding a different problem, we give a polynomial encoding for Rado's theorem. 

% A system of linear equations $Ax = 0$ is \emph{regular} if there exists some $n$ such that every $k$-coloring of $[n]$ contains a monochromatic solution $x$. Rado's theorem says that the system $Ax = 0$ is regular if and only if $A$ satisfies the columns condition \cite{GrahamRothschildSpencer}:

% \begin{definition}Let $c_1,\dots,c_m$ denote the columns of $A$. Then $A$ is said to satisfy the \emph{columns condition} if there exists a partition of the columns $\{C_1,\dots,C_\ell\}$ such that, letting $S_i = \sum_{c \in C_i} c_i$, we have 
% 	\begin{enumerate}[i)]
% 		\item $S_1 = 0,$ 
% 		\item For $i>1$, $S_i$ can be expressed as a linear combination of columns $c_j \in C_k$ with $k<i$. 
% 	\end{enumerate}
% \end{definition}

% Using the same ideas as in Encoding \ref{binEdge}, we can encode the problem of computing the $\emph{Rado number}$ $R(A,k)$, the smallest integer $n$ such that every $k$-coloring of $[n]$ contains a monochromatic solution to $Ax = 0$. 

% \begin{encoding}
% 	Let $A$ be an $\ell \times m$ matrix, and let $S = \{ x: Ax = 0,\ x_i \in [n] \text{ for all } i\}$. Then the Rado number $R(A,k)$ is at most $n$ if and only if the following system of equations has no solution:
	
% 	\begin{align*}
% 	\prod_{j=1}^m x_{i,s_j} = 0 & \qquad \forall i, 1\le i \le k, \forall s = (s_1,\dots,s_m) \in S, \\
% 	1+\sum_{i=1}^k x_{i,j} = 0 & \qquad \forall j\in[n], \\
% 	x_{i_{1},j}x_{i_2,j} = 0 & \qquad \forall j\in[n], \forall i_1,i_2, 1\le i_1< i_2 \le k.
% 	\end{align*}
% \end{encoding}
% For example, consider the theorems of Schur and van der Waerden \cite{GrahamRothschildSpencer}. Schur's theorem states that for all $k$, there exists an integer $S(k)$ such that every $k$-coloring of $[S(k)]$ contains a monochromatic sum of the form $x+y = z$. Van der Waerden's theorem states that for all $k$ and $r$ there exists an integer $W(k,r)$ such that every $r$-coloring of $[W(k,r)]$ contains a monochromatic $k$-term arithmetic progression. The following lemma gives polynomial encodings for the problems of finding $S(k)$ and $W(k,m)$.

% \begin{encoding}
% The Schur number $S(k)$ is at most $n$ if and only if there is no solution to the following system over $\Ftwobar$: 

% \begin{align*} x_{i,u}x_{i,v}x_{i,w} &=0 &&{\forall i, 1\le i\le k,\quad u<v<w\in [n], u+v = w} \\
% x_{i,u}x_{i,2u} &= 0 &&{\forall i, 1\le i\le k,\quad u\le\lfloor n/2\rfloor}\\
% 1+\sum_{i=1}^k x_{i,m}&= 0 &&{\forall m \in [n]} \\
% x_{i,m}x_{j,m} & = 0 &&\forall m\in[n],\forall i,j, 1\le i<j\le k.
% \end{align*}

% The van der Waerden number $W(k,r)$ is at most $n$ if and only if there is no solution to the following system over $\Ftwobar$:

% \begin{align*} \prod_{j=0}^{m-1} x_{i,a+dj} &=0 &&{\forall i, 1\le i\le r,\quad a,d\in [n], a+d(k-1)\le n}  \\
% 1+\sum_{i=1}^r x_{i,\ell}&= 0 &&{\forall \ell \in [n]} \\
% x_{i,\ell}x_{j,\ell} & = 0 &&\forall \ell \in [n],\forall i,j, 1\le i<j\le r.
% \end{align*}

% \end{encoding}

%\begin{proposition}[Ramsey's theorem]
%	If $N\ge2^{2\max(r,s)-3}$, then there is no solution to the system.  
%\end{proposition}
%
%\begin{proof}
%	We adapt the proof in \cite{Diestel}. Label the vertices of $K_N$ from 1 to $N$. Let $v_1 =1$. For the first $2^{2r-3}-1$ levels of the certificate tree, label level $i$ by the edge $(1,i+1)$. By the pigeonhole principle, on each path from the root to a leaf there are either $2^{2r-2}$ edges labeled with an $x_e$ or $2^{2r-2}$ labeled with a $y_e$. Let $S_1$ be the set of all the vertices in these edges, except $v_1$.
%	
%	Now we may proceed inductively: for each leaf, let $v_2$ be the first  vertex in $S_1$. Label the vertices in $S_1$ $w_{1,j}, 1\le j\le |S_1|$. Then label the next $2^{2r-2}$ levels by the edge $(v_2,w_{1,i+1})$. {\color{red} Need to finish/make more precise}
%	
%	Ultimately all of the polynomials at the leaves will be cancelled by clique polynomials. 
%\end{proof}
% We can also use Boolean formulas to encode the problem of computing Rado numbers.
% \begin{encoding}
%     	Let $A$ be an $\ell \times m$ matrix, and let $S = \{ x: Ax = 0,\ x_i \in [n] \text{ for all } i\}$. Then the Rado number $R(A,k)$ is at most $n$ if and only if the following formula is unsatisfiable.
    	
%     	$$ \left(\bigwedge_{i=1}^n\left(\bigvee_{j=1}^k v_{i}^k\right)\right) \wedge \left(\bigwedge_{s\in S}\bigwedge_{j=1}^k\left(\bigvee_{i=1}^m \bar{v}_{s_i}^j\right)\right) \wedge \left(\bigwedge_{i=1}^n \bigwedge_{1\le j_1 < j_2 <k} (\bar{v}_{i}^{j_1} \vee \bar{v}_{i}^{j_2}) \right)$$
% \end{encoding}

% A special case of Rado's theorem is \emph{Schur's theorem}, which corresponds to the case $A  = \begin{pmatrix} 1 & 1 & -1\end{pmatrix}.$ The Schur number $S(k)$ is the smallest number $n$ such that every $k$-coloring of $[n]$ contains a monochromatic solution to the equation $x+y = z$. We give another encoding of the problem of finding the Schur number $S(k)$:

% \begin{encoding}\label{SchurEncoding}
% 	The Schur number $S(k)$ is at most $n$ if and only if there is no solution to the following system of equations over $\C$ or $\overline{\mathbb{F}_q}$ with $q$ and $k$ relatively prime. 
	
% 	\begin{align*}
% 	x_i^k-1 &=0 &&\forall i, 1\le i\le n,\\ 
% 	\frac{(x_i^k-x_{2i}^k)}{x_i-x_{2i}} &= 0 &&\forall i, 2i\in [n],\\
% 	\frac{(x_u^k-x_{v}^k)(x_u^k-x_w^k)}{(x_u-x_{v})(x_u-x_w)}&=0&&\forall u<v<w\in[n], u+v=w.
% 	\end{align*}
% \end{encoding}
% % \begin{remark}
% % We may reduce the exponents of the variables in the third set of equations modulo $k$ in order to give them a more symmetrical appearance. 
% % \end{remark}
% Encoding \ref{SchurEncoding} is similar to the encodings for non $k$-colorability of graphs given in \cite{MarguliesThesis}, where it is shown that the minimal degree of certificates of non-3-colorability is congruent to 1 modulo 3. The following proposition is an analogous fact for the encoding for Schur numbers.

% \begin{proposition}
% 	The degree of a minimal degree certificate for the statement $S(k)\le n$ using Encoding \ref{SchurEncoding} is congruent to 0 or 1 modulo $k$. 
% \end{proposition} 
% \begin{proof}
% 	Let $d$ be the minimal degree of a certificate for $S(k)\le n$. Then a minimal degree certificate has the form \begin{equation}\sum_{i=1}^n \beta_i (x_i^k-1) + \sum_{i=1}^{\lfloor n/2 \rfloor}\gamma_i\frac{x_i^k-x_{2i}^k}{x_i-x_{2i}} + \sum_{u+v =w \le n, u<v} \delta_{uv}\frac{(x_u^k-x_{v}^k)(x_u^k-x_w^k)}{(x_u-x_{v})(x_u-x_w)}=1. \label{SchurCertEq}\end{equation}
	
% 	Now observe that in expanding the polynomial on the left-hand side of Equation \ref{SchurCertEq}, the sum of all monomials whose degrees are not congruent to 0 modulo $k$ is zero. The polynomials $x_i^k-1$, $\frac{x_i^k-x_{2i}^k}{x_i-x_{2i}}$, and $\frac{(x_u^k-x_{v}^k)(x_u^k-x_w^k)}{(x_u-x_{v})(x_u-x_w)}$ contain only monomials whose degrees are congruent to 0, $-1$, and $-2$ modulo $k$, respectively.   Therefore we may assume that the $\beta_i,\gamma_i,$ and $\delta_{uv}$ respectively contain only monomials whose degrees are congruent to 0, 1, and 2 modulo $k$. Suppose $d = mk+2$ is the minimal degree of a certificate. Then the product of the degree $d$ monomials in $\delta_{uv}$ and the polynomial $\frac{(x_u^k-x_{v}^k)(x_u^k-x_w^k)}{(x_u-x_{v})(x_u-x_w)}$ is a homogeneous polynomial $P_{uv}$ of degree $(m+2)k$. Since the $\beta_i$ and $\gamma_i$ contain monomials of degree at most $mk$ and $mk+1$, respectively, the products $\beta_i(x_i^k-1)$ and $\gamma_i \frac{x_i^k-x_{2i}^k}{x_i-x_{2i}}$ have degree at most $(m+1)k$, and the sum of the $P_{uv}$ is identically zero. Therefore we could obtain a certificate of degree smaller than $d$ by omitting each monomial of degree $d$ in the $\delta_{uv}$, which contradicts the minimality of $d$. Therefore $d$ cannot be congruent to $2$ modulo $k$. 
% \end{proof}

% \subsection{SAT and the Nullstellensatz}

% It is possible to encode a Boolean formula $\phi$ as a system of polynomial equations that has a solution if and only if $\phi$ is satisfiable. 
% \begin{encoding} \label{Encoding2SAT}
%     Let $\phi$ be a CNF formula with clauses $C_1, \dots, C_m$ and variables $x_1,\dots, x_n$. Then $\phi$ is satisfiable if and only if the following system of equations has a solution over $\C$. 
    
%     \begin{align*}
%         x_i (1-x_i) &= 0, &&1\le i \le n, \\
%         \prod_{x_j \in C_i}(1-x_j) \prod_{\bar x_j \in C_i} x_j & = 0, &&1\le i \le m.
%     \end{align*}
% \end{encoding}
% The problem $k$-SAT is the problem of determining the satisfiability of a CNF formula in which each clause contains at most $k$ literals. It is well known that $k$-SAT is NP-complete for $k\ge3$, but 2-SAT is solvable in polynomial time. A result from \cite{MarguliesThesis} states that if the degrees Nullstellensatz certificates of a problem are bounded by a constant, then that problem can be solved in polynomial time. Therefore, if P $\neq$ NP, then given an NP-complete problem $A$ and a encoding of $A$ as a system of equations, we can find a family of instances of $A$ whose Nullstellensatz degrees grow. 

% However, it is possible for problems in P to exhibit this degree growth nonetheless. Consider the following formula $\phi_n$. 

% $$ \phi_n := x_1 \wedge  \left(\bigwedge_{i=1}^{n-1} (\bar x_i \vee x_{i+1}) \right)\wedge \bar x_n.$$
% It is not difficult to see that $\phi_n$ is unsatisfiable for all $n$. Using Encoding \ref{Encoding2SAT}, it follows that for all $n$, the following system of equations has no solution.  
% \begin{align*}
%     1- x_1 &= 0, \\
%     x_i(1-x_{i+1}) &= 0, &&1\le i \le n-1, \\
%     x_n &= 0. \\
%     % x_i^2 - x_i &= 0, && 1\le i\le n.
% \end{align*}

% In \cite{BussPitassi_InductionPrinciple}, Buss and Pitassi prove that the degree of a Nullstellensatz certificate for this system has degree $\Omega(\log n)$.
% \section{Future Directions}\label{Future Directions}

% We conclude by mentioning some open problems. \cref{RamseyNullUpperBound} says that if one assumes Ramsey's theorem, then there exists an algebraic certificate of an upper bound for $R(r,s)$. One can ask whether a ``converse" holds.
% \begin{question}
% 	Is there an algebraic proof of Ramsey's theorem using properties of ideals in infinite polynomial rings?
% \end{question}

% Moreover, \cref{RamseyNullUpperBound} gives an upper bound for the degree of a Nullstellensatz certificate for $R(r,s)$. However, it is not known whether this bound is tight in general. 

% \begin{question}
% 	What are the best upper and lower bounds for the degree of a Nullstellensatz certificate for $R(r,s)$ using the encoding in Encoding \ref{binEdge}?
% \end{question}

\begin{acknowledgements}
The authors were supported by National Science Foundation grant DMS-1818969. We thank Susan Margulies for helpful discussions and assistance with computations. 
\end{acknowledgements}
% A lower bound for rank of a cutting planes proof of the fact that $R(r,r)\le 4^r$ is given in \cite{LauriaRamsey}. A natural question is then to find an upper bound and a general cutting planes proof of $R(r,r) \le 4^r$ similar to \cref{TuranCP}.
% \begin{question}
% 	What is an upper bound for the rank of a cutting planes proof of $R(r,s)\le N$ using Encoding \ref{RamseyCuttingPlanesEncoding}?
% \end{question}
\printbibliography
% \bibliographystyle{abbrv}
% \bibliography{RamseyDraft_v7}
\end{document}