PreprintarXiv licencearXiv
A Computer-Assisted Proof that R(5,10;5,8)=21 for the Generalized Threshold Ramsey Number
Abstract
We prove that the generalized threshold Ramsey number R(5,10;5,8) equals 21. This number corresponds to the set Ramsey number r_5(10,8) introduced by Harborth. The proof is computer-assisted. We first enumerate all (4,6;5,8)-good and (5,10;4,4)-good graphs. Then we apply the lucky-vertex inequality derived from the McKay--Radziszowski edge identity to filter candidate pairs for a gluing search, and encode the remaining cases as SAT instances. The search yields exactly 17 non-isomorphic (5,10;5,8;20)-good graphs. Finally, we exclude all one-vertex extensions of these 17 graphs, which proves that no (5,10;5,8;21)-good graph exists.Additionally, we update the tabulation of small set Ramsey numbers r_5(m,n) for 1 <= m,n <= 10.
Related
- The Primitive Generalized Fermat Equation x^3+y^5=z^7: A computer-assisted proof
- Bounds on the Threshold Ramsey Multiplicity of Ramsey Numbers with Many Colors
- The Ramsey threshold for trees versus odd cycles
- The logarithmic exponent of the Ramsey number r(4,t)
- An upper bound of 61 for the Ramsey number $R(3,3,3,3)$
BibTeX
@misc{guo2026computerassisted,
title = {{A Computer-Assisted Proof that R(5,10;5,8)=21 for the Generalized Threshold Ramsey Number}},
author = {Wancai Guo and Min Wan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29584},
eprint = {2610.29584},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29584},
}
RIS
TY - UNPB
TI - A Computer-Assisted Proof that R(5,10;5,8)=21 for the Generalized Threshold Ramsey Number
AU - Wancai Guo
AU - Min Wan
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29584
UR - https://arxiv.org/abs/2610.29584
AB - We prove that the generalized threshold Ramsey number R(5,10;5,8) equals 21. This number corresponds to the set Ramsey number r_5(10,8) introduced by Harborth. The proof is computer-assisted. We first enumerate all (4,6;5,8)-good and (5,10;4,4)-good graphs. Then we apply the lucky-vertex inequality derived from the McKay--Radziszowski edge identity to filter candidate pairs for a gluing search, and encode the remaining cases as SAT instances. The search yields exactly 17 non-isomorphic (5,10;5,8;20)-good graphs. Finally, we exclude all one-vertex extensions of these 17 graphs, which proves that no (5,10;5,8;21)-good graph exists.Additionally, we update the tabulation of small set Ramsey numbers r_5(m,n) for 1 <= m,n <= 10.
ER -