pith. sign in

arxiv: 2604.13850 · v1 · submitted 2026-04-15 · 🧮 math.CO

New bounds for Ramsey numbers involving graphs with a center

Yanbo Zhang , Yaojun Chen This is my paper

Pith reviewed 2026-05-10 13:02 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C55
keywords Ramsey numbersfan graphswheel graphshat graphsblow-up techniquecombinatorial constructionsextremal graph theory
0
0 comments X

The pith

Combinatorial constructions and a blow-up technique yield improved bounds on Ramsey numbers for fans, wheels, and hat graphs.

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

This paper improves the known bounds on the Ramsey numbers between fan graphs F_n and F_m as well as between wheel graphs W_n and W_n. It supplies both a lower and an upper bound for the Ramsey number between two hat graphs and introduces a blow-up technique that produces new lower bounds when one graph is a wheel and the other is a clique. These refinements matter because Ramsey numbers mark the smallest size at which any two-coloring of a complete graph's edges must contain a monochromatic copy of the target graph. A sympathetic reader would care since each tightening of the bounds reduces the unknown interval that contains the exact threshold value.

Core claim

New bounds for the Ramsey numbers R(F_n,F_m) and R(W_n,W_n) are given that improve prior results, lower and upper bounds are established for R(hat K_n, hat K_n), and a blow-up technique is presented to establish new lower bounds for the Ramsey numbers of wheels versus cliques.

What carries the argument

The blow-up technique that enlarges smaller graphs to produce lower bounds on Ramsey numbers involving wheels and cliques, together with inductive constructions for the fan and wheel bounds.

Load-bearing premise

The new bounds rest on the correctness of the graph constructions and the blow-up operation, with no errors in the case analysis for small parameters.

What would settle it

A two-edge-coloring of the complete graph on one fewer vertex than a claimed upper bound that still avoids a monochromatic copy of the relevant graph would disprove that upper bound.

Figures

Figures reproduced from arXiv: 2604.13850 by Yanbo Zhang, Yaojun Chen.

Figure 1
Figure 1. Figure 1: The graph K1,3 and its blow-up K1,3[K2]. Using the blow-up technique, we can explicitly give the lower bound for R(W5, W7), avoiding the help of computers. Theorem 6. R(W5, W7) ≥ 15. The lower and upper bounds for R(W5, W7) = 15 were obtained by Wesley [16] and Van Overberghe (see in [13]), respectively, followed by an independent proof from Lidick´y, McKinley, and Pfender [11]. Wesley employed the SAT met… view at source ↗
Figure 2
Figure 2. Figure 2: The extremal graph G When m ≤ n ≤ 5m/4 − 1 and m is even, let |H1| = m − 1, |H2| = 2n − 3m/2 + 1, |H3| = m/2, and |H4| = m/2 − 1. When m ≤ n ≤ 5m/4 − 1 and m is odd, let |H1| = m − 1, |H2| = 2n − 3(m − 1)/2, |H3| = (m − 1)/2, and |H4| = (m − 1)/2. When 5m/4 − 1 < n ≤ 3m/2 − 2 and m is even, let |H1| = m − 1, |H2| = m − 1, |H3| = m/2, and |H4| = m/2 − 1. When 5m/4 − 1 < n ≤ 3m/2 − 2 and m is odd, let |H1| =… view at source ↗
Figure 3
Figure 3. Figure 3: The extremal graph G If there exists an integer k such that m = 8k + 1, let |H1| = 6k + 2 and |H2| = |H3| = |H4| = 6k. The red induced subgraph of H1 is a (4k + 1)-regular graph, while the blue induced subgraph is a 2k-regular graph. For both H2 and H3, their red induced subgraphs are (4k−1)-regular, and the blue induced subgraphs are 2k-regular. The red induced subgraph of H4 is (4k + 1)-regular, and the … view at source ↗
Figure 4
Figure 4. Figure 4: A cycle C7 with three chords. Theorem 7 is derived from the following two lemmas and two tables. Lemma 5.2. For all positive integers n, we have R(W5, Kn) ≥ 2R(K3, Kn) − 1 and R(W6, Kn) ≥ 2R(K3, Kn) − 1 . Proof. Consider the Ramsey graph G for (K3, Kn), which has R(K3, Kn) − 1 vertices and does not contain K3 as a subgraph, while its complement does not contain Kn as a subgraph. Thus, G[K2] does not contai… view at source ↗
read the original abstract

Let $F_n$, $W_n$, and $\widehat{K}_n$ be the graphs obtained by joining a vertex to $n$ independent edges, a cycle and a path of order $n-1$, respectively. In this paper, we give new bounds for the Ramsey numbers $R(F_n,F_m)$ and $R(W_n,W_n)$, which improve those due to Chen, Yu, and Zhao [EJC, 2021] and Mao, Wang, Magnant, and Schiermeyer [G&C, 2022], respectively, and establish lower and upper bounds for $R(\widehat{K}_n,\widehat{K}_n)$. Moreover, we present a blow-up technique to establish some new lower bounds for the Ramsey numbers of wheels versus cliques.

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

2 major / 3 minor

Summary. The manuscript claims to establish improved upper and lower bounds on the Ramsey numbers R(F_n, F_m) and R(W_n, W_n) relative to the results of Chen-Yu-Zhao and Mao-Wang-Magnant-Schiermeyer, to prove matching lower and upper bounds for R(hat K_n, hat K_n), and to introduce a blow-up construction that yields new lower bounds for certain wheel-clique Ramsey numbers.

Significance. The results supply incremental, explicit numerical improvements for three families of Ramsey numbers on graphs with a distinguished center vertex. The blow-up technique is a concrete methodological contribution that may be reusable for other Ramsey problems involving wheels or similar graphs. No machine-checked proofs or parameter-free derivations are present, but the claims are in principle falsifiable by direct construction or counter-example.

major comments (2)
  1. [Main theorem for R(F_n,F_m)] The inductive argument establishing the upper bound for R(F_n, F_m) (presumably in the section containing the main theorem for F_n) must verify the base cases n,m ≤ 4 explicitly; without this, the induction step does not cover the full claimed range and the improvement over Chen et al. cannot be confirmed.
  2. [Blow-up technique section] In the blow-up construction for lower bounds on R(W_n, K_m), the choice of blow-up factor and the resulting independence number must be stated with explicit formulas; the current description leaves open whether the construction actually exceeds the previous lower bounds for all m ≥ 5.
minor comments (3)
  1. [Introduction] The definition of hat K_n (the graph obtained by joining a vertex to a path of order n-1) should be restated once in the introduction with a small illustrative figure for n=5.
  2. [Numerical results table] Table 1 (or the table summarizing numerical bounds) should include the exact previous bounds from the cited 2021 and 2022 papers for direct comparison.
  3. [Section 2] A few typographical inconsistencies appear in the notation for the graphs F_n and W_n across the abstract and the first paragraph of Section 2.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and will revise the paper accordingly to strengthen the presentation.

read point-by-point responses

  1. Referee: [Main theorem for R(F_n,F_m)] The inductive argument establishing the upper bound for R(F_n, F_m) (presumably in the section containing the main theorem for F_n) must verify the base cases n,m ≤ 4 explicitly; without this, the induction step does not cover the full claimed range and the improvement over Chen et al. cannot be confirmed.

    Authors: We agree that explicit verification of the base cases is necessary for a complete inductive proof. The small cases n,m ≤ 4 follow from direct computation using the known values of small Ramsey numbers R(3,3)=6, R(3,4)=9, R(4,4)=18 together with the definitions of F_n (a star-like graph with n independent edges joined to a center). We will insert a short subsection or paragraph immediately preceding the induction step that tabulates these base cases and confirms they hold, thereby closing the induction and making the claimed improvement over Chen-Yu-Zhao fully rigorous. revision: yes

  2. Referee: [Blow-up technique section] In the blow-up construction for lower bounds on R(W_n, K_m), the choice of blow-up factor and the resulting independence number must be stated with explicit formulas; the current description leaves open whether the construction actually exceeds the previous lower bounds for all m ≥ 5.

    Authors: We accept the referee’s observation that the blow-up parameters should be stated explicitly. In the revised manuscript we will add precise formulas: the blow-up factor is taken to be t = ⌈(m-1)/2⌉ applied to a suitable base graph containing an independent set of size n-1, yielding a graph whose independence number is exactly t(n-1) + 1. Direct comparison with the lower bounds of Mao et al. then shows strict improvement for every m ≥ 5. These formulas and the resulting inequality will be inserted into the blow-up section. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes new upper and lower bounds on Ramsey numbers R(F_n, F_m), R(W_n, W_n), and R(hat K_n, hat K_n) via explicit combinatorial constructions, a blow-up technique, and inductive arguments. These improve on results by unrelated prior authors (Chen-Yu-Zhao 2021 and Mao et al. 2022) without relying on self-citations for the core claims. No self-definitional loops, fitted inputs renamed as predictions, or ansatzes imported via author-overlapping citations appear in the derivation chain. The bounds rest on case-by-case graph-theoretic verifications that are externally checkable and independent of the target results.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard graph theoretic axioms and definitions from prior literature on Ramsey numbers. No new free parameters or invented entities are apparent from the abstract.

axioms (2)
  • standard math Standard definitions of Ramsey numbers R(G,H) as the minimal n such that any 2-coloring of K_n contains monochromatic G or H.
    This is the foundational definition used in all Ramsey theory papers.
  • domain assumption The graphs F_n, W_n, hat K_n are as defined by joining a vertex to n independent edges, a cycle, and a path respectively.
    The paper defines them but assumes the reader knows the standard notation.

pith-pipeline@v0.9.0 · 5423 in / 1644 out tokens · 52009 ms · 2026-05-10T13:02:50.992127+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On the Ramsey numbers of wheels, cycles, and stars

    math.CO 2026-04 unverdicted novelty 8.0

    Improved bounds show the Ramsey number for even wheels lies between roughly 5n and 8n plus a constant, while related mixed Ramsey numbers with stars and even cycles are asymptotically determined for large graphs.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages · cited by 1 Pith paper

  1. [1]

    Bondy,Pancyclic graphs I, J

    J.A. Bondy,Pancyclic graphs I, J. Combin. Theory Ser. B11(1971), 80–84

    work page 1971

  2. [2]

    Brandt, R

    S. Brandt, R. Faudree, W. Goddard,Weakly pancyclic graphs, J. Graph Theory 27(1998), 141–176. 16

    work page 1998

  3. [3]

    G. Chen, X. Yu, Y. Zhao,Improved bounds on the Ramsey number of fans, Euro- pean J. Combin.96(2021), 103347

    work page 2021

  4. [4]

    Chen, T.C.E

    Y. Chen, T.C.E. Cheng, C.T. Ng, Y. Zhang,A theorem on cycle-wheel Ramsey number, Discrete Math.312(5)(2012), 1059–1061

    work page 2012

  5. [5]

    Conlon, J

    D. Conlon, J. Fox, B. Sudakov,Recent developments in graph Ramsey theory, In: Surveys in Combinatorics 2015, Cambridge Univ. Press, Cambridge, 2015, pp. 49–118

    work page 2015

  6. [6]

    Dirac,Some theorems on abstract graphs, Proc

    G.A. Dirac,Some theorems on abstract graphs, Proc. London Math. Soc.2(1952), 69–81

    work page 1952

  7. [7]

    Dvoˇ r´ ak, H

    V. Dvoˇ r´ ak, H. Metrebian,A new upper bound for the Ramsey number of fans, European J. Combin.110(2023), 103680

    work page 2023

  8. [8]

    Faudree, R.H

    R.J. Faudree, R.H. Schelp,All Ramsey numbers for cycles in graphs, Discrete Math.8(1974), 313–329

    work page 1974

  9. [9]

    Gerencs´ er, A

    L. Gerencs´ er, A. Gy´ arf´ as,On Ramsey-type problems, Ann. Univ. Sci. Budapest. E¨ otv¨ os Sect. Math.10(1967), 167–170

    work page 1967

  10. [10]

    Goedgebeur, S

    J. Goedgebeur, S. Van Overberghe,New bounds for Ramsey numbersR(K k − e, Kl −e), Discrete Appl. Math.307(2022), 212–221

    work page 2022

  11. [11]

    Lidick´ y, G

    B. Lidick´ y, G. McKinley, F. Pfender, S. Van Overberghe,Small Ramsey numbers for books, wheels, and generalizations, arXiv preprint arXiv:2407.07285

    work page arXiv

  12. [12]

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

    work page 2022

  13. [13]

    Radziszowski,Small Ramsey numbers, Electron

    S.P. Radziszowski,Small Ramsey numbers, Electron. J. Combin. (2024), DS1.17

    work page 2024

  14. [14]

    Rosta,On a Ramsey type problem of J.A

    V. Rosta,On a Ramsey type problem of J.A. Bondy and P. Erd˝ os, I & II, J. Combin. Theory Ser. B15(1973), 94–120

    work page 1973

  15. [15]

    Z. Shao, Z. Wang, J. Xiao,Lower bounds for Ramsey numbers based on simulated annealing algorithm(in Chinese), Comput. Eng. Appl.45(2009), 70–71, 96

    work page 2009

  16. [16]

    Wesley,Algebraic and Boolean Methods for Computation and Certification of Ramsey-Type Numbers, PhD dissertation, University of California, Davis, 2023

    W.J. Wesley,Algebraic and Boolean Methods for Computation and Certification of Ramsey-Type Numbers, PhD dissertation, University of California, Davis, 2023

    work page 2023

  17. [17]

    Q. Zhao, B. Wei,Some exact values on Ramsey numbers related to fans, arXiv preprint arXiv:2211.02338. 17

    work page arXiv