Rado numbers: SAT methods and connections to Nullstellensatz complexity

on YouTube ↗38m

" summary

Computations produce hundreds of new exact Rado numbers and a SAT method that generates SAT-based formulas for three infinite families of three‑color Rado numbers, using standard CDCL solvers (CaDiCaL) to find thousands of two‑color, a few hundred three‑color and about ten four‑color values with most 2–3 color instances solved in under a minute. A constructive reduction produces bounded Nullstellensatz certificates and proves Nullstellensatz degree ≤ online Rado number via Builder‑Painter games, with explicit gaps observed (e.g. Schur: degree 2 vs Rado 5).

AI-written summary · about

" chapters (18)

1. 0:00Introduction
2. 1:40Origins of Ramsey Theory
3. 2:26Schur's Theorem
4. 3:57Van der Waerden's Theorem
5. 4:33Van der Waerden numbers
6. 5:58Rado numbers
7. 6:46Rado's theorem
8. 8:46SAT successes in Ramsey theory
9. 11:08Three-variable equations
10. 15:03SAT encoding
11. 16:07SAT solving
12. 18:132-color Generalized Schur Numbers
13. 19:01Upper bounds: Variables indexed by polynomials
14. 20:29Current work
15. 24:55Polynomial encodings
16. 26:11Hilbert's Nullstellensatz
17. 27:01Online Ramsey numbers
18. 29:45Future work