Pith. sign in

REVIEW 2 minor 37 references

Prime Certificates for Exact Vertex-Coprime Ramsey Numbers

T0 review · 0 major / 2 minor · reviewed 2026-06-29 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The mixed vertex-coloring coprime Ramsey number R_cop(k_1,…,k_c) equals the prime whose index is the sum of (k_i-1).

desk verdict The paper delivers an exact closed-form for the vertex-coprime Ramsey number as the right prime, with matching elementary bounds that check out on the given sketch. read the letter →

arxiv 2605.26815 v2 pith:KLXYV7AJ submitted 2026-05-26 math.CO cs.DMmath.NT

Zhicheng Du , Wenji Xi , Zhuo Deng , Lan Ma This is my paper · ORCID
classification math.COcs.DMmath.NT
keywords coprimeRamseynumbersvertex-coloringprimecertificatesgraphstheoryexactformulaspartitions
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper establishes an exact closed-form expression for the mixed vertex-coloring coprime Ramsey numbers on the coprime graph G_n. It shows these numbers equal the prime at position equal to the sum over i of (k_i minus one). A sympathetic reader would care because the result replaces the usual search for Ramsey thresholds with a direct reference to the sequence of primes. The upper bound follows from the pigeonhole principle applied to a large clique, while the lower bound follows from a partition that routes each composite number into one of its prime factors.

What carries the argument

The clique formed by 1 together with all primes up to n in the coprime graph G_n, which supplies the pigeonhole upper bound, together with the prime-bin partition that supplies the matching lower bound.

What would settle it

An explicit c-coloring of the coprime graph on the integers from 1 to p_m minus 1, where m equals the sum of (k_i minus 1), that avoids a monochromatic coprime clique of size k_i in color i for each i.

Watch

Extended reading notes

Core claim

We prove that the mixed vertex-coloring coprime Ramsey number satisfies R_cop(k_1,…,k_c)=p_{∑_{i=1}^c(k_i-1)}, where p_m is the m-th prime. The proof is elementary: the prime clique {1}∪{p≤n:p prime} gives the upper bound by pigeonhole, while a prime-bin partition gives the matching lower bound by coloring each composite with a bin containing one of its prime divisors. The same certificate viewpoint yields an exact reduction of the edge-coloring variant to classical Ramsey numbers: R_edge(k_1,…,k_c)=p_{R_cl(k_1,…,k_c)-1}.

Load-bearing premise

The set consisting of 1 together with the primes up to the relevant prime forms a clique in the coprime graph G_n.

Editorial extensions

If this is right

  • The edge-coloring parameter satisfies the exact reduction R_edge(k_1,…,k_c)=p_{R_cl(k_1,…,k_c)-1}.
  • The balanced two-color diagonal threshold equals the unrestricted threshold p_{2k-2} for every k at least 2.
  • For any fixed number of colors c, multicolor balanced certificates exist for all sufficiently large parameters via a Hall argument combined with the Selberg-Delange estimate.
  • A polynomial-time primitive exists for extracting the certificates from the same clique-label construction.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The formula directly ties the growth of these Ramsey numbers to the distribution of primes.
  • The certificate method may transfer to other Ramsey parameters defined on graphs whose edges or vertices are governed by divisibility or coprimality conditions.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that the mixed vertex-coloring coprime Ramsey number satisfies R_cop(k_1,…,k_c)=p_{∑(k_i−1)}, where p_m is the m-th prime. The upper bound follows from the clique {1}∪{primes ≤ n} in the coprime graph G_n together with the pigeonhole principle on color classes; the matching lower bound is obtained from a prime-bin partition in which each composite is colored according to one of its prime factors. The same certificate framework yields an exact reduction Redge(k_1,…,k_c)=p_{R_cl(k_1,…,k_c)−1} for the edge-coloring variant, a support-disjointness generalization, and exact balanced two-color thresholds p_{2k−2} for all k≥2 via a deterministic prime-bin split that uses only the inequality 2p_m < p_{2m} < 3p_m.

Significance. If the derivations hold, the result supplies a closed-form expression for an entire family of Ramsey-type numbers on the coprime graph, a rare occurrence in Ramsey theory. The elementary certificate construction, the direct reduction of the edge-coloring parameter to classical Ramsey numbers, and the provision of polynomial-time certificate extraction constitute concrete strengths that would be noted in any assessment of the work.

minor comments (2)
  1. The abstract states that the balanced two-color result holds for all k≥2 via the inequality 2p_m < p_{2m} < 3p_m; a short explicit verification of this inequality (or a reference to a standard bound) would make the deterministic split fully self-contained.
  2. Notation: the symbols Rcop and Redge are introduced in the abstract but the manuscript should confirm that they are used consistently in all subsequent statements of the main theorems.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript and the recommendation to accept.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The paper's central claim is established by an elementary direct argument: the set {1} union primes forms a clique in G_n by the definition of coprimality, so the pigeonhole principle on color classes immediately yields the upper bound R_cop(k1,...,kc) <= p_{sum(ki-1)}; the matching lower bound follows from an explicit prime-bin coloring in which each composite is assigned to a bin sharing one of its prime factors, ensuring each color class has no ki pairwise-coprime vertices. Neither bound reduces to a fitted parameter, a self-citation chain, or an imported ansatz; the argument is self-contained against the standard definitions of the coprime graph and Ramsey numbers, with no load-bearing reliance on prior work by the authors.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The central claim rests on standard mathematical facts about primes and the pigeonhole principle. No free parameters are fitted, and no new entities are introduced.

assumptions (2)
  • standard math Pigeonhole principle
    Invoked to obtain the upper bound from the size of the prime clique.
  • standard math Every composite integer greater than 1 has at least one prime divisor
    Used to construct the prime-bin coloring for the lower bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Prime Certificates for Exact Vertex-Coprime Ramsey Numbers." pith.science (2026). https://pith.science/paper/KLXYV7AJ

@misc{pith2026260526815,
  author       = {Pith},
  title        = {Pith review of: Prime Certificates for Exact Vertex-Coprime Ramsey Numbers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KLXYV7AJ}},
  note         = {Machine review of arXiv:2605.26815}
}
abstract

Let $G_n$ be the coprime graph on $\{1,\ldots,n\}$. We prove that the mixed vertex-coloring coprime Ramsey number satisfies \[ \Rcop(k_1,\ldots,k_c)=p_{\sum_{i=1}^c(k_i-1)}, \] where $p_m$ is the $m$-th prime. The proof is elementary: the prime clique $\{1\}\cup\{p\le n:p\text{ prime}\}$ gives the upper bound by pigeonhole, while a prime-bin partition gives the matching lower bound by coloring each composite with a bin containing one of its prime divisors. We reserve $\Rcop$ for this vertex-coloring parameter; the edge-coloring parameter on the same host graph is denoted $\Redge$. The same certificate viewpoint yields several extensions, including a support-disjointness generalization, a polynomial-time certificate-extraction primitive, and an exact reduction of the edge-coloring variant to classical Ramsey numbers: $\Redge(k_1,\ldots,k_c)=p_{\Rcl(k_1,\ldots,k_c)-1}$. These two formulas are rank transfers from the same clique-label certificate. We also prove that the balanced two-color diagonal threshold equals the unrestricted threshold $p_{2k-2}$ for all $k\ge2$, via a deterministic prime-bin split requiring only the weak inequality $2p_m<p_{2m}<3p_m$; for fixed $c$, a Hall argument plus a standard Selberg--Delange estimate gives eventual multicolor balanced certificates.

Figures

Figures reproduced from arXiv: 2605.26815 by the authors.

Figure 1
Figure 1. The central story of the paper. A direct Ramsey encoding produces a large search [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Ratio plot for Rcop(k; 2) = p2k−2 against the baseline 2k log k. The second-order prime￾number-theorem term explains the visible gap beyond the first-order scale. 12 [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Shifted intervals produce a small but genuine dependence on local arithmetic structure. [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Supplementary visualization of the off-diagonal formula: the values form prime-index [PITH_FULL_IMAGE:figures/full_fig_p026_4.png]
Figure 5
Figure 5. Figure 5: One extremal prime-bin coloring at k = 10, n = 60. Blue and orange squares are the two color classes in a canonical prime-bin witness. The visible imbalance is diagnostic only; the exact balanced theorem is proved independently in Theorem 6.2. B.2 Balanced Colorings in…
Figure 6
Figure 6. Figure 6: For k = 3, . . . , 9, near-balanced two-colorings exist up to the same last feasible n as unrestricted colorings. The two sequences coincide; the markers and line styles are chosen so both computed thresholds remain visible. B.2.2 Constructive prime-bin witnesses The M…
Figure 7
Figure 7. Figure 7: For k = 3, . . . , 16, the reachable color-0 interval inside one prime-bin split contains the balanced target at n = Rcop(k; 2) − 1. Blue segments show the reachable intervals and red markers show the balanced targets [PITH_FULL_IMAGE:figures/full_fig_p033_7.png]
Figure 8
Figure 8. Figure 8: For the deterministic splits that succeeded for [PITH_FULL_IMAGE:figures/full_fig_p034_8.png]
Figure 9
Figure 9. Figure 9: For the proved skip-2 split, the color-0 forced side has the exact formula [PITH_FULL_IMAGE:figures/full_fig_p034_9.png]
Figure 10
Figure 10. Figure 10: For the start-0 round-robin certificate strategy in each color count, the forced-side ratio [PITH_FULL_IMAGE:figures/full_fig_p035_10.png]
Figure 11
Figure 11. Figure 11: Clique and clause counts grow rapidly, but the exact upper-bound certificate is the single [PITH_FULL_IMAGE:figures/full_fig_p038_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 23 canonical work pages

  1. [1]

    F. P. Ramsey. On a problem of formal logic.Proceedings of the London Mathematical Society, 30:264–286, 1930

    1930

  2. [2]

    A combinatorial problem in geometry.Compositio Mathematica, 2:463–470, 1935

    Paul Erd˝ os and George Szekeres. A combinatorial problem in geometry.Compositio Mathematica, 2:463–470, 1935

    1935

  3. [3]

    Some remarks on the theory of graphs.Bulletin of the American Mathematical Society, 53:292–294, 1947

    Paul Erd˝ os. Some remarks on the theory of graphs.Bulletin of the American Mathematical Society, 53:292–294, 1947

    1947

  4. [4]

    R. E. Greenwood and A. M. Gleason. Combinatorial relations and chromatic graphs.Canadian Journal of Mathematics, 7:1–7, 1955

    1955

  5. [5]

    A note on Ramsey numbers.Journal of Combinatorial Theory, Series A, 29(3):354–360, 1980

    Mikl´ os Ajtai, J´ anos Koml´ os, and Endre Szemer´ edi. A note on Ramsey numbers.Journal of Combinatorial Theory, Series A, 29(3):354–360, 1980

    1980

  6. [6]

    The Ramsey number R(3, t) has order of magnitude t2/logt .Random Structures & Algorithms, 7(3):173–207, 1995

    Jeong Han Kim. The Ramsey number R(3, t) has order of magnitude t2/logt .Random Structures & Algorithms, 7(3):173–207, 1995

    1995

  7. [7]

    Burr, Paul Erd˝ os, and L´ aszl´ o Lov´ asz

    Stefan A. Burr, Paul Erd˝ os, and L´ aszl´ o Lov´ asz. On graphs of Ramsey type.Ars Combinatoria, 1:167–190, 1976

    1976

  8. [8]

    Radziszowski

    Stanis law P. Radziszowski. Small Ramsey numbers.Electronic Journal of Combinatorics, Dynamic Surveys DS1, revision 18, April 24, 2026. doi:10.37236/21

    work page doi:10.37236/21 2026

Show all 37 references
  1. [9]

    Vigleik Angeltveit and Brendan D. McKay. R(5, 5) ≤ 46.Journal of Graph Theory, online

  2. [10]

    arXiv:2409.15709

    doi:10.1002/jgt.70029. arXiv:2409.15709

    doi

  3. [11]

    An expo- nential improvement for diagonal Ramsey.Annals of Mathematics, 203(3):869–932, 2026

    Marcelo Campos, Simon Griffiths, Robert Morris, and Julian Sahasrabudhe. An expo- nential improvement for diagonal Ramsey.Annals of Mathematics, 203(3):869–932, 2026. doi:10.4007/annals.2026.203.3.4. arXiv:2303.09521

    2026 doi

  4. [12]

    A new lower bound for the Ramsey numbersR(3, k)

    Marcelo Campos, Matthew Jenssen, Marcus Michelen, and Julian Sahasrabudhe. A new lower bound for the Ramsey numbersR(3, k). arXiv:2505.13371, 2025

    2025

  5. [13]

    An exponential improvement for Ramsey lower bounds

    Jie Ma, Wujie Shen, and Shengjie Xie. An exponential improvement for Ramsey lower bounds. Inventiones Mathematicae, online 2026. doi:10.1007/s00222-026-01421-9. arXiv:2507.12926

    2026 doi arXiv

  6. [14]

    Gaussian random graphs and Ramsey numbers

    Zach Hunter, Aleksa Milojevi´ c, and Benny Sudakov. Gaussian random graphs and Ramsey numbers. arXiv:2512.17718, revised May 2026

    2026 arXiv

  7. [15]

    An update on multicolor Ramsey lower bounds

    Marcelo Campos and Cosmin Pohoata. An update on multicolor Ramsey lower bounds. arXiv:2601.15183, 2026

    2026

  8. [16]

    A note on multicolour Ramsey numbers and random sphere graphs

    Yamaan Attwa, Albert L´ opez Vidal, and Patrick Morris. A note on multicolour Ramsey numbers and random sphere graphs. arXiv:2602.02155, 2026

    2026

  9. [17]

    Reinforced generation of combinatorial structures: Ramsey numbers

    Ansh Nagda, Prabhakar Raghavan, and Abhradeep Thakurta. Reinforced generation of combinatorial structures: Ramsey numbers. arXiv:2603.09172, revised April 2026

    2026 arXiv

  10. [18]

    Benjamin Przybocki, John Mackey, Marijn J. H. Heule, and Bernardo Subercaseaux. Dou- bly saturated Ramsey graphs: A case study in computer-assisted mathematical discovery. arXiv:2604.21187, 2026. 41

    2026 arXiv

  11. [19]

    On structural properties and adjacency spectrum of coprime graph of integers.Asian-European Journal of Mathematics, 19(1):2550069, 2026

    Subarsha Banerjee. On structural properties and adjacency spectrum of coprime graph of integers.Asian-European Journal of Mathematics, 19(1):2550069, 2026. doi:10.1142/s179355712550069x. arXiv:2506.10583

    2026 doi

  12. [20]

    On finite groups whose coprime graph is a divisor graph

    Xuanlong Ma, Liangliang Zhai, Nan Gao, and Junyao Pan. On finite groups whose coprime graph is a divisor graph. arXiv:2501.14339, revised February 2026

    2026

  13. [21]

    Ravi Ranjan and Shubh N. Singh. On prime coprime graphs of certain finite groups. arXiv:2507.15993, 2025

    2025

  14. [22]

    What Happens When You Let an AI Loose on 1,000 Erd˝ os Problems

    Alex Towell. What Happens When You Let an AI Loose on 1,000 Erd˝ os Problems. Blog post, updated April 26, 2026. https://metafunctor.com/post/2026-03-16-computational-exp lorations/

    2026

  15. [23]

    Computational explorations in number theory, combinatorics, and beyond

    Alex Towell. Computational explorations in number theory, combinatorics, and beyond. GitHub repository, 2026.https://github.com/queelius/computational-explorations

    2026

  16. [24]

    Chromatic number of coprime graph

    Misha Lavrov. Answer to “Chromatic number of coprime graph”. Mathematics Stack Exchange,

  17. [25]

    https://math.stackexchange.com/questions/3603536/chromatic-number-of-cop rime-graph/3603563

  18. [26]

    S´ ark¨ ozy

    Paul Erd˝ os and Gabor N. S´ ark¨ ozy. On cycles in the coprime graph of integers.Electronic Journal of Combinatorics, 4(2):R8, 1997. doi:10.37236/1323

    1997 doi

  19. [27]

    Subgraphs of coprime graphs on sets of consecutive integers.Integers, 22:A47, 2022

    Ethan Berkove and Michael Brilleslyper. Subgraphs of coprime graphs on sets of consecutive integers.Integers, 22:A47, 2022. doi:10.5281/zenodo.10987344

    2022 doi

  20. [28]

    Batta and L

    G. Batta and L. Hajdu. Minimal common factor graphs containing all graphs of order k. Discrete Mathematics, 349(5):114974, 2026. doi:10.1016/j.disc.2025.114974

    2026 doi

  21. [29]

    Coprime divisors graphs and their col- oring parameters.Discrete Mathematics Letters, 13:128–134, 2024

    Mohamed Jorf, Brahim Boudine, and Lahcen Oukhtite. Coprime divisors graphs and their col- oring parameters.Discrete Mathematics Letters, 13:128–134, 2024. doi:10.47443/dml.2024.045

    2024 doi

  22. [30]

    Remarks in number theory IV

    Paul Erd˝ os. Remarks in number theory IV. Extremal problems in number theory I.Matematikai Lapok, 13:228–255, 1962

    1962

  23. [31]

    S. L. G. Choi. On sequences containing at most 3 pairwise coprime integers.Transactions of the American Mathematical Society, 183:437–440, 1973. doi:10.1090/s0002-9947-1973-0327710-7

    1973 doi

  24. [32]

    Khachatrian

    Rudolf Ahlswede and Levon H. Khachatrian. On extremal sets without coprimes.Acta Arithmetica, 66(1):89–99, 1994. doi:10.4064/aa-66-1-89-99

    1994 doi

  25. [33]

    On sequences containing at most 4 pairwise coprime inte- gers.Discrete Mathematics, 313:357–365, 2013

    Yong-Gao Chen and Xiao-Feng Zhou. On sequences containing at most 4 pairwise coprime inte- gers.Discrete Mathematics, 313:357–365, 2013. doi:10.1016/j.disc.2012.11.008. arXiv:1101.0050

    2013 doi arXiv

  26. [34]

    Kiss, Csaba S´ andor, and Quan-Hui Yang

    S´ andor Z. Kiss, Csaba S´ andor, and Quan-Hui Yang. On a conjecture of Erd˝ os about sets without k pairwise coprime integers.SIAM Journal on Discrete Mathematics, 32(4):2453–2466,

  27. [35]

    arXiv:1705.05730

    doi:10.1137/17m1130630. arXiv:1705.05730

    doi arXiv

  28. [36]

    Third edition, Graduate Studies in Mathematics 163, American Mathematical Society, 2015

    G´ erald Tenenbaum.Introduction to Analytic and Probabilistic Number Theory. Third edition, Graduate Studies in Mathematics 163, American Mathematical Society, 2015

    2015

  29. [37]

    Estimates of some functions over primes without R.H

    Pierre Dusart. Estimates of some functions over primes without R.H. arXiv:1002.0442, 2010. Published version:The Ramanujan Journal, 45(1):227–251, 2018, doi:10.1007/s11139-016-9839- 4. 42

    2010 doi arXiv

Pith tools

Reviewed June 29, 2026 · model on record in the stance chip above.