Recognition: 2 theorem links
· Lean TheoremA linear upper bound for zero-sum Ramsey numbers of bounded degree graphs
Pith reviewed 2026-05-16 20:40 UTC · model grok-4.3
The pith
Bounded-degree graphs have zero-sum Ramsey numbers at most linear in their vertex count.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that R(G, Γ) ≤ C n for every n-vertex graph G of bounded maximum degree and every finite abelian group Γ such that |Γ| divides the number of edges of G, where the constant C depends only on the degree bound and on Γ.
What carries the argument
The zero-sum Ramsey number R(G, Γ), the smallest t such that every Γ-edge-coloring of K_t contains a copy of G whose colors sum to zero.
If this is right
- The critical complete graph size needed to force a zero-sum copy of G stays proportional to the size of G itself.
- The same linear bound applies simultaneously to every group Γ whose order divides e(G).
- The result covers all bounded-degree graphs at once rather than only special families such as cycles or trees.
- If the degree bound is removed, the linear guarantee no longer follows from the argument.
Where Pith is reading between the lines
- The bound suggests that sparseness (via bounded degree) is the main feature allowing the Ramsey number to remain linear under the zero-sum condition.
- For groups whose order does not divide e(G) the linear statement is not claimed, leaving open whether a slightly weaker bound still holds.
- The argument may adapt to hypergraphs or to directed graphs with analogous sum conditions.
Load-bearing premise
The maximum degree of G is bounded by a constant independent of n and the order of Γ divides the number of edges in G.
What would settle it
An explicit bounded-degree n-vertex graph G together with a group Γ whose order divides e(G) and a Γ-coloring of K_{c n-1} (for arbitrarily large c) containing no zero-sum copy of G would show the linear bound fails.
Figures
read the original abstract
Let $G$ be a graph and $\Gamma$ a finite abelian group. The zero-sum Ramsey number of $G$ over $\Gamma$, denoted by $R(G, \Gamma)$, is the smallest positive integer $t$ (if it exists) such that any edge-colouring $c:E(K_t)\to\Gamma$ contains a copy of $G$ with $\sum_{e\in E(G)}c(e)=0_\Gamma$. We prove a linear upper bound $R(G, \Gamma)\leq Cn$ that holds for every $n$-vertex graph $G$ with bounded maximum degree and every finite abelian group $\Gamma$ with $|\Gamma|$ dividing $e(G)$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper defines the zero-sum Ramsey number R(G, Γ) as the smallest t such that every edge-coloring of K_t with colors from a finite abelian group Γ contains a copy of G whose edge colors sum to the zero element of Γ. It proves that when G is an n-vertex graph with maximum degree bounded by a constant Δ independent of n, and |Γ| divides the number of edges of G, then R(G, Γ) ≤ C n for a constant C depending only on Δ and |Γ|. The argument reduces the problem to the Erdős–Ginzburg–Ziv theorem and uses a bounded-degree embedding lemma followed by probabilistic deletion to produce a positive-density zero-sum copy.
Significance. If the claimed linear bound holds, the result supplies a strong, linear upper bound for zero-sum Ramsey numbers in the bounded-degree setting, where general Ramsey numbers are typically much larger. The proof is notable for its explicit dependence of C only on Δ and |Γ|, its direct appeal to the EGZ theorem to guarantee zero-sum subsets, and the use of a probabilistic deletion step that controls overlaps via the degree bound; these features make the argument self-contained and potentially adaptable to related zero-sum embedding problems.
minor comments (2)
- The abstract states the bound R(G, Γ) ≤ C n but does not indicate whether C is effective or merely existential; adding a brief sentence on the dependence of C would clarify the result for readers.
- In the embedding argument (presumably §3 or §4), the probabilistic deletion step is described as yielding a positive-density surviving copy; a short calculation showing the survival probability is bounded away from zero in terms of Δ alone would make the constant dependence fully explicit.
Simulated Author's Rebuttal
We thank the referee for their careful reading of the manuscript and for the positive assessment. We are pleased that the referee recognizes the strength of the linear bound and the self-contained nature of the argument via the EGZ theorem and probabilistic deletion.
Circularity Check
No significant circularity detected
full rationale
The paper derives the linear upper bound R(G, Γ) ≤ C n directly from the Erdős–Ginzburg–Ziv theorem combined with a bounded-degree graph embedding argument and probabilistic deletion. The constants C depend only on the fixed maximum degree Δ and group order |Γ|, with the divisibility hypothesis |Γ| | e(G) used explicitly to guarantee zero-sum subsets. No load-bearing step reduces the claimed inequality to a fitted parameter, self-citation chain, or definitional equivalence; the proof is self-contained against standard external combinatorial results.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Finite abelian groups admit zero-sum subsets when the order divides the total sum (standard Cauchy-Davenport or Erdős–Ginzburg–Ziv type facts).
- domain assumption Bounded-degree graphs admit linear-size Ramsey-type embeddings under edge-colorings (standard in sparse Ramsey theory).
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We prove a linear upper bound R(G, Γ) ≤ C n that holds for every n-vertex graph G with bounded maximum degree and every finite abelian group Γ with |Γ| dividing e(G).
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.
Forward citations
Cited by 1 Pith paper
-
A linear upper bound on zero-sum Ramsey numbers of $d$-degenerate graphs in $\mathbb{Z}_p$
For d-degenerate graphs satisfying m ≥ 2pd(d+1)^2, p|m and 2d<p, the zero-sum Ramsey number R(G, Z_p) is at most n + (3+3d)p.
Reference graph
Works this paper leans on
-
[1]
N. Alon and Y. Caro. On three zero-sum Ramsey-type problems.Journal of Graph Theory,17:177–192, 1993
work page 1993
-
[2]
J. Alvarado, L. Colucci, R. Parente, and V. Souza. On the zero-sum Ramsey problem overZd
-
[3]
InLatin 2022: Theoretical Informatics, volume 13568 ofLecture Notes in Computer Science, pages 445–459. Springer, 2022
work page 2022
- [4]
- [5]
-
[6]
A. Bialostocki and P. Dierker. On the Erdős-Ginzburg-Ziv theorem and the Ramsey numbers for stars and matchings.Discrete Mathematics,110:1–8, 1992
work page 1992
-
[7]
R. Campbell, J. P. Gollin, K. Hendrey, and R. Steiner. Optimal bounds for zero-sum cycles. I. Odd order.Journal of Combinatorial Theory, Series B,173:246–256, 2025
work page 2025
- [8]
- [9]
-
[10]
Y. Caro. On zero-sum Ramsey numbers – stars.Discrete Mathematics,104:1–6, 1992
work page 1992
-
[11]
Y. Caro. A complete characterization of the zero-sum (mod 2) Ramsey numbers.Journal of Combina- torial Theory, Series A,68:205–211, 1994
work page 1994
-
[12]
Y. Caro. Zero-sum problems — A survey.Discrete Mathematics,152(1):93–113, 1996
work page 1996
-
[13]
M. Christoph, C. Knierim, A. Martinsson, and R. Steiner. Improved bounds for zero-sum cycles inZd p. Journal of Combinatorial Theory, Series B,173:365–373, 2025
work page 2025
-
[14]
V. Chvátal, V. Rödl, E. Szemerédi, and W. T. Trotter Jr. The Ramsey number of a graph with bounded maximum degree.Journal of Combinatorial Theory, Series B,34:239–243, 1986. 29
work page 1986
-
[15]
L. Colucci and M. D’Emidio. A linear upper bound on the zero-sum Ramsey number of forests inZp. arXiv:2512.06229, 2025
- [16]
- [17]
-
[18]
Cambridge Univ. Press
-
[19]
D. S. Dummit and R. M. Foote.Abstract algebra, volume 3. Wiley Hoboken, 2004
work page 2004
-
[20]
P. Erdős. Some remarks on the theory of graphs.Bulletin of the American Mathematical Society, 53:292–294, 1947
work page 1947
- [21]
-
[22]
P. Erdős and G. Szekeres. A combinatorial problem in geometry.Compositio Mathematica,2:463–470, 1935
work page 1935
-
[23]
R. L. Graham, B. L. Rothschild, and J. H. Spencer.Ramsey theory, Vol. 20. John Wiley & Sons, 1991
work page 1991
- [24]
-
[25]
L. Halbeisen, M. Hamilton, and P. Růžička. Minimal generating sets of groups, rings, and fields. Quaestiones Mathematicae,30(3):355–363, 2007
work page 2007
- [26]
-
[27]
M. Kneser. Abschätzungen der asymptotischen dichte von summenmengen.Mathematische Zeitschrift, 58(1):459–484, 1953
work page 1953
-
[28]
C. Lee. Ramsey numbers of degenerate graphs.Annals of Mathematics,185:791–829, 2017
work page 2017
-
[29]
J. Ma, W. Shen, and S. Xie. An exponential improvement for Ramsey lower bounds.arXiv:2507.12926, 2025
work page internal anchor Pith review Pith/arXiv arXiv 2025
-
[30]
S. Mattheus and J. Verstraete. The asymptotics ofr(4, t).Annals of Mathematics,199:919–941, 2024
work page 2024
-
[31]
F. P. Ramsey. On a problem of formal logic.Proceedings of the London Mathematical Society,30:264– 286, 1930. A Proof of Lemma 9.3 The proof of Lemma 9.3 uses the following two facts, both of which are consequences of Theorem 3.1. Fact A.1.Letpbe prime, and letΓ =Z pa1 × · · · ×Zpat, wherea i ∈Nfor all1≤i≤t. LetΓ ′ be a subgroup ofΓ. ThenΓ ′ ∼= Zpb1 × · · ...
work page 1930
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.