pith. sign in

arxiv: 2605.26815 · v2 · pith:KLXYV7AJnew · submitted 2026-05-26 · 🧮 math.CO · cs.DM· math.NT

Prime Certificates for Exact Vertex-Coprime Ramsey Numbers

Zhicheng Du , Wenji Xi , Zhuo Deng , Lan Ma This is my paper

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

classification 🧮 math.CO cs.DMmath.NT
keywords coprime Ramsey numbersvertex-coloringprime certificatescoprime graphsRamsey theoryexact formulasprime partitions
0
0 comments X

The pith

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).

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

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.

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}.

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.

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.

Where Pith is reading between the lines

These are 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.

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.

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.

Figures

Figures reproduced from arXiv: 2605.26815 by Lan Ma, Wenji Xi, Zhicheng Du, Zhuo Deng.

Figure 1
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. 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. 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 ↗
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] view at source ↗
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 More Detail Balanced coloring was the most useful side branch after the main theorem. It tests whether the exact threshold is merely exploi… view at source ↗
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 MILP treats every coprime clique explicitly. A more structural search stays inside the proof certificate. At n = p2k−2 − 1, there are 2k − 3 … view at source ↗
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] view at source ↗
Figure 8
Figure 8. Figure 8: For the deterministic splits that succeeded for [PITH_FULL_IMAGE:figures/full_fig_p034_8.png] view at source ↗
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] view at source ↗
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] view at source ↗
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] view at source ↗
read the original 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.

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

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 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.

axioms (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.

pith-pipeline@v0.9.1-grok · 5819 in / 1422 out tokens · 78036 ms · 2026-06-29T17:23:08.174014+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

37 extracted references · 23 canonical work pages · 7 internal anchors

  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

  9. [9]

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

  10. [10]

    arXiv:2409.15709

    doi:10.1002/jgt.70029. arXiv:2409.15709

    work page doi:10.1002/jgt.70029

  11. [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

    work page doi:10.4007/annals.2026.203.3.4 2026

  12. [12]

    Campos, M

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

    work page arXiv 2025

  13. [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

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/s00222-026-01421-9 2026

  14. [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

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  15. [15]

    An update on multicolor Ramsey lower bounds

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

    work page arXiv 2026

  16. [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

    work page arXiv 2026

  17. [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

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  18. [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

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  19. [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

    work page doi:10.1142/s179355712550069x 2026

  20. [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

    work page arXiv 2026

  21. [21]

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

    work page arXiv 2025

  22. [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

  23. [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

  24. [24]

    Chromatic number of coprime graph

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

  25. [25]

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

    work page arXiv

  26. [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

    work page doi:10.37236/1323 1997

  27. [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

    work page doi:10.5281/zenodo.10987344 2022

  28. [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

    work page doi:10.1016/j.disc.2025.114974 2026

  29. [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

    work page doi:10.47443/dml.2024.045 2024

  30. [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

  31. [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

    work page doi:10.1090/s0002-9947-1973-0327710-7 1973

  32. [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

    work page doi:10.4064/aa-66-1-89-99 1994

  33. [33]

    On Sequences Containing at Most 4 Pairwise Coprime Integers

    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

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1016/j.disc.2012.11.008 2013

  34. [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,

  35. [35]

    On a conjecture of Erd\H{o}s about sets without $k$ pairwise coprime integers

    doi:10.1137/17m1130630. arXiv:1705.05730

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1137/17m1130630

  36. [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

  37. [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

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/s11139-016-9839- 2010