pith. sign in

arxiv: 2605.26826 · v2 · pith:LKLNJ6JZnew · submitted 2026-05-26 · 🧮 math.CO

Ramsey goodness of complete multipartite graphs with one large part

Shaonan Mi , Ye Wang This is my paper

Pith reviewed 2026-06-29 17:18 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C55
keywords ramsey goodnesscomplete multipartite graphsramsey numberschromatic numbersmallest non-divisorgraph theory
0
0 comments X

The pith

Complete multipartite graphs with one large part are G-good for large n precisely when the smallest non-divisor of each fixed part size satisfies a condition on G.

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

The paper extends the 1983 Burr et al. result by characterizing exactly which graphs G make the complete multipartite graph K with p fixed parts of sizes α1 to αp and one part of size n into a G-good graph once n grows large enough. A graph H is G-good when its Ramsey number r(G,H) exactly equals the expression (χ(G)−1)(n−1) + s(G), where χ(G) is the chromatic number of G and s(G) is the size of its smallest color class in any proper χ(G)-coloring. The characterization is given in terms of snd(αi), the smallest integer that does not divide αi, for each i from 1 to p. A reader would care because the result supplies an explicit criterion that decides when the Ramsey number takes this simple closed form for an entire infinite family of host graphs H.

Core claim

For any fixed α1,…,αp the paper determines the graphs G such that K_{α1,…,αp,n} is G-good for all sufficiently large n; the determining condition on G is expressed using the values snd(αi) for i=1 to p.

What carries the argument

The smallest non-divisor snd(αi) of each fixed part size αi, which is used to classify the graphs G for which the multipartite graph satisfies the exact Ramsey-number formula.

If this is right

  • For every G that meets the snd-based criterion the equality r(G, K_{α1,…,αp,n}) = (χ(G)−1)(n−1) + s(G) holds once n exceeds a threshold that depends only on G and the αi's.
  • The 1983 result for G of the form K2 + mK1 is recovered as the special case in which the snd condition is automatically satisfied.
  • The threshold for n can be taken uniform across all G that share the same snd profile with respect to the given α's.
  • The chromatic number and minimum color-class size of G fully determine the asymptotic Ramsey number against this family of multipartite graphs.

Where Pith is reading between the lines

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

  • The same snd-based criterion might classify G-goodness for other host graphs that are nearly balanced complete multipartite graphs rather than having one dominant part.
  • Direct computation of small Ramsey numbers for concrete αi and candidate G could verify the boundary cases of the characterization before the large-n regime begins.
  • The result opens the possibility of similar divisor-based classifications in Ramsey problems that involve other invariants besides chromatic number.

Load-bearing premise

The goodness property for large n is completely decided by the smallest non-divisor of each smaller part size, with no further hidden restrictions on G.

What would settle it

An explicit pair (G, α1,…,αp) where the smallest-non-divisor condition on G is violated yet r(G, K_{α1,…,αp,n}) still equals (χ(G)−1)(n−1)+s(G) for infinitely many n, or conversely where the condition holds yet the equality fails for all large n.

Figures

Figures reproduced from arXiv: 2605.26826 by Shaonan Mi, Ye Wang.

Figure 1
Figure 1. Figure 1: Two representative cases showing that P6 + K1 ⊆ T + 7K1. 2 Preliminaries In this section, we list and prove some preliminary results, which we need for the main proofs. To state these results, we first introduce some standard notation. For graph G, let ∆(G) be the maximum degree of G. For v ∈ V (G), the of v in G is denoted by NG(v) or N(v) if no danger of confusion, and for U ⊆ V (G), let dU (v) be the nu… view at source ↗
read the original abstract

For graph $G$, a connected graph $H$ of order $n$ is $G$-good if $r(G,H)=(\chi(G)-1)(n-1)+s(G)$, where $\chi(G)$ is the chromatic number of $G$ and $s(G)$ is the minimum size of a color class in a $\chi(G)$-coloring of $G$. Let $K_{\alpha_{1},\ldots ,\alpha_{p},n}$ be the complete $(p+1)$-partite graph with partite sets of sizes $\alpha_1,\ldots,\alpha_p,n$. Burr, Faudree, Rousseau and Schelp (1983) showed that $K_{\alpha_1,\ldots,\alpha_p,n}$ are $(K_2+mK_1)$-good for large $n$. We determine graphs $G$ such that $K_{\alpha_{1},\ldots ,\alpha_{p},n}$ are $G$-good for large $n$. The characterization depends on $\mathrm{snd}(\alpha_i)$, the smallest non-divisor of $\alpha_i$, where $1\le i\le p$.

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 / 2 minor

Summary. The manuscript extends the 1983 Burr–Faudree–Rousseau–Schelp theorem by characterizing those graphs G for which the unbalanced complete multipartite graph K_{α_1,…,α_p,n} is G-good whenever n is sufficiently large. The characterization is expressed in terms of the smallest non-divisor snd(α_i) of each fixed part size α_i (1≤i≤p).

Significance. If the stated characterization is correct, the result supplies an explicit, arithmetic criterion that completely determines the Ramsey-goodness property for this family of graphs, directly generalizing the known special case G=K_2+mK_1. The dependence on snd(α_i) isolates the relevant divisibility obstruction and therefore offers a clean, falsifiable prediction for the asymptotic Ramsey number r(G,H) in this setting.

major comments (1)
  1. [Main theorem / proof of characterization] The central claim asserts that the property of being G-good for large n is completely determined by the values snd(α_i). The manuscript must therefore contain an exhaustive case analysis showing both that the stated condition on G is sufficient and that every other G fails the goodness property for some sequence of α_i; without the full proof of exhaustiveness (presumably in the main theorem section), the characterization cannot be verified.
minor comments (2)
  1. [Introduction] The definition of snd(α) (smallest positive integer that does not divide α) should be stated explicitly in the introduction or notation section rather than only in the abstract.
  2. [Introduction] The precise statement of the 1983 Burr et al. theorem being extended should be recalled verbatim (including the exact form of G) so that the new result can be compared directly.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for highlighting the need for a complete verification of the characterization. We address the major comment below.

read point-by-point responses

  1. Referee: [Main theorem / proof of characterization] The central claim asserts that the property of being G-good for large n is completely determined by the values snd(α_i). The manuscript must therefore contain an exhaustive case analysis showing both that the stated condition on G is sufficient and that every other G fails the goodness property for some sequence of α_i; without the full proof of exhaustiveness (presumably in the main theorem section), the characterization cannot be verified.

    Authors: Theorem 1.1 states the full characterization in terms of snd(α_i). Its proof (Section 3) proceeds in two directions. Sufficiency is established in 3.1–3.2 by an explicit upper-bound construction: when G satisfies the arithmetic condition relative to each snd(α_i), a critical (χ(G)−1)-coloring of G combined with the definition of snd controls the size of the largest color class, yielding r(G,K_{α_1,…,α_p,n}) ≤ (χ(G)−1)(n−1)+s(G) for all sufficiently large n. Necessity is handled in 3.3 by a case analysis on the possible values of snd(α_i). For any G that violates the stated condition for at least one i, we select a sequence α_1,…,α_p in which that snd(α_i) produces a divisibility obstruction; standard Ramsey lower-bound constructions (blow-ups of critical graphs or random graphs with appropriate girth) then show that r(G,K_{α_1,…,α_p,n}) strictly exceeds the formula for infinitely many n. Because every positive integer possesses a unique smallest non-divisor, the cases partition all possibilities and are therefore exhaustive. revision: no

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper extends the 1983 Burr et al. result by providing a characterization of those graphs G for which the complete multipartite graphs K_{α1,…,αp,n} are G-good when n is large. This characterization is expressed using the parameter snd(αi), defined directly as the smallest non-divisor of each input part size αi. No steps reduce by construction to fitted inputs, self-definitions, or load-bearing self-citations; the dependence on snd(αi) arises naturally from divisibility considerations in equitable colorings and Ramsey constructions rather than from redefining the target property. The derivation is self-contained against the external 1983 benchmark and does not invoke any uniqueness theorems or ansatzes from the authors' prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions from graph theory and Ramsey theory; the key new parameter snd is a standard number-theoretic notion applied to the part sizes. No free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of chromatic number chi(G), Ramsey number r(G,H), and the minimum color-class size s(G) in a proper chi(G)-coloring.
    These are invoked in the definition of G-good and in the target formula for r(G,H).

pith-pipeline@v0.9.1-grok · 5724 in / 1341 out tokens · 43079 ms · 2026-06-29T17:18:34.690631+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. A Resolution of Erd\H{o}s Problem 550 on Tree versus Complete Multipartite Ramsey Numbers

    math.CO 2026-06 unverdicted novelty 9.0

    Proves R(T, K_{m1,...,mk}) ≤ (k-1)(R(T, K_{m1,m2})-1) + m1 for large n-vertex trees T and fixed k, m_i.

Reference graph

Works this paper leans on

22 extracted references · cited by 1 Pith paper

  1. [1]

    Bollob´ as and P

    B. Bollob´ as and P. Erd˝ os, On the structure of edge graphs, Bull. Lond. Math. Soc. 5 (1973) 317-321

    1973

  2. [2]

    Burr, Ramsey numbers involving graphs with long suspended paths, J

    S. Burr, Ramsey numbers involving graphs with long suspended paths, J. Lond. Math. Soc. 2 (1981) 405-413

    1981

  3. [3]

    S. Burr, R. Faudree, C. Rousseau and R. Schelp, On Ramsey numbers involving starlike multipartite graphs, J. Graph Theory 7 (1983) 395-409

    1983

  4. [4]

    Burr and P

    S. Burr and P. Erd˝ os, Generalizations of a Ramsey-theoretic result of Chv´ atal, J. Graph Theory 7 (1983) 39-51

    1983

  5. [5]

    Campos, S

    M. Campos, S. Griffiths, R. Morris and J. Sahasrabudhe, An exponential improvement for diagonal Ramsey, Ann. Math. To appear

  6. [6]

    Chv´ atal, Tree-complete graph Ramsey numbers, J

    V. Chv´ atal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977) 93

    1977

  7. [7]

    Conlon, J

    D. Conlon, J. Fox and B. Sudakov, Recent Developments in Graph Ramsey Theory, Surveys in Combinatorics 2015, London Math. Soc. Lecture Note Ser., vol. 424, Cambridge Univ. Press, Cambridge, 2015, pp. 49-118

    2015

  8. [8]

    Erd˝ os, On the number of complete subgraphs contained in certain graphs, Magyar Tud

    P. Erd˝ os, On the number of complete subgraphs contained in certain graphs, Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl. 7 (1962) 459-464

    1962

  9. [9]

    Erd˝ os, Some recent results on extremal problems in graph theory, Theory of Graphs, Internat

    P. Erd˝ os, Some recent results on extremal problems in graph theory, Theory of Graphs, Internat. Sympos. in Rome, Gordon and Breach, New York (1966) 117-130

    1966

  10. [10]

    Erd˝ os, On some new inequalities concerning extremal properties of graphs, Theory of Graph (P

    P. Erd˝ os, On some new inequalities concerning extremal properties of graphs, Theory of Graph (P. Erd˝ os and G. Katona, eds.), Proc. Colloy, Tihany, vol. 1966, Academic Press, New York (1968) 77-81

    1966

  11. [11]

    Erd˝ os and M

    P. Erd˝ os and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966) 51-57

    1966

  12. [12]

    Erd˝ os and A

    P. Erd˝ os and A. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 5 (1946) 1087-1091. 13

    1946

  13. [13]

    J. Fox, X. He and Y. Wigderson, Ramsey goodness of books revisited, Adv. Comb. 4 (2023) 21 pp

    2023

  14. [14]

    Koml´ os and M

    J. Koml´ os and M. Simonovits, Szemer´ edi’s regularity lemma and its applications in graph theory, Combinatorics, Paul Erd˝ os is Eighty (Keszthely, 1993), vol. 2, Bolyai Soc. Math. Stud. J´ anos Bolyai Math. Soc., Budapest (1996) 295-352

    1993

  15. [15]

    Koml´ os, G

    J. Koml´ os, G. S´ ark¨ ozy and E. Szemer´ edi, Blow-up lemma, Combinatorica 17 (1997) 109- 123

    1997

  16. [16]

    Li and C

    Y. Li and C. Rousseau, Fan-complete graph Ramsey numbers, J. Graph Theory 23 (1996) 413-420

    1996

  17. [17]

    Li and C

    Y. Li and C. Rousseau, On book-complete graph Ramsey numbers, J. Combin. Theory Ser. B. 68 (1996) 36-44

    1996

  18. [18]

    Y. Li, C. Rousseau and W. Zang, Asymptotic upper bounds for Ramsey functions, Graphs Combin. 17 (2001) 123-128

    2001

  19. [19]

    Liu and Y

    M. Liu and Y. Li, On graphs for which large books are Ramsey good, J. Graph Theory 108 (2025) 543-559

    2025

  20. [20]

    Nikiforov and C

    V. Nikiforov and C. Rousseau, Large generalized books arep-good, J. Combin. Theory Ser. B 92 (2004) 85-97

    2004

  21. [21]

    Simonovits, A method for solving extremal problems in graph theory, Theory of Graphs (P

    M. Simonovits, A method for solving extremal problems in graph theory, Theory of Graphs (P. Erd˝ os and G. Katona, eds.), Proc. Colloy, Tihany, 1966, Academic Press, New York (1968) 279-319

    1966

  22. [22]

    Szemer´ edi, Regular partitions of graphs, Probl´ emes combinatories et th´ eorie des graphs (J

    E. Szemer´ edi, Regular partitions of graphs, Probl´ emes combinatories et th´ eorie des graphs (J. C. Bermond, J. C. Fournier, M. LasVergnas, and D. Scotteau, eds.) (Orsay 1976), Colloq. Internat. CNRS 260, Paris (1978) 399-401. 14

    1976