pith. sign in

arxiv: 2605.22116 · v1 · pith:TN3YG3VDnew · submitted 2026-05-21 · 🧮 math.CO

Diagonal Ramsey numbers for wheels

Maoxuan Li , Masaki Kashima , Yaping Mao This is my paper

Pith reviewed 2026-05-22 04:43 UTC · model grok-4.3

classification 🧮 math.CO
keywords Ramsey numberswheel graphsdiagonal Ramsey numbersgraph coloringsextremal graph theorymulti-color Ramsey numbers
0
0 comments X

The pith

The diagonal Ramsey number R(W_n, W_n) satisfies 3n-2 to 6n-6 for even n at least 8 and 2n to (9n-7)/2 for odd n at least 7.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper tightens the known estimates for the smallest complete graph size that forces a monochromatic wheel in any red-blue edge coloring. Previous work had looser ranges; the new constructions and proofs narrow the gap to linear functions of n. The results also supply recursive relations that bound the k-color versions of the same number in terms of smaller cases. A reader would care because exact Ramsey numbers remain elusive even for simple graphs like wheels, and linear bounds give a clearer picture of their growth.

Core claim

The authors prove that for even n ≥ 8 the Ramsey number R(W_n, W_n) lies between 3n-2 and 6n-6, established by exhibiting a 2-edge-coloring of K_{3n-3} with no monochromatic wheel and showing that every coloring of K_{6n-6} contains one. For odd n ≥ 7 the interval is 2n to (9n-7)/2. They further derive recursive upper bounds relating the k-color Ramsey number for W_n to the (k-1)-color number for a smaller wheel.

What carries the argument

The wheel graph W_n formed by adding a hub vertex joined to every vertex of a cycle on n-1 vertices; the Ramsey number R(G,G) is the smallest N such that every 2-coloring of K_N contains a monochromatic copy of G.

If this is right

  • The two-color Ramsey number for wheels grows linearly with the number of vertices.
  • The gap between lower and upper bounds is at most a small constant factor for large n.
  • Recursive relations allow the k-color Ramsey numbers to be bounded using the two-color case for smaller wheels.
  • The same style of construction and forcing argument extends from the two-color to the multi-color setting.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The linear upper bounds imply that wheels are among the sparser graphs whose Ramsey numbers do not grow exponentially.
  • For concrete small n one could check whether the new lower-bound colorings are optimal by exhaustive search on the boundary sizes.
  • The recursive multi-color bounds open a route to studying the asymptotic growth rate as the number of colors increases.

Load-bearing premise

The explicit colorings that avoid monochromatic wheels on the smaller complete graphs and the arguments that force a monochromatic wheel on the larger ones hold for all n in the stated parity and size ranges.

What would settle it

An explicit red-blue coloring of K_{6n-7} with no monochromatic W_n for some even n ≥ 8 would falsify the upper bound, or a coloring of K_{3n-3} containing a monochromatic W_n would falsify the lower bound.

read the original abstract

The Ramsey number $\mathrm{R}(G_1,G_2)$ is the smallest integer $N$ such that any red-blue coloring of the edges of the complete graph $K_N$ contains either a red copy of $G_1$ or a blue copy of $G_2$. In 2022, the third author and others gave lower and upper bounds of the Ramsey number $\mathrm{R}(W_n,W_n)$, where $W_n$ is the wheel graph with $n$ vertices. In this paper, we improve their bounds by showing that $3n-2\leq \mathrm{R}(W_n,W_n)\leq 6n-6$ for even $n\geq 8$ and $2n\leq \mathrm{R}(W_n,W_n)\leq \frac{9n-7}{2}$ for odd $n\geq 7$. Furthermore, we give recursive bounds for the $k$-colored Ramsey number for $W_n$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript improves known bounds on the diagonal Ramsey number R(W_n, W_n) for the wheel graph W_n on n vertices. It establishes the inequalities 3n-2 ≤ R(W_n, W_n) ≤ 6n-6 for all even n ≥ 8 and 2n ≤ R(W_n, W_n) ≤ (9n-7)/2 for all odd n ≥ 7, supported by explicit constructions for the lower bounds and direct or inductive arguments for the upper bounds. The paper also supplies recursive bounds for the k-colored Ramsey numbers R_k(W_n).

Significance. If the stated constructions and forcing arguments hold for the full ranges, the results tighten the 2022 bounds referenced in the abstract and add recursive multicolor estimates. Explicit lower-bound colorings of K_{3n-3} (even case) and K_{2n-1} (odd case) together with the upper-bound proofs would constitute a concrete advance in the study of Ramsey numbers for wheels.

major comments (1)
  1. Main theorems (even and odd cases): the universal statements require that the lower-bound colorings of K_{3n-3} and K_{2n-1} contain no monochromatic W_n for every n in the infinite families, and that every coloring of the larger complete graphs forces a monochromatic wheel. A single failure for any n ≥ 8 (even) or n ≥ 7 (odd) would falsify the claimed inequalities; the manuscript must therefore supply either a uniform general argument or explicit verification that covers all n without gaps.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need to confirm that the claimed bounds hold uniformly over the infinite families. We address the major comment below.

read point-by-point responses

  1. Referee: [—] Main theorems (even and odd cases): the universal statements require that the lower-bound colorings of K_{3n-3} and K_{2n-1} contain no monochromatic W_n for every n in the infinite families, and that every coloring of the larger complete graphs forces a monochromatic wheel. A single failure for any n ≥ 8 (even) or n ≥ 7 (odd) would falsify the claimed inequalities; the manuscript must therefore supply either a uniform general argument or explicit verification that covers all n without gaps.

    Authors: We appreciate the referee drawing attention to this requirement. The lower-bound colorings are presented via explicit, uniform constructions that apply to every even n ≥ 8 (respectively every odd n ≥ 7). For even n the 3-partite coloring of K_{3n-3} is defined by fixing three sets of size n-1 and coloring intra-set edges red and inter-set edges according to a fixed cyclic pattern; the proof that this coloring is W_n-free proceeds by contradiction on the possible hub-and-rim structure and uses only the parity of n and the set sizes, which hold for the entire family. The odd-case construction on K_{2n-1} is likewise uniform and its W_n-freeness is established by a single counting argument that does not depend on the specific value of n beyond the stated range. The upper-bound arguments are either direct (for small n) or inductive on n, with the inductive step again relying only on the parity distinction and the numerical inequalities that are valid for all n in the families. We have inserted a short clarifying paragraph immediately after the statements of the main theorems to emphasize that both the constructions and the forcing arguments are uniform and contain no gaps. revision: yes

Circularity Check

0 steps flagged

No circularity: bounds from explicit constructions and direct arguments

full rationale

The paper derives improved Ramsey bounds for wheels via explicit 2-colorings of K_{3n-3} and K_{2n-1} that avoid monochromatic W_n (lower bounds) together with direct or inductive arguments showing that larger complete graphs force a monochromatic wheel (upper bounds), plus recursive multicolor extensions. These steps are self-contained mathematical constructions and proofs that do not reduce to fitted parameters, self-definitions, or load-bearing self-citations. The reference to 2022 work by the third author merely contextualizes the improvement and is not invoked to justify the new results themselves. No equations or claims in the derivation chain collapse by construction to the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The results rest on standard definitions of Ramsey numbers, wheel graphs, and edge colorings together with combinatorial constructions and proof techniques. No free parameters are fitted to data, no new entities are postulated, and no ad-hoc axioms beyond ordinary graph theory are invoked.

axioms (1)
  • standard math Basic properties of complete graphs, edge colorings, and wheel graphs as defined in standard graph theory.
    Invoked throughout the definitions and statements of the Ramsey numbers R(W_n, W_n).

pith-pipeline@v0.9.0 · 5692 in / 1355 out tokens · 51919 ms · 2026-05-22T04:43:07.604213+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    J. A. Bondy and U. S. R. Murty.Graph theory. Springer Publishing Company, Incorporated, 2008

    work page 2008

  2. [2]

    Brandt, R

    S. Brandt, R. Faudree, and W. Goddard. Weakly pancyclic graphs.Journal of Graph Theory, 27(3):141–176, 1998

    work page 1998

  3. [3]

    S. A. Burr and P. Erdős. Generalizations of a Ramsey-theoretic result of Chvátal.Journal of Graph Theory, 7(1):39–51, 1983

    work page 1983

  4. [4]

    Y. Chen, Y. Zhang, and K. Zhang. The Ramsey numbers of paths versus wheels.Discrete Mathematics, 290(1):85–87, 2005

    work page 2005

  5. [5]

    V. Chvátal. Tree-complete graph Ramsey numbers.Journal of Graph Theory, 1(1):93–93, 1977

    work page 1977

  6. [6]

    G. A. Dirac. Some theorems on abstract graphs.Proceedings of the London Mathematical Society, 3(1):69–81, 1952

    work page 1952

  7. [7]

    Erdős, R

    P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp. On cycle-complete graph ramsey numbers.Journal of Graph Theory, 2(1):53–64, 1978

    work page 1978

  8. [8]

    R. J. Faudree and B. McKay. A conjecture of Erdős and the Ramsey numberR(W6).Journal of Combinatorial Mathematics and Combinatorial Computing, 13:23–31, 1993

    work page 1993

  9. [9]

    R. J. Faudree and R. H. Schelp. All Ramsey numbers for cycles in graphs.Discrete Mathe- matics, 8(4):313–329, 1974

    work page 1974

  10. [10]

    R. L. Graham, B. L. Rothschild, and J. H. Spencer.Ramsey theory. John Wiley & Sons, 1991

    work page 1991

  11. [11]

    Combinatorialrelationsandchromaticgraphs.Canadian Journal of Mathematics, 7:1–7, 1955

    R.E.GreenwoodandA.M.Gleason. Combinatorialrelationsandchromaticgraphs.Canadian Journal of Mathematics, 7:1–7, 1955

    work page 1955

  12. [12]

    Harborth and I

    H. Harborth and I. Mengersen. All Ramsey numbers for five vertices and seven or eight edges. Discrete Mathematics, 73(1-2):91–98, 1988

    work page 1988

  13. [13]

    G. R. Hendry. Ramsey numbers for graphs with five vertices.Journal of Graph Theory, 13(2):245–248, 1989

    work page 1989

  14. [14]

    Károlyi and V

    G. Károlyi and V. Rosta. Generalized and geometric Ramsey numbers for cycles.Theoretical Computer Science, 263(1-2):87–98, 2001. 11

    work page 2001

  15. [15]

    Y. Mao, Z. Wang, C. Magnant, and I. Schiermeyer. Ramsey and Gallai-Ramsey number for wheels.Graphs and Combinatorics, 38(2):42, 2022

    work page 2022

  16. [16]

    Radziszowski and X

    S. Radziszowski and X. Jin. Paths, cycles and wheels in graphs without antitriangles.Centre for Discrete Mathematics and Computing: Australasian Journal of Combinatorics, 9, 1994

    work page 1994

  17. [17]

    V. Rosta. On a Ramsey-type problem of J. A. Bondy and P. Erdős. ii.Journal of Combina- torial Theory, Series B, 15(1):105–120, 1973

    work page 1973

  18. [18]

    Salman and H

    A. Salman and H. J. Broersma. On Ramsey numbers for paths versus wheels.Discrete mathematics, 307(7-8):975–982, 2007

    work page 2007

  19. [19]

    L. Shi. Ramsey numbers of long cycles versus books or wheels.European Journal of Combi- natorics, 31(3):828–838, 2010

    work page 2010

  20. [20]

    Zhang, Y

    L. Zhang, Y. Chen, and T. E. Cheng. The Ramsey numbers for cycles versus wheels of even order.European Journal of Combinatorics, 31(1):254–259, 2010. 12

    work page 2010