Return to Colloquia & Seminar listing
PhD Exit Seminar: Algebraic and Boolean Methods for Computation and Certification of Ramsey-type Numbers
Special Events| Speaker: | Jack Wesley, UC Davis |
| Location: | 2112 MSB |
| Start time: | Fri, May 26 2023, 3:10PM |
Ramsey numbers and their variants are among the most interesting and
well-studied numbers
in combinatorics. These numbers are often difficult to compute, and few
exact values are known. We explore them through algebraic and Boolean
methods.
On the computational side, we present new results on numbers in
arithmetic Ramsey theory. In particular, we give exact formulas for
three infinite families of Rado numbers using Boolean formulas and SAT
solvers.
Regarding certification, we study encodings for the problem of computing
Ramsey numbers using systems of polynomial equations. When a system has
no solution, there is an associated polynomial identity called a
Nullstellensatz certificate. We show that the complexity of the
certificates for our encodings are related to so-called Builder-Painter
games and the restricted online Ramsey numbers studied by Conlon et al.
Click here to join via Zoom: https://ucdavis.zoom.us/j/6325991814