Bounds on Small Ramsey Numbers by Semidefinite Programming
SIAM Review · 30.06.2026 · 68 (2) · 385-403
DOI: 10.1137/25m1827554 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Review, online erschienen am 13.05.2026. Verfasst von Bernard Lidický und 1 weiteren Autor:innen. Die Arbeit nennt 69 Literaturangaben. Gefördert von: National Science Foundation, Simons Collaboration grant, Simons Foundation.
Abstract (Originalsprache)
Finding exact Ramsey numbers is a problem typically restricted to relatively small graphs. The flag algebra method introduced by Razborov in 2007 was developed to find asymptotic results for very large graphs, so it seems that the method should not be suitable for finding small Ramsey numbers. But this intuition is wrong, and we will develop a technique to do just that in this paper. We find new upper bounds for many small graph and hypergraph Ramsey numbers. As a result, we prove several exact values. The main power of the method relies on utilizing semidefinite programming to find certificates that are sums of squares. We hope that this technique will be adapted to address other questions for smaller graphs with the flag algebra method.
Förderung
- National Science Foundation
- Simons Collaboration grant
- Simons Foundation
- Scott Hanna professorship
- University of Colorado Denver
Zitieren
APA
Lidický, B., & Pfender, F. (2026). Bounds on Small Ramsey Numbers by Semidefinite Programming. SIAM Review, 68(2), 385-403. https://doi.org/10.1137/25m1827554
Vancouver
Lidický B, Pfender F. Bounds on Small Ramsey Numbers by Semidefinite Programming. SIAM Review. 2026;68(2):385-403. doi:10.1137/25m1827554
BibTeX
@article{Lidick2026,
author = {Lidický, Bernard and Pfender, Florian},
title = {Bounds on Small Ramsey Numbers by Semidefinite Programming},
journal = {SIAM Review},
year = {2026},
volume = {68},
number = {2},
pages = {385--403},
doi = {10.1137/25m1827554}
}
EUVIMED