Four new values of small Ramsey numbers: R(F3,F5)=21, R(F4,F5)=22, R(K3,3,K3,4)=19 and R(K2,4,K3,5)=19

Let F_n = K_1 + nK_2 be the fan consisting of n triangles sharing one vertex. We show that R(F_3,F_5) = 21 and R(F_4,F_5) = 22; previously only 21 ≤ R(F_3,F_5) ≤ 26 and 21 ≤ R(F_4,F_5) ≤ 28 followed from general results. We also show R(K_{3,3},K_{3,4}) = 19 and R(K_{2,4},K_{3,5}) = 19, which are listed as 19–20 in Table IVb of Radziszowski's dynamic survey. The lower bound R(F_4,F_5) ≥ 22 is, to our knowledge, new and is given by an explicit colouring of K_21. The upper bounds are computer assisted. For fans, a short argument bounds the colour degrees, and a case split on the maximum degree of one colour fixes the neighbourhood of one vertex. Each case, and each bipartite instance, is refuted by CaDiCaL 2.1.3, and the unsatisfiability of every formula is certified by an LRAT proof accepted by the formally verified checker cake_lpr. The encodings were checked semantically on small orders, and the deposited files were verified to be exactly the generator output plus audited fan and matching clauses. Files: newvals.pdf is the note (7 pages). newvals_data.zip contains the lower-bound colourings with independent checkers, all CNF formulas whose proofs were checked, the generators, the cake_lpr logs, the CNF audit and encoding-validation logs, the LaTeX source, and SHA-256 checksums of every file. The LRAT proofs are not included because of their size (about 63 GB); they can be regenerated with the included script. Not peer reviewed. The search code, the computations and a first draft of the note were produced with the help of an AI assistant (Claude, Anthropic). The author is responsible for the content.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-01
DOI
https://doi.org/10.5281/zenodo.23840068
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Four new values of small Ramsey numbers: R(F3,F5)=21, R(F4,F5)=22, R(K3,3,K3,4)=19 and R(K2,4,K3,5)=19

Yuichi Murakami
2 links
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

Four new values of small Ramsey numbers: R(F3,F5)=21, R(F4,F5)=22, R(K3,3,K3,4)=19 and R(K2,4,K3,5)=19

Yuichi Murakami
preprint en

Abstract

Let F_n = K_1 + nK_2 be the fan consisting of n triangles sharing one vertex. We show that R(F_3,F_5) = 21 and R(F_4,F_5) = 22; previously only 21 ≤ R(F_3,F_5) ≤ 26 and 21 ≤ R(F_4,F_5) ≤ 28 followed from general results. We also show R(K_{3,3},K_{3,4}) = 19 and R(K_{2,4},K_{3,5}) = 19, which are listed as 19–20 in Table IVb of Radziszowski's dynamic survey. The lower bound R(F_4,F_5) ≥ 22 is, to our knowledge, new and is given by an explicit colouring of K_21. The upper bounds are computer assisted. For fans, a short argument bounds the colour degrees, and a case split on the maximum degree of one colour fixes the neighbourhood of one vertex. Each case, and each bipartite instance, is refuted by CaDiCaL 2.1.3, and the unsatisfiability of every formula is certified by an LRAT proof accepted by the formally verified checker cake_lpr. The encodings were checked semantically on small orders, and the deposited files were verified to be exactly the generator output plus audited fan and matching clauses. Files: newvals.pdf is the note (7 pages). newvals_data.zip contains the lower-bound colourings with independent checkers, all CNF formulas whose proofs were checked, the generators, the cake_lpr logs, the CNF audit and encoding-validation logs, the LaTeX source, and SHA-256 checksums of every file. The LRAT proofs are not included because of their size (about 63 GB); they can be regenerated with the included script. Not peer reviewed. The search code, the computations and a first draft of the note were produced with the help of an AI assistant (Claude, Anthropic). The author is responsible for the content.

Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon