Paperlane

no. 11 · Monday 9 November 2026

A Structural Lower Bound for the Ramsey Number of the Petersen Graph

Yuan Si

math.CO

Abstract

In this note, we investigate the diagonal Ramsey number of the Petersen graph, denoted by \(R(\mathcal{P}, \mathcal{P})\). To the best of our knowledge, the dynamic survey \textit{Small Ramsey Numbers} (Revision \#18, 2026) records the lower bound as 19, established by Harborth and Krause. We construct a novel 2-coloring on the complete graph \(K_{20}\) that avoids any monochromatic Petersen graph. By defining the blue graph as the complement of the red graph, we utilize a specific join graph structure \(K_{9,9} \vee \overline{K_2}\). We rigorously prove its Petersen-free property, thereby improving the previously documented lower bound to \(R(\mathcal{P}, \mathcal{P}) \ge 21\). Furthermore, we demonstrate the limit of this structural family by showing that the natural extension \(K_{9,9} \vee \overline{K_3}\) contains a Petersen subgraph.

fields
Combinatorics
pdf ↗ page arXiv:2611.09347 ↗