# Quantum Information Approach to the Implementation of a Neutron Cavity

O. Nahman-Lévesque  Institute for Quantum Computing, University of Waterloo,
Waterloo, ON, Canada, N2L3G1  Department of Physics, University of Waterloo,
Waterloo, ON, Canada, N2L3G1  D. Sarenac  Institute for Quantum Computing,
University of Waterloo, Waterloo, ON, Canada, N2L3G1  D. G. Cory  Institute
for Quantum Computing, University of Waterloo, Waterloo, ON, Canada, N2L3G1
Department of Chemistry, University of Waterloo, Waterloo, ON, Canada, N2L3G1
M. G. Huber  National Institute of Standards and Technology, Gaithersburg,
Maryland 20899, USA  D. A. Pushin<EMAIL_ADDRESS>Institute for
Quantum Computing, University of Waterloo, Waterloo, ON, Canada, N2L3G1
Department of Physics, University of Waterloo, Waterloo, ON, Canada, N2L3G1

###### Abstract

Using the quantum information model of dynamical diffraction we consider a
neutron cavity composed of two perfect crystal silicon blades capable of
containing the neutron wavefunction. We show that the internal confinement of
the neutrons through Bragg diffraction can be modelled by a quantum random
walk. Good agreement is found between the simulation and the experimental
implementation. Analysis of the standing neutron waves is presented in regards
to the crystal geometry and parameters; and the conditions required for well-
defined bounces are derived. The presented results enable new approaches to
studying the setups utilizing neutron confinement, such as the experiments to
measure neutron magnetic and electric dipole moments.

###### pacs:

Valid PACS appear here

##  I Introduction

The advancement of silicon fabrication techniques in the 20th century has
enabled the use of perfect crystals in neutron science to resolve dynamical
diffraction effects. The most successful application was perfect-crystal
neutron interferometry where three well-polished blades from a single ingot of
silicon achieve centimeter-scale path separation and coherent superposition
Rauch  _et al._ (1974); Klepp  _et al._ (2014); Rauch and Werner (2015);
Pushin  _et al._ (2015); Huber  _et al._ (2019). Hallmark experiments with a
perfect-crystal neutron interferometer (NI) include the first demonstration of
gravity on a quantum particle Colella  _et al._ (1975), probing of dark
energy/fifth forces Lemmel  _et al._ (2015); Li  _et al._ (2016), observing
the 4$\pi$ symmetry of spinor rotation Rauch  _et al._ (1975), and observing
neutron orbital angular momentum Clark  _et al._ (2015); Sarenac  _et al._
(2016).

The theory of dynamical diffraction (DD) models the neutron propagation
through perfect crystals. Albeit powerful, it becomes impractical when
considering complicated geometries. For example, neutron cavities that employ
DD have been experimentally investigated for use as a neutron storage device
Jericha  _et al._ (1996, 1997, 2000); Jaekel  _et al._ (2005, 2005); Rauch
(2001); Facchi  _et al._ (2003). However, in-depth modelling of the neutron
propagation through the cavity and parameter analysis is lacking.

The recently introduced quantum information (QI) model of DD attempts to
simplify the mathematics by treating the neutron propagation as a quantum
random walk Nsofini  _et al._ (2016, 2019, 2017); Nahman-Lévesque  _et al._
(2022). Good agreement has been found between the model and the standard DD
effects such as the Borrmann triangle, pendellösung oscillations, and the
spatial intensity profiles of the NI paths.

Here we apply the QI model of DD to the case of a neutron cavity built from
two perfect crystal silicon blades. We show that such an arrangement can
contain the neutron wavefunction. The behaviour of the neutron modes inside
the cavity is characterized with respect to the cavity geometry, and good
agreement is found between an initial experimental implementation and the
model. In addition to providing new insights into neutron storage devices, the
presented work lays the foundation for simulating the proposed measurements of
the neutron magnetic and electric dipole moment Dombeck  _et al._ (2001);
Gentile  _et al._ (2019).

##  II QI model for dynamical diffraction

When considering neutron diffraction through crystals, DD effects must be
considered. However, the standard theory of DD is limited to idealized perfect
crystals (no impurities or defects) and practically limited to simple
geometries. In Nsofini  _et al._ (2016), it was demonstrated that there exists
a simpler, more computationally accessible QI based model in terms of a
quantum random walk. In the QI model, the crystal is represented as a lattice
of nodes which act as a unitary operator on the neutron state by either
transmitting or reflecting it to its nearest neighbours. The neutron input
state to every node is given by a two-state vector:

$\alpha\ket{a}+\beta\ket{b}\quad\mathrm{or}\quad\begin{pmatrix}\alpha\\\
\beta\\\ \end{pmatrix}$ (1)

where $\ket{a}$ and $\ket{b}$ are the states propagating onto the node in the
up and down directions, respectively. The action of one node is given by:

$U_{i}=\ket{a_{i+1}}(t_{a}\bra{a_{i}}+r_{b}\bra{b_{i}})+\ket{b_{i-1}}(r_{a}\bra{a_{i}}+t_{b}\bra{b_{i}})$
(2)

with coefficients

$\begin{split}t_{a}=e^{i\xi}\cos{\gamma},\;\;r_{b}=e^{i\zeta}\sin{\gamma}\\\
r_{a}=-e^{-i\zeta}\sin{\gamma},\;\;t_{b}=e^{-i\xi}\cos{\gamma}\end{split}$ (3)

The parameter $\gamma$ controls the amplitude of reflection/transmission at
each node, while $\xi$ and $\zeta$ are phase parameters.

Figure 1: The simulated neutron intensity inside two perfect-crystal silicon
blades acting as a neutron cavity. The neutron is initialized as an incident
spherical wave to the corner of the top crystal. Given that most of the beam
gets initially transmitted, the range of the color bar is limited to emphasize
the confined intensity. The crystals are placed a distance $D$ apart, have
thickness $t$ and length $L$. After the first few bounces, most of the
leftover neutron intensity is contained within a small band on the inside
edges of the crystals. This intensity is preserved with further propagation. A
detector can be placed at the exit of the crystals to capture the neutrons
exiting the cavity. This simulation ($\Delta_{H}\approx 50\mu$m, $t\approx
0.5$mm, $D\approx 0.2$mm, $L\approx 3$cm) considers a very thin crystal slice
to better illustrate the behavior near the gap.

The full state vector $\psi$ at every layer of a simulation of height $h$ is
represented by a size $2h$ column vector, where the entries $m,m+1$ are the up
and down inputs to node number $\frac{m+1}{2}$. Every lattice column $c_{i}$
has a corresponding unitary operator $C_{i}$, and the state vector after $n$
layers is given by

$\psi_{n}=\prod_{i=0}^{n-1}C_{n-i}\psi_{0}$ (4)

In Nahman-Lévesque  _et al._ (2022), it was shown that there is an equivalence
between the simulation parameters and a given experimental configuration in
both the Laue and Bragg geometry, given by

$n\cdot\gamma=\frac{\pi d}{2\Delta_{H}}$ (5)

where $n$ is the number of simulation layers needed to simulate a real-space
distance $d$ with parameter $\gamma$. $\Delta_{H}$ is the pendellösung period
inside the crystal, and is given by

$\Delta_{H}=\frac{\pi V_{cell}\cos\theta_{B}}{\lambda|F_{H}|}$ (6)

where $V_{cell}$ is the volume of a crystal unit cell, $\theta_{B}$ is the
Bragg angle, $\lambda$ is the neutron wavelength and $F_{H}$ is the crystal
structure factor. For a material such as silicon, with common wavelengths used
in experiments, $\Delta_{H}$ is on the order of $50~{}\mu$m.

##  III Modelling of a Neutron Cavity

Figure 2: The average neutron intensity across a horizontal slice of the top
crystal shown in Fig. 1 is plotted as a function of the penetration depth
inside the top crystal. Note that the starting point was at bounce 110 in
order to avoid the initial high intensity region. The intensity drops sharply
within the first pendellösung period, indicating that the neutron is confined
within a band of width $\approx\Delta_{H}$ inside the cavity.

Dynamic diffraction theory predicts that in the Bragg geometry, neutrons
falling within a narrow range of momentum centered around the Bragg condition
(the Darwin width) are reflected with close to 100% probability. In a neutron
cavity composed of two perfect crystals, neutrons outside the Darwin width
will escape through the crystals within the first few bounces. Conversely,
neutrons inside this width are effectively confined, allowing for a great
number of bounces. Interestingly, the QI model predicts that this result can
be explained purely as a consequence of a quantum random walk: the total
neutron wavefunction is expressed as a sum over all the possible paths through
the Bragg lattice. The difference in phase accumulated by the different paths
results in constructive interference only for the paths which stay confined in
a small region close to the gap.

To model such a geometry, we use a single column matrix where the nodes
outside (inside) the crystals are free space (Bragg diffracting) operators.
The operator for the free space nodes is given by the matrix

$U_{\textrm{free}}=\ket{a_{i+1}}\bra{a_{i}}+\ket{b_{i-1}}\bra{b_{i}}$ (7)

while the operator for the Bragg diffracting nodes are given by Eqn. 2. As
shown in Fig. 1, without any information about transverse momentum, boundary
conditions, or incident angle, the model predicts that only after a few
bounces, the intensity is almost entirely localized in a narrow band around
the inter-crystal gap. Most neutrons that do not settle within this band are
either transmitted straight through the top of the crystal interferometer, or
bounce at most once and transmit through the bottom.

Figure 3: a) The neutron intensity remaining inside the cavity as a function
of the number of bounces, for a cavity with $D=12\Delta_{H}$ and
$t=87.5\Delta_{H}$. The intensity drops very sharply during the first few
bounces then stabilizes as the direct beam leaves the top crystal. A value for
the reflectivity of the crystal of $\approx 1-1.6\times 10^{-5}$ was extracted
by fitting to an inverse exponential between bounces 500 and 800. b) The
neutron intensity remaining inside the cavity after a length of 16000
$\Delta_{H}$. The neutron undergoes a number of bounces proportional to
$D^{-1}$. The final intensity in the cavity oscillates with period
$D=\Delta_{H}$.

Shown in Fig. 2 is the neutron average intensity across a horizontal slice of
the top crystal as a function of penetration depth into the top crystal. The
intensity drops sharply within the first $\Delta_{H}$, showing that the
confined neutrons do not penetrate very deeply inside the crystal.

###  III.1 Confined Intensity

With the QI model we can examine the neutrons which remain confined within the
cavity. Fig. 3 a) shows the confined intensity inside the cavity as a function
of the number of bounces, for cavity parameters $D=12\Delta_{H}$ and
$t=87.5\Delta_{H}$. It is to be noted that as the neutron progresses through
the cavity, the individual bounces become hard to resolve, and therefore here
we are considering a length of crystal corresponding to a geometrical path of
1000 bounces. The intensity drops sharply as the direct beam transmits
straight through the first crystal, and then drops slightly less at each
subsequent reflection. Eventually, it settles to an effectively constant value
of around $4\,\%$ of the incoming intensity. An estimation for the
reflectivity of the crystal as the number of bounces increases can be
extracted from this curve, by fitting it to an inverse exponential. The
reflectivity in the “stable” region between 500 and 800 bounces is found to be
$(\approx 1-1.6\times 10^{-5})$.

In Fig. 3b, the intensity remaining in the cavity after a length
$L=16000\Delta_{H}$ is plotted as a function of $D$. The confined intensity
oscillates with period $D=\Delta_{H}$. The QI model indicates that to maximize
the number of bounces for a given set of crystals, the spacing can be made
very small without losing much intensity at the exit, but should be made no
smaller than $\Delta_{H}/4$.

Figure 4: a) The intensity reflected from the bottom surface of the top
crystal as a function of position, for different intercrystal spacing
distances $D$. There are two different regimes: when the spacing is smaller
than the pendellösung length, the neutron state is represented by a standing
wave, whose frequency depends on crystal spacing. The second regime is where
the spacing is larger than the pendellösung length. Here the neutron bounces
are well-separated at first followed by self interference after many bounces.
There is a noticeable disruption around 175 $\Delta_{H}$ (indicated by an
downwards arrow) caused by the first reflection from the back face of the top
crystal. b) The frequency spectrum of the intensity profiles shown in Fig. 4a.
In the region of $D<\Delta_{H}$, there is one dominant frequency, which varies
with $D$. As the spacing increases, the neutron bounces become well-separated,
and new frequencies appear corresponding to the higher harmonics of the main
bounce frequency.

###  III.2 Cavity Modes

Simulation of the neutron cavity using the QI model shows that the neutrons
inside the cavity settle in one of two regimes, depending on the intercrystal
distance $D$. It should be noted that in the limit where $D\to 0$, the system
reduces to a simple Laue crystal of thickness $L$, in which case the neutron
will diverge to the edges of the Bormann triangle as predicted by DD theory.
However, for nonzero spacing, after the first few bounces, most of the neutron
current is confined within a small band of size of order $\Delta_{H}$ on the
inside surface of the cavity, and bounces back and forth without penetrating
very deeply into the crystal. Fig. 4a shows the simulated reflected intensity
on the surface of the top crystal throughout the cavity, for different values
of $D$. For the D $<\Delta_{H}$ regime, the neutron behaves like a standing
wave inside the cavity, with a period dependant on $D$. For the regime with
larger values of $D$ ($>2\Delta_{H}$), the bounces are well-separated and
localized at first. As the number of bounces increases, the neutron wave
packets spread and induce interference effects. This behavior is shown in Fig.
4b: for small $D$, there is one dominant frequency which changes with $D$. As
$D$ increases, more pairs of harmonics are introduced.

##  IV Experimental Implementation

An experimental implementation of a neutron cavity was performed at the NIOF
beamline at the National Institute of Standards and Technology (NIST) center
for neutron research (NCNR). The setup is shown in Fig. 5. A beam of neutrons
with wavelength 0.235 nm was propagated through a 10 mm wide silicon neutron
cavity composed of two 10 mm thick perfect-crystal silicon blades (220
reflection) attached to a common base. The theoretical pendellösung length for
this configuration is found to be $50.38$ $\mu$m. The neutrons underwent four
well-defined bounces before leaving the cavity at the exit. A scanning slit
and an integrating detector were placed behind the top crystal, and were used
to map the spatial intensity of neutrons along the crystal cavity.

Using the QI model we can simulate the experimental configuration. The
simulation parameters were chosen according to the equivalence relation of Eq.
5. As shown in Ref. Nahman-Lévesque  _et al._ (2022) we can account for the
experimental factors such as the spread of the incident beam, beam divergence,
and slit size through the analysis of a Bragg diffraction peak. Similar to the
methods of Ref. Nahman-Lévesque  _et al._ (2022) the intensity penetrating
through the top crystal was convolved with the measured shape of the exit
peak. The simulated intensity throughout the setup is shown as a false-color
map, and the simulated integrated intensity at the detector is shown above the
setup in a black, dashed line. The simulated intensity profile is in good
agreement with the measured intensity profile. It can be observed that the
majority of the contribution to the exiting beam of the cavity comes from the
classical bouncing path.

Figure 5: The experimental implementation of a neutron cavity using two
perfect-crystal silicon blades and a position sensitive neutron detector above
the top blade. Using the described QI model of DD we can simulate the neutron
propagation through the cavity. Here the nodes outside the two crystals act as
identity matrices, while a quantum random walk occurs inside the two crystals.
No further physics or boundary conditions are present. The geometric
trajectory of the neutron as it bounces back and forth is clearly visible
between the two crystals. Shown above in red is the experimental measurement
corresponding to this geometry. Overlaid in the black, dashed line, is the
intensity obtained via the QI model. Note that as shown in Ref. Nahman-
Lévesque  _et al._ (2022), the QI model accounts for experimental parameters
by convolving the intensity output with the shape of the exiting beam. Good
agreement is found between the simulation and experiment.

##  V Conclusion and Discussion

In conclusion, we have applied the QI model of dynamical diffraction to the
case of a neutron cavity composed of two perfect crystal silicon blades. The
model enables us to study the dependence of the cavity modes on the system
geometry. Full analysis is provided and good agreement is found between an
experimental implementation and the simulation of the particular setup.

Several exciting applications and proposed measurements rely on neutron
confinement inside such cavities. Our work presents an in-depth analysis of
the neutron behaviour inside the crystal blades and the crystal spacing.
Therefore, we expect that the QI model will become a standard and easily-
accessible tool used for experimental analysis that relies on neutron
dynamical diffraction.

##  VI Acknowledgements

This work was supported by the Canadian Excellence Research Chairs (CERC)
program, the Natural Sciences and Engineering Research Council of Canada
(NSERC) Discovery program, the Collaborative Research and Training Experience
(CREATE) program, the Canada First Research Excellence Fund (CFREF), and the
US Department of Energy, Office of Nuclear Physics, under Interagency
Agreement 89243019SSC000025. The authors would like to thank Ansel Himmer and
Tim Olsen for helping collect the experimental data.

## References

  * Rauch  _et al._ (1974) H Rauch, W Treimer, and U Bonse, “Test of a single crystal neutron interferometer,” Phys. Lett. A 47, 369–371 (1974).
  * Klepp  _et al._ (2014) J. Klepp, S. Sponar, and Y. Hasegawa, “Fundamental phenomena of quantum mechanics explored with neutron interferometers,” Progress of Theoretical and Experimental Physics 2014, 82A01–0 (2014).
  * Rauch and Werner (2015) Helmut Rauch and Samuel A Werner,  _Neutron interferometry: lessons in experimental quantum mechanics_ (Oxford University Press, New York, 2015).
  * Pushin  _et al._ (2015) DA Pushin, MG Huber, M Arif, CB Shahi, J Nsofini, CJ Wood, D Sarenac, and DG Cory, “Neutron interferometry at the national institute of standards and technology,” Advances in High Energy Physics 2015 (2015).
  * Huber  _et al._ (2019) Michael G Huber, Shannon F Hoogerheide, Muhammad Arif, Robert W Haun, Fred E Wietfeldt, Timothy C Black, Chandra B Shahi, Benjamin Heacock, Albert R Young, Ivar AJ Taminiau, _et al._ , “Overview of neutron interferometry at nist,” in  _EPJ Web of Conferences_ , Vol. 219 (EDP Sciences, 2019) p. 06001.
  * Colella  _et al._ (1975) R. Colella, A. W. Overhauser, and S. A. Werner, “Observation of Gravitationally Induced Quantum Interference,” Phys. Rev. Lett. 34, 1472–1474 (1975).
  * Lemmel  _et al._ (2015) H Lemmel, Ph Brax, AN Ivanov, T Jenke, G Pignol, M Pitschmann, T Potocar, M Wellenzohn, M Zawisky, and H Abele, “Neutron interferometry constrains dark energy chameleon fields,” Physics Letters B 743, 310–314 (2015).
  * Li  _et al._ (2016) Ke Li, Muhammad Arif, David G Cory, Robert Haun, Benjamin Heacock, Michael G Huber, Joachim Nsofini, Dimitry A Pushin, Parminder Saggu, Dusan Sarenac, _et al._ , “Neutron limit on the strongly-coupled chameleon field,” Physical Review D 93, 062001 (2016).
  * Rauch  _et al._ (1975) Helmut Rauch, Anton Zeilinger, Gerald Badurek, A Wilfing, W Bauspiess, and U Bonse, “Verification of coherent spinor rotation of fermions,” Physics Letters A 54, 425–427 (1975).
  * Clark  _et al._ (2015) Charles W Clark, Roman Barankov, Michael G Huber, Muhammad Arif, David G Cory, and Dmitry A Pushin, “Controlling neutron orbital angular momentum,” Nature 525, 504–506 (2015).
  * Sarenac  _et al._ (2016) Dusan Sarenac, Michael G Huber, Benjamin Heacock, Muhammad Arif, Charles W Clark, David G Cory, Chandra B Shahi, and Dmitry A Pushin, “Holography with a neutron interferometer,” Optics express 24, 22528–22535 (2016).
  * Jericha  _et al._ (1996) E Jericha, CJ Carlile, and H Rauch, “Performance of an improved perfect crystal neutron storage cavity,” Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 379, 330–334 (1996).
  * Jericha  _et al._ (1997) E Jericha, CJ Carlile, M Jaekel, and H Rauch, “Cold neutron storage by perfect crystals,” Physica B: Condensed Matter 234, 1066–1067 (1997).
  * Jericha  _et al._ (2000) E Jericha, DE Schwab, MR Jäkel, CJ Carlile, and H Rauch, “Neutron beam tailoring by accumulation between perfect crystal mirrors,” Physica B: Condensed Matter 283, 414–417 (2000).
  * Jaekel  _et al._ (2005) Martin R Jaekel, Erwin Jericha, and Helmut Rauch, “New developments in cold neutron storage with perfect crystals,” Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 539, 335–344 (2005).
  * Rauch (2001) H Rauch, “Quantum zeno-effect with polarized neutrons,” Physica B: Condensed Matter 297, 299–302 (2001).
  * Facchi  _et al._ (2003) Paolo Facchi, Yoichi Nakaguro, Hiromichi Nakazato, Saverio Pascazio, Makoto Unoki, and Kazuya Yuasa, “Optimization of a neutron-spin test of the quantum zeno effect,” Physical Review A 68, 012107 (2003).
  * Nsofini  _et al._ (2016) J. Nsofini, K. Ghofrani, D. Sarenac, D. G. Cory, and D. A. Pushin, “Quantum-information approach to dynamical diffraction theory,” Physical Review A 94 (2016), 10.1103/physreva.94.062311.
  * Nsofini  _et al._ (2019) J Nsofini, D Sarenac, DG Cory, and DA Pushin, “Coherence optimization in neutron interferometry through defocusing,” Physical Review A 99, 043614 (2019).
  * Nsofini  _et al._ (2017) Joachim Nsofini, Dusan Sarenac, Kamyar Ghofrani, Michael G Huber, Muhammad Arif, David G Cory, and Dmitry A Pushin, “Noise refocusing in a five-blade neutron interferometer,” Journal of Applied Physics 122, 054501 (2017).
  * Nahman-Lévesque  _et al._ (2022) O Nahman-Lévesque, D Sarenac, DG Cory, B Heacock, MG Huber, and DA Pushin, “Generalizing the quantum information model for dynamic diffraction,” Physical Review A 105, 022403 (2022).
  * Dombeck  _et al._ (2001) T Dombeck, R Ringo, DD Koetke, H Kaiser, K Schoen, SA Werner, and D Dombeck, “Measurement of the neutron reflectivity for bragg reflections off a perfect silicon crystal,” Physical Review A 64, 053607 (2001).
  * Gentile  _et al._ (2019) TR Gentile, MG Huber, DD Koetke, M Peshkin, M Arif, T Dombeck, DS Hussey, DL Jacobson, P Nord, DA Pushin, _et al._ , “Direct observation of neutron spin rotation in bragg scattering due to the spin-orbit interaction in silicon,” Physical Review C 100, 034005 (2019).


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

Jesús A. De Loera<EMAIL_ADDRESS>Department of Mathematics,
University of California, Davis
1 Shields Ave
Davis, CA 95616  William J. Wesley<EMAIL_ADDRESS>Department of
Mathematics, University of California, Davis
1 Shields Ave
Davis, CA 95616

_Dedicated to Bernd Sturmfels for his 60th birthday_

##  1 Introduction

Ramsey numbers are some of the most interesting and mysterious combinatorial
numbers [21]. In its simplest, most popular form, the 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$. 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 [43]. The goal of this article is to uncover further structure and
complexity of Ramsey numbers through algebraic-geometric means.

Our paper introduces two interpretations of $R(r,s)$ and related numbers and
graphs using polynomial ideals, varieties, and Nullstellensatz identities (see
[11] for an introduction). We tie the values and complexity of $R(r,s)$ to
encodings or models using systems of _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 Section 2.
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\leq r\leq 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 [23, 9]. Ramsey numbers as small as
$R(5,5)$ remain unknown, and the best known bounds are $43\leq R(5,5)\leq 48$.
See [19, 2]. The numbers $R(G_{1},G_{2})$ are known for some families of
graphs, but many cases remain open (see, for example, [42] 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 [47]
and [44], 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
_arrowing decision problem_ asks whether given three graphs $F,G,H$ is there
is a red blue edge-coloring of $F$ that contains either a red $G$ or a blue
$H$? This decision problem was shown to be in co-NP for fixed choices of $G,H$
[6]. Later Schaefer [46] 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 [46, 6, 25].

In recent years, Pak and collaborators [40, 29, 41] 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: _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 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 relsat [3], following the work of successful
computations in Ramsey theory using SAT solvers in, for example, [26] and [8]
(see also the database at [38]). 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$.

$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)$
---|---|---|---|---|---|---
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

### Our Contributions:

Our first contribution, in Section 2, is to 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)\leq RG(n,r+1,s)$, follow immediately from Theorem
1.

######  Theorem 1.

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)$.

$\displaystyle p_{H,i}:=\prod_{e\in E(H)}x_{i,e}$ $\displaystyle=0$
$\displaystyle{\forall i,1\leq i\leq k,\quad\forall H\subseteq K_{n},\ H\cong
G_{i}},$ (1) $\displaystyle q_{e}:=1+\sum_{i=1}^{k}x_{i,e}$ $\displaystyle=0$
$\displaystyle{\forall e\in E},$ (2) $\displaystyle u_{i,j,e}:=x_{i,e}x_{j,e}$
$\displaystyle=0$ $\displaystyle\forall e\in E,\ \forall i,j,\ i\neq j.$ (3)

When $k=2$, $G_{1}=K_{r}$, and $G_{2}=K_{s}$, the _Ramsey ideal_ $RI(n,r,s)$
is ideal of the polynomial ring
$\overline{\mathbb{F}_{2}}[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

$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$

A key interesting consequence of Theorem 1 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 _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

$\sum_{i=1}^{m}\beta_{i}f_{i}=1.$ (4)

We call such an identity (4) a Nullstellensatz certificate. The 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, [7, 37, 16, 13, 17, 14, 34, 15]. Here we show a surprising connection
of Ramsey numbers to Nullstellensatz certificates.

In Theorem 2 we give a general construction for Nullstellensatz certificates
of Ramsey number upper bounds using the polynomial encoding from Theorem 1. In
other words, assuming the number of vertices of a Ramsey ideal is $n$ and
$n\geq 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
restricted online Ramsey numbers $\tilde{R}(G_{1},\dots,G_{k};n)$, first
introduced by Conlon et al. in [10]. These numbers are defined in terms of the
following _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})\leq\binom{R(G_{1},\dots,G_{k})}{2}$, but it was
shown in [20] that in the case of 2-color classical Ramsey numbers that
$\tilde{R}(r,r;n)\leq\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, [5, 33].

######  Theorem 2.

If $n\geq 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 Theorem 1. In
particular, in the case of 2-color classical Ramsey numbers, this implies that
if $n\geq 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.

The proof of Theorem 2 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 Theorem 1 to suit several well-known
problems in Ramsey theory (see, for example, [21, 32]). We express these
problems using the general framework below.

######  Definition 3.

Let $k$ be a positive integer, and let $\\{S_{n}\\}$ be a sequence of sets.
For $c$ in $[k]$, the set of colors, let $\mathcal{P}_{n}^{c}$ be a subset of
$S_{n}$. A triple $A:=(\\{S_{n}\\},\\{\mathcal{P}_{n}^{c}\\};k)$ is a Ramsey-
type problem if the following hold:

  1. (i)

$S_{i}\subseteq S_{i+1}$ for $i\geq 1$,

  2. (ii)

$\mathcal{P}^{c}_{i}\subseteq\mathcal{P}^{c}_{i+1}$ for $i\geq 1$, $1\leq
c\leq k$,

  3. (iii)

There exists an integer $N$ such that for all $i\geq N$ and every $k$-coloring
of $S_{i}$ there is a color $c$ and some element $X\in\mathcal{P}^{c}_{i}$
where each element of $X$ is assigned color $c$.

The smallest such $N$ is called the Ramsey-type number for $A$, and is denoted
$R(A)$.

We see that in the problem of computing classical Ramsey numbers $R(r,s)$, we
have $S_{n}=E(K_{n})=\\{(i,j):1\leq i<j\leq n\\}$. The families
$\mathcal{P}_{n}^{1}$ and $\mathcal{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 _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
$\mathcal{P}_{n}^{c}=\\{\\{x,y,z\\}:\\{x,y,z\\}\subseteq[n],x+y=z\\}$.

As we see in Section 2, the encoding in Theorem 1 can be modified to give
bounds for many other Ramsey-type numbers, including Schur, Rado, van der
Waerden, and Hales-Jewett numbers [21, 32]. 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.

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\mathcal{P}_{n}^{c}$ where every element of $X$ is assigned color $c$.
Define the number
$\tilde{R}_{k}(\mathcal{P}_{n}^{1},\dots,\mathcal{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}(\mathcal{P}_{n}^{1},\mathcal{P}_{n}^{2};S_{n})$ with
$\mathcal{P}_{n}$ and $S_{n}$ defined as above for the Ramsey number $R(r,s)$.
Theorem 4 generalizes Theorems 1 and 2.

######  Theorem 4.

Let $A=(\\{S_{n}\\},\\{\mathcal{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
$\overline{\mathbb{F}_{2}}$.

$\displaystyle p_{X,c}:=\prod_{s\in X}x_{c,s}$ $\displaystyle=0$
$\displaystyle{\forall X\in\mathcal{P}_{n}^{c}},\ 1\leq c\leq k$
$\displaystyle q_{s}:=1+\sum_{i=1}^{k}x_{i,s}$ $\displaystyle=0$
$\displaystyle{\forall s\in S_{n}},$ $\displaystyle u_{i,j,s}:=x_{i,s}x_{j,s}$
$\displaystyle=0$ $\displaystyle\forall s\in S_{n},\ \forall i,j,\ 1\leq
i<j\leq k.$

If $n\geq R(A)$, then the minimal degree of a Nullstellensatz certificate for
this system is at most
$\tilde{R}_{k}(\mathcal{P}_{n}^{1},\dots,\mathcal{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\mathcal{P}_{n}^{c}$ contains an object that is not assigned color $c$.

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 Section 2 we give some examples of
values of $\tilde{R}(r,s;n)$ and
$\tilde{R}(\mathcal{P}_{n}^{1},\dots,\mathcal{P}_{n}^{k};S_{n})$ and discuss
the Nullstellensatz certificates for the associated polynomial systems.

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, [1, 24, 18, 48, 30, 28, 45] and the references therein).

Here we show that lower bounds for Ramsey numbers can be obtained by showing
that a certain _Ramsey polynomial_ $f_{r,s,n}$ is not identically zero. Its
coefficients are new combinatorial numbers $E_{n,k,r,H}$ which we call
_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 Section 2.

Theorem 5 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 [1].

######  Theorem 5.

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$.

##  2 Ramsey and Hilbert’s Nullstellensatz

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)\leq n$.

Many combinatorial problems can be encoded as a system of polynomial
equations, including colorings, independence sets, partitions, etc. (see,
e.g., [7, 4, 12, 16, 17, 27, 35, 37]). 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 [31]. However, the
exponential bounds should not be bad news for combinatorialists. First, it has
been shown [33] 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 [22], and a recent paper [39]
gives substantial improvements to these bounds. The bounds we give in Theorems
2 and 4 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, [36, 34, 14] 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 [13, 14, 34].

We now prove Theorem 1 of our encoding for Ramsey numbers over
$\overline{\mathbb{F}_{2}}$ below.

###### Proof of Theorem 1.

Suppose there is a solution $\mathbf{x}$ to the system over
$\overline{\mathbb{F}_{2}}$. 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 x
where

$x_{i,e}=\begin{cases}1&\text{if }\chi(e)=i,\\\
0&\text{otherwise}.\end{cases}$

One can check easily that 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^{\prime})}x_{i,e}$ if and
only if $H$ is a subgraph of $H^{\prime}$. 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^{\prime})}x_{i,e}$ with
$H^{\prime}\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. ∎

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

######  Example 6.

For all $r$, there exists a Nullstellensatz certificate of degree
$\binom{r}{2}-1$ of the statement $R(r,2)\leq r$.

###### Proof.

Label the edges of $K_{r}$ from 1 to $n=\binom{r}{2}$. The following identity
is a certificate that $R(r,2)\leq r$. Polynomials in parentheses are part of
the system of equations in Theorem 1.

$\displaystyle 1$
$\displaystyle=(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$
$\displaystyle\quad+x_{1,1}x_{1,2}\cdots x_{1,n-1}(1+x_{1,n}+x_{2,n})$
$\displaystyle\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})$ $\displaystyle\quad+(x_{1,1}\cdots x_{1,n})$

∎

In the proof of Theorem 2, 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 Example 6,
this is not a concern since the order in which Builder selects edges does not
matter, and in fact $\tilde{R}(r,2)=r$. Painter can simply color every edge
Builder selects the first color, and Builder wins only when all $\binom{r}{2}$
edges are selected.

The proofs of Theorems 2 and 4 are similar, and in fact Theorem 2 follows from
Theorem 4, but for the sake of concreteness we begin with Theorem 2.

###### Proof of Theorem 2.

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\leq 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

$\sum_{i=1}^{k}\sum_{H\cong G_{i}}\beta_{H,i}p_{H,i}+\sum_{e\in
E}\gamma_{e}q_{e}=1.$ (5)

Denote the left-hand side of Equation 6 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:

  1. 1.

Expand and simplify $L$ so that $L$ is a sum of monomials. If $L=1$, then we
are done.

  2. 2.

Otherwise, at least one term in $L$ is a nonconstant monomial $f$.

  3. 3.

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}\leftarrow\beta_{H,i}+\frac{f}{p_{H,i}}.$

This results in $L\leftarrow L+f$, which cancels the original $f$ in the
certificate since it is an expression over $\overline{\mathbb{F}_{2}}$, which
has characteristic 2.

  4. 4.

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}\leftarrow\gamma_{e}+f.$

Since $fq_{e}=f+\sum_{i=1}^{k}fx_{i,e}$, we obtain $L\leftarrow
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$.

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$.

∎

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)\leq 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}$.
Then for the next three turns, Builder selects the edges
$w_{1}w_{2},w_{1}w_{3}$, and $w_{2}w_{3}$, and Painter must construct a
monochromatic triangle. However, if Builder plays poorly and selects, for
example, the edges $(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 _no_ monochromatic
triangles, and this leads to a higher degree certificate.

The proof of Theorem 2 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 Theorems 2. 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
Theorem 1, which is better than the bound given in Theorem 2. We now give the
proof of Theorem 4.

###### Proof of Theorem 4.

Let $A=(\\{S_{n}\\},\\{\mathcal{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\mathcal{P}_{n}^{c}$ where Painter has colored all the elements of $X$
color $c$. Let $d:=\tilde{R}_{k}(\mathcal{P}_{n};S_{n})$. If Builder follows
an optimal strategy for choosing edges, then the game lasts at most $d$ turns,
that is $t\leq 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

$\sum_{(X,c)\in\mathcal{P}_{n}}\beta_{X,c}p_{X,c}+\sum_{s\in
S_{n}}\gamma_{s}q_{s}=1.$ (6)

Denote the left-hand side of Equation 6 by $L$. Initialize $\beta_{X,c}$ to 0
for all $(X,c)\in\mathcal{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:

  1. 1.

Expand and simplify $L$ so that $L$ is a sum of monomials. If $L=1$, then we
are done.

  2. 2.

Otherwise, at least one term in $L$ is a nonconstant monomial $f$.

  3. 3.

If $\sigma(f)$ is a completed game state, then $p_{X,c}$ divides $f$ for some
$(X,c)\in\mathcal{P}_{n}$. Then set

$\beta_{X,c}\leftarrow\beta_{X,c}+\frac{f}{p_{X,c}}.$

This results in $L\leftarrow L+f$, which cancels the original $f$ in the
certificate since it is an expression over $\overline{\mathbb{F}_{2}}$, which
has characteristic 2.

  4. 4.

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}\leftarrow\gamma_{s}+f.$

Since $fq_{s}=f+\sum_{i=1}^{k}fx_{i,s}$, we obtain $L\leftarrow
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$.

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$. ∎

As an application of Theorem 4, let $\mathcal{E}$ be a linear equation, and
let $R_{k}(\mathcal{E})$ denote the $k$-color _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
$\mathcal{P}_{n}^{c}:=X_{n,\mathcal{E}}$ for all $c$. If $R_{k}(\mathcal{E})$
exists, then $(\\{[n]\\},\\{\mathcal{P}_{n}^{c}\\};k)$ is a Ramsey-type
problem, and we have the following corollary.

######  Corollary 7.

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\leq m_{j}\leq n\\}$ be the set of solutions over $[n]$ to $\mathcal{E}$.
Then for every $n$, the following system has no solution over
$\overline{\mathbb{F}_{2}}$ if and only if $n\geq R_{k}(\mathcal{E})$.

$\displaystyle\prod_{j=1}^{t}x_{i,m_{j}}$ $\displaystyle=0$
$\displaystyle\forall(m_{1},\dots,m_{t})\in X_{n,\mathcal{E}},\ 1\leq i\leq
k,$ $\displaystyle 1+\sum_{i=1}^{k}x_{i,m}$ $\displaystyle=0$ $\displaystyle
1\leq m\leq n,$ $\displaystyle x_{i,m}x_{j,m}$ $\displaystyle=0$
$\displaystyle 1\leq m\leq n,1\leq i<j\leq k.$

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$.

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$ [32]. 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])\leq 5$, and the
minimal degree of a Nullstellensatz certificate for the system of equations in
Corollary 7 is at most 4. In fact, some computations show the minimal degree
is 2.

Similarly, the encoding in Theorem 1 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 Theorem 4, we have $S(2)\leq 5$ if and only if the following system of
equations has no solutions over $\overline{\mathbb{F}_{2}}$.

$\displaystyle 1+x_{1,i}+x_{2,i}=0,$ $\displaystyle 1\leq i\leq 5,$
$\displaystyle\hskip 18.0pt\begin{aligned} x_{i,1}x_{i,2}&=0,&&\hskip
17.0ptx_{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}$
$\displaystyle\left.\begin{aligned} \\\ \\\ \end{aligned}\right\\}i=1,2$

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]$. The following identity
(over $\overline{\mathbb{F}_{2}}$) is a degree 3 Nullstellensatz certificate
for the above system of equations, which is an improvement on the bound in
Theorem 4.

$\displaystyle 1$
$\displaystyle=(x_{2,5}+x_{1,4}x_{1,5}+x_{1,5}x_{2,3}x_{2,4})(1+x_{1,1}+x_{2,1})+$
$\displaystyle(x_{1,1}x_{1,3}+x_{2,1}x_{2,5}+x_{1,1}x_{1,5}x_{2,4}+x_{1,1}x_{2,3}x_{2,5}+x_{1,3}x_{1,5}x_{2,4}+x_{1,4}x_{1,5}x_{2,1})(1+x_{1,2}+x_{2,2})+$
$\displaystyle(x_{1,1}x_{2,5}+x_{2,4}x_{1,5}+x_{1,1}x_{1,5}x_{2,4})(1+x_{1,3}+x_{2,3})+$
$\displaystyle(x_{1,5}+x_{1,1}x_{1,3}x_{1,5}+x_{1,1}x_{1,3}x_{2,2}+x_{1,2}x_{2,1}x_{2,5})(1+x_{1,4}+x_{2,4})+$
$\displaystyle(1+x_{1,1}x_{1,3})(1+x_{1,5}+x_{2,5})+$
$\displaystyle(x_{1,3}+x_{2,3}x_{2,5}+x_{2,4}x_{1,5})x_{1,1}x_{1,2}+(x_{2,1}x_{1,5}+x_{2,1}x_{2,5})x_{1,2}x_{2,4}$
$\displaystyle(x_{2,5}+x_{1,4}x_{1,5})x_{2,1}x_{2,2}+(x_{1,1}x_{1,3}+x_{1,1}x_{1,5}+x_{1,3}x_{3,5})x_{2,2}x_{2,4}+(x_{1,5}+x_{2,2})x_{1,1}x_{1,3}x_{1,4}+$
$\displaystyle(x_{1,1}x_{1,4}x_{1,5})+x_{2,4}(x_{1,2}x_{1,3}x_{1,5})+x_{1,5}(x_{2,1}x_{2,3}x_{2,4})+x_{1,2}(x_{2,1}x_{2,4}x_{2,5})+x_{1,1}(x_{2,2}x_{2,3}x_{2,5}).$

The _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
[21]. Let $AP_{n,t}$ denote the set of all $t$-term arithmetic progressions in
$[n]$. Then setting $\mathcal{P}_{n}^{c}:=AP_{n,t}$ for all $c$, then
$(\\{[n]\\},\\{\mathcal{P}_{n}^{c}\\};k)$ is a Ramsey-type problem as well.

######  Corollary 8.

For every $n$, the following system has no solution over
$\overline{\mathbb{F}_{2}}$ if and only if $n\geq w(t,k)$.

$\displaystyle\prod_{j=1}^{t}x_{i,m_{j}}$ $\displaystyle=0$
$\displaystyle\forall(m_{1},\dots,m_{t})\in AP_{n,t},\ 1\leq i\leq k,$
$\displaystyle 1+\sum_{i=1}^{k}x_{i,m}$ $\displaystyle=0$ $\displaystyle 1\leq
m\leq n,$ $\displaystyle x_{i,m}x_{j,m}$ $\displaystyle=0$ $\displaystyle
1\leq m\leq n,1\leq i<j\leq k.$

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.

We give one last consequence of Theorem 4. For fixed parameters $t$ and $n$, a
_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
_Hales-Jewett number $HJ(t,k)$_ is the smallest number $n$ such that every
$k$-coloring of $[t]^{n}$ contains a monochromatic combinatorial line [21].
Let $L_{t,n}$ denote the set of all combinatorial lines on $t^{n}$. If we set
$\mathcal{P}_{n}^{c}=L_{t,n}$ for all $c$, then
$(\\{[t]^{n},\\{\mathcal{P}_{n}^{c}\\};k)$ is a Ramsey-type problem.

######  Corollary 9.

For every $n$, the following system has no solution over
$\overline{\mathbb{F}_{2}}$ if and only if $n\geq HJ(t,k)$.

$\displaystyle\prod_{j=1}^{t}x_{i,v^{j}}$ $\displaystyle=0$
$\displaystyle\forall(v^{1},\dots,v^{t})\in L_{t,n},\ 1\leq i\leq k,$
$\displaystyle 1+\sum_{i=1}^{k}x_{i,v}$ $\displaystyle=0$ $\displaystyle
v\in[t]^{n},$ $\displaystyle x_{i,v}x_{j,v}$ $\displaystyle=0$ $\displaystyle
v\in[t]^{n},1\leq i<j\leq k.$

The number of solutions to this system is the number of $k$-colorings of
$[t]^{n}$ that do not contain any monochromatic combinatorial lines.

##  3 Ramsey and Alon’s Combinatorial Nullstellensatz

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, [1, 18, 28, 24, 48, 30] and the references therein).

######  Theorem 10 (Alon, [1]).

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$.

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:

$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).$ (7)

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)\leq
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 Theorem
10, this representative is the zero polynomial if and only if $R(r,s)\leq|V|$.

In the proof of Theorem 5, we focus on the case when $r=s$ and study the
polynomial $f_{r,r,n}$. Before proving Theorem 5, 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 _$(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 _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.

1234512345123451234512345123451234512345

We now prove Theorem 5.

###### Proof of Theorem 5.

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{r}{2}\right)\left(\sum_{e\in
E(S)}x_{e}+\binom{r}{2}\right)\equiv\left(\sum_{\\{e,e^{\prime}\\}\in\binom{E(S)}{2}}2x_{e}x_{e^{\prime}}+\binom{r}{2}-\binom{r}{2}^{2}\right).$

Taking the product of these terms over all $r$-subsets of $V$ gives

$f(x)\equiv\prod_{S\subset V,\
|S|=r}\left(\sum_{\\{e,e^{\prime}\\}\in\binom{E(S)}{2}}2x_{e}x_{e^{\prime}}+\binom{r}{2}-\binom{r}{2}^{2}\right).$
(8)

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

$f\equiv\sum_{H\subseteq G}a_{H}m_{H}.$ (9)

We now calculate the coefficients $a_{H}$ in terms of $E_{n,k,r,H}$.

In the expansion of the right-hand side of (8), 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_{e}x_{e^{\prime}}$
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

$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}.$
(10)

If $a_{H}$ is nonzero for some graph $H$, then the multilinear representative
of $f$ is nonzero, and by Theorem 10 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. ∎

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\\}\\}$.

$H$ $k$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---|---
$\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

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.

##  4 Acknowledgements

We thank Susan Margulies for helpful discussions and assistance with
computations.

## References

  * [1] N. Alon.  Combinatorial Nullstellensatz.  Combinatorics, Probability, and Computing, 8:7–29, 1999.
  * [2] V. Angeltveit and B. McKay.  $R(5,5)\leq 48$.  J. Graph Theory, 89(1):5–13, 2018.
  * [3] R. Bayardo.  Relsat.  https://github.com/roberto-bayardo/relsat.
  * [4] D. Bayer.  The Division Algorithm and the Hilbert Scheme.  PhD thesis, Harvard University, 1982.
  * [5] W. D. Brownawell.  Bounds for the degrees in the Nullstellensatz.  Ann. of Math. (2), 126(3):577–591, 1987.
  * [6] S. A. Burr.  On the computational complexity of Ramsey-type problems.  In Mathematics of Ramsey theory, volume 5 of Algorithms Combin., pages 46–52. Springer, Berlin, 1990.
  * [7] S. Buss and T. Pitassi.  Good degree bounds on Nullstellensatz refutations of the induction principle.  volume 57, pages 162–171. 1998.  Complexity 96—The Eleventh Annual IEEE Conference on Computational Complexity (Philadelphia, PA).
  * [8] Y. Chang, J. A. De Loera, and W. J. Wesley.  Rado numbers and SAT computations.  In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, ISSAC ’22, page 333–342, New York, NY, USA, 2022\. Association for Computing Machinery.
  * [9] M. Codish, M. Frank, A. Itzhakov, and A. Miller.  Computing the Ramsey number $R(4,3,3)$ using abstraction and symmetry breaking.  Constraints, 21(3):375–393, 2016.
  * [10] D. Conlon, J. Fox, A. Grinshpun, and X. He.  Online Ramsey numbers and the subgraph query problem.  In I. Bárány, G. O. H. Katona, and A. Sali, editors, Building Bridges II, pages 159–194. Springer, 2019.
  * [11] D. A. Cox, J. Little, and D. O’Shea.  Ideals, varieties, and algorithms.  Undergraduate Texts in Mathematics. Springer, Cham, fourth edition, 2015\.  An introduction to computational algebraic geometry and commutative algebra.
  * [12] J. A. De Loera.  Gröbner bases and graph colorings.  Beiträge Algebra Geom., 36(1):89–96, 1995.
  * [13] J. A. De Loera, J. Lee, P. N. Malkin, and S. Margulies.  Hilbert’s Nullstellensatz and an algorithm for proving combinatorial infeasibility.  Proceedings of the Twenty-first International Symposium on Symbolic and Algebraic Computation, pages 197–206, 2008.
  * [14] J. A. De Loera, J. Lee, P. N. Malkin, and S. Margulies.  Computing infeasibility certificates for combinatorial problems through Hilbert’s Nullstellensatz.  J. Symbolic Comput., 46(11):1260–1283, 2011.
  * [15] J. A. De Loera, J. Lee, S. Margulies, and J. Miller.  Weak orientability of matroids and polynomial equations.  European J. Combin., 50:56–71, 2015.
  * [16] J. A. De Loera, J. Lee, S. Margulies, and S. Onn.  Expressing combinatorial problems by systems of polynomial equations and Hilbert’s Nullstellensatz.  Combinatorics, Probability and Computing, 18(4):551–582, 2009\.
  * [17] J. A. De Loera, S. Margulies, M. Pernpeintner, E. Riedl, D. Rolnick, G. Spencer, D. Stasi, and J. Swenson.  Graph-coloring ideals: Nullstellensatz certificates, Gröbner bases for chordal graphs, and hardness of Gröbner bases.  In ISSAC’15—Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation, pages 133–140. ACM, New York, 2015.
  * [18] Z. Dvořák, S. Norin, and L. Postle.  List coloring with requests.  J. Graph Theory, 92(3):191–206, 2019.
  * [19] G. Exoo.  A lower bound for $R(5,5)$.  J. Graph Theory, 13(1):97–98, 1989.
  * [20] D. Gonzalez, X. He, and H. Zheng.  An upper bound for the restricted online Ramsey number.  Discrete Math., 342(9):2564–2569, 2019.
  * [21] R. Graham, B. Rothschild, and J. Spencer.  Ramsey Theory.  Wiley, 2nd edition, 1980.
  * [22] B. Green and T. Tao.  The distribution of polynomials over finite fields, with applications to the Gowers norms.  Contrib. Discrete Math., 4(2):1–36, 2009.
  * [23] R. Greenwood and A. Gleason.  Combinatorial relations and chromatic graphs.  Canadian J. Math., 7:1–7, 1955.
  * [24] L. Guth.  Polynomial methods in combinatorics, volume 64 of University Lecture Series.  American Mathematical Society, Providence, RI, 2016.
  * [25] H. Haanpää.  Computational methods for Ramsey numbers.  Research Report A65, Helsinki University of Technology Laboratory for Theoretical Computer Science, 2000.
  * [26] M. Heule.  Schur number five.  Proceedings of AAAI-18, pages 6598–6606, 2018.
  * [27] C. J. Hillar and T. Windfeldt.  Algebraic characterization of uniquely vertex colorable graphs.  J. Combin. Theory Ser. B, 98(2):400–414, 2008.
  * [28] J. Hladký, D. Kráľ, and U. Schauz.  Brooks’ theorem via the Alon-Tarsi theorem.  Discrete Math., 310(23):3426–3428, 2010.
  * [29] C. Ikenmeyer and I. Pak.  What is in #P and what is not?  CoRR, abs/2204.13149, 2022.
  * [30] G. Károlyi and Z. L. Nagy.  A simple proof of the Zeilberger-Bressoud $q$-Dyson theorem.  Proc. Amer. Math. Soc., 142(9):3007–3011, 2014.
  * [31] J. Kollár.  Sharp effective Nullstellensatz.  Journal of the AMS, 1(4):963–975, 1988.
  * [32] B. M. Landman and A. Robertson.  Ramsey theory on the integers, volume 73 of Student Mathematical Library.  American Mathematical Society, Providence, RI, second edition, 2014.
  * [33] D. Lazard.  Algèbre linéaire sur $K[X_{1},\cdots,X_{n}]$, et élimination.  Bull. Soc. Math. France, 105(2):165–190, 1977.
  * [34] B. Li, B. Lowenstein, and M. Omar.  Low degree Nullstellensatz certificates for 3-colorability.  Electron. J. Combin., 23(1):Paper 1.6, 12, 2016.
  * [35] L. Lovász.  Stable sets and polynomials.  volume 124, pages 137–153. 1994.  Graphs and combinatorics (Qawra, 1990).
  * [36] S. Margulies.  Computer Algebra, Combinatorics, and Complexity: Hilbert’s Nullstellensatz and NP-complete Problems.  PhD thesis, 2008.
  * [37] S. Margulies, S. Onn, and D. V. Pasechnik.  On the complexity of Hilbert refutations for partition.  J. Symbolic Comput., 66:70–83, 2015.
  * [38] B. McKay.  Ramsey Graphs.  https://users.cecs.anu.edu.au/b̃dm/data/ramsey.html.
  * [39] G. Moshkovitz and J. Yu.  Sharp effective finite-field Nullstellensatz, 2022.  preprint, arXiv, https://arxiv.org/abs/2111.09305.
  * [40] I. Pak.  Complexity problems in enumerative combinatorics.  In Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, pages 3153–3180. World Sci. Publ., Hackensack, NJ, 2018.
  * [41] I. Pak.  What is a combinatorial interpretation?  preprint, arXiv, https://arxiv.org/pdf/2209.06142.pdf, 2022.
  * [42] S. Radziszowski.  Small Ramsey numbers.  Electronic Journal of Combinatorics, 2021.
  * [43] F. Ramsey.  On a problem of formal logic.  Proceedings of the London Mathematical Society, 30:264–286, 1930\.
  * [44] A. Sah.  Diagonal Ramsey via effective quasirandomness.  preprint, arXiv, https://arxiv.org/abs/2005.09251, 2020.
  * [45] L. Sauermann and Y. Wigderson.  Polynomials that vanish to high order on most of the hypercube.  Journal of the London Mathematical Society.
  * [46] M. Schaefer.  Graph Ramsey theory and the polynomial hierarchy (extended abstract).  In Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), pages 592–601. ACM, New York, 1999.
  * [47] J. Spencer.  Ramsey’s theorem—a new lower bound.  J. Combinatorial Theory Ser. A, 18:108–115, 1975.
  * [48] T.-L. Wong and X. Zhu.  Every graph is $(2,3)$-choosable.  Combinatorica, 36(1):121–127, 2016.