pith. sign in

arxiv: 2605.21817 · v1 · pith:N4JXJVDInew · submitted 2026-05-20 · 🧮 math.CO

A linear upper bound on the mathbb{Z}_p-Ramsey number of graphs with sufficiently large 2-packing

Emily Heath , Andrew Simmons This is my paper

Pith reviewed 2026-05-22 08:14 UTC · model grok-4.3

classification 🧮 math.CO
keywords Z_p-Ramsey numberszero-sum graph colorings2-packings in graphsRamsey theory modulo plinear upper boundsedge sums in graphs
0
0 comments X

The pith

For graphs with a 2-packing of size p-1, the Z_p-Ramsey number is at most n + 6p - 9 when p is prime and divides the edge count.

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

The paper shows that any Z_p-edge-coloring of the complete graph on n + 6p - 9 vertices contains a copy of G whose edges sum to zero, provided G has n vertices, minimum degree at least one, p divides the number of edges, and G contains a 2-packing of size p-1. A sympathetic reader would care because the bound is linear in n instead of growing faster, and it covers all graphs meeting the packing condition. The same argument yields a constant additive term for any family of graphs whose maximum degree is bounded.

Core claim

The paper proves that R(G, Z_p) is at most n + 6p - 9 for every n-vertex graph G where p is prime, p divides the number of edges in G, the minimum degree is at least 1, and G admits a 2-packing of size p-1. The bound tightens when vertices in the 2-packing have higher degrees and is achieved in some cases. The same result gives an upper bound of the form R(G, Z_p) at most n plus a constant for all n-vertex graphs of bounded maximum degree.

What carries the argument

A 2-packing of size p-1, a collection of p-1 vertices whose closed neighborhoods are pairwise disjoint, used to select vertices that independently control possible color sums in the search for a monochromatic zero-sum copy of G.

If this is right

  • The upper bound improves when the vertices inside the 2-packing have larger degrees.
  • The result supplies an additive constant depending only on the degree bound and on p for every graph family with bounded maximum degree.
  • Equality holds between the stated upper bound and the actual Ramsey number for certain graphs and colorings.

Where Pith is reading between the lines

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

  • Similar linear bounds may hold for composite moduli provided a packing of appropriate size can be located.
  • Direct computation for small primes such as p = 3 or p = 5 on modest n could test how tight the additive term 6p - 9 actually is.
  • The packing condition might be relaxed or replaced by other local density assumptions while preserving a linear upper bound.

Load-bearing premise

The existence of a 2-packing of size exactly p-1 is what allows the color-sum control needed to build the zero-sum copy.

What would settle it

A counterexample would be a graph G on n vertices that has a 2-packing of size p-1, minimum degree at least 1, and p dividing its edge count, together with a Z_p-coloring of all edges in K_{n + 6p - 10} that contains no copy of G whose edges sum to zero.

Figures

Figures reproduced from arXiv: 2605.21817 by Andrew Simmons, Emily Heath.

Figure 1
Figure 1. Figure 1: By Lemma 1, finding a zero-sum copy of the graph on the left in a [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An example of switches that may arise in the proof of Theorem 1 for [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
read the original abstract

Given a positive integer $k$ and graph $G$, the $\mathbb{Z}_k$-Ramsey number $R(G,\mathbb{Z}_k)$ is the least $N$ (if it exists) such that every coloring $f:E(K_N)\rightarrow \mathbb{Z}_k$ contains a copy $G'$ of $G$ such that $\sum_{e\in E(G')}f(e)=0$. Motivated by a question of Caro and Mifsud, we study the $\mathbb{Z}_k$-Ramsey number of graphs with a sufficiently large 2-packing, i.e. a set of vertices $S\subseteq V(G)$ such that $N[u]\cap N[v]=\emptyset$ for all distinct $u,v\in S$. In particular, we prove that $R(G,\mathbb{Z}_p)\leq n+6p-9$ for all $n$-vertex graphs $G$ and all primes $p$ such that $p$ divides $e(G)$, the minimum degree of $G$ is at least $1$, and there exists a $2$-packing of $G$ with size $p-1$. This upper bound improves depending on vertex degrees in the $2$-packing, with equality in certain cases. The result also implies an upper bound of the form $R(G,\mathbb{Z}_p)\leq n+C$ for $n$-vertex graphs $G$ of bounded maximum degree.

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

Summary. The manuscript proves that if G is an n-vertex graph with minimum degree at least 1, p is a prime dividing e(G), and G admits a 2-packing of size exactly p-1, then the Z_p-Ramsey number satisfies R(G, Z_p) ≤ n + 6p - 9. The argument is purely combinatorial: the 2-packing is used to partition neighborhoods, after which a case analysis on partial color sums modulo p forces either a zero-sum monochromatic copy of G or a contradiction with the packing size, adding at most 6p-9 vertices in total. The bound is stated to improve with higher degrees inside the packing, and the result yields R(G, Z_p) ≤ n + C for graphs of bounded maximum degree.

Significance. If the stated bound holds, the result supplies an explicit linear upper bound on these zero-sum Ramsey numbers for graphs possessing a large 2-packing. The proof relies only on direct counting and neighborhood partitioning rather than probabilistic or algebraic machinery, which is a clear strength. The implication for bounded-degree graphs is useful, as it shows the additive term can be made independent of n. The work therefore gives a concrete, verifiable advance in the study of Z_p-Ramsey numbers.

minor comments (3)
  1. The abstract asserts that the bound 'improves depending on vertex degrees in the 2-packing, with equality in certain cases,' yet the main theorem statement does not record the refined expression in terms of those degrees; stating the improved bound explicitly would make the sharpness claim easier to verify.
  2. Section 2 (or the notation subsection) introduces the 2-packing but does not include a small illustrative example for p=3 or p=5; adding one would clarify how the packing controls the possible color sums.
  3. The final paragraph on bounded-degree graphs states an upper bound of the form n+C but does not record the explicit dependence of C on the maximum degree; supplying the dependence would strengthen the corollary.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, the assessment of its significance, and the recommendation of minor revision. No specific major comments appear in the report, so there are no individual points requiring direct response or rebuttal.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper proves the stated linear upper bound on R(G, Z_p) by direct combinatorial case analysis that invokes the given hypotheses (a 2-packing of size exactly p-1, p prime dividing e(G), and minimum degree at least 1) to partition neighborhoods and bound partial color sums modulo p. The additive term 6p-9 is obtained by counting the maximum number of additional vertices needed to force a monochromatic zero-sum copy or contradict the packing size; this counting follows immediately from the degree conditions and the packing hypothesis without any fitted parameters, self-referential definitions, or load-bearing self-citations. The argument is independent of the target bound and does not reduce any claimed result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard axioms of graph theory, the definition of closed neighborhoods, and the ring structure of Z_p; no free parameters, ad-hoc constants, or new postulated entities are introduced in the abstract.

axioms (1)
  • standard math Standard definitions and basic properties of graphs, closed neighborhoods, and edge colorings with elements of Z_p
    The Z_p-Ramsey number and 2-packing are defined using these background facts.

pith-pipeline@v0.9.0 · 5800 in / 1371 out tokens · 51799 ms · 2026-05-22T08:14:06.834756+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

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.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    On zero-sum

    Cheng Chi and Jialin He , year=. On zero-sum

    work page

  2. [2]

    A linear upper bound on zero-sum

    Andrey Shapiro , year=. A linear upper bound on zero-sum

    work page

  3. [3]

    On zero-sum

    Caro, Yair , year =. On zero-sum. The Quarterly Journal of Mathematics , doi =

    work page

  4. [4]

    ON ZERO SUM

    Bialostocki, A and Dierker, P , journal=. ON ZERO SUM. 1990 , publisher=

    work page 1990

  5. [5]

    On zero-sum

    Yair Caro , abstract =. On zero-sum. Discrete Mathematics , volume =. 1992 , issn =. doi:https://doi.org/10.1016/0012-365X(92)90621-L , url =

    work page doi:10.1016/0012-365x(92)90621-l 1992

  6. [6]

    Classic Papers in Combinatorics , pages =

    On a problem of formal logic , author =. Classic Papers in Combinatorics , pages =. 1987 , publisher =

    work page 1987

  7. [7]

    Ars Combinatoria , volume =

    Yair Caro and Yair Roditty , title=. Ars Combinatoria , volume =

    work page

  8. [8]

    A complete characterization of the zero-sum (mod 2)

    Yair Caro , abstract =. A complete characterization of the zero-sum (mod 2). Journal of Combinatorial Theory, Series A , volume =. 1994 , issn =. doi:https://doi.org/10.1016/0097-3165(94)90098-1 , url =

    work page doi:10.1016/0097-3165(94)90098-1 1994

  9. [9]

    Alvarado and Lucas Colucci and Roberto Parente , year=

    José D. Alvarado and Lucas Colucci and Roberto Parente , year=. On a problem of

    work page

  10. [10]

    On zero-sum

    Caro, Yair and Mifsud, Xandru , journal=. On zero-sum

    work page

  11. [11]

    Theorem in the additive number theory , author=. Bull. Res. Council Israel Sect. F 10F , volume=. 1961 , page=

    work page 1961

  12. [12]

    Combinatorica , volume=

    Edge-colored complete graphs with precisely colored subgraphs , author=. Combinatorica , volume=. 1983 , publisher=

    work page 1983

  13. [13]

    Journal of the London Mathematical Society , volume=

    On the addition of residue classes , author=. Journal of the London Mathematical Society , volume=. 1935 , publisher=

    work page 1935

  14. [14]

    Discrete Mathematics , volume =

    Zero-sum problems -- A survey , author =. Discrete Mathematics , volume =. 1996 , issn =. doi:https://doi.org/10.1016/0012-365X(94)00308-6 , url =

    work page doi:10.1016/0012-365x(94)00308-6 1996

  15. [15]

    A linear upper bound on the zero-sum

    Lucas Colucci and Marco D'Emidio , year=. A linear upper bound on the zero-sum

    work page

  16. [16]

    A linear upper bound for zero-sum

    Jasmin Katz and Xiaopan Lian and Alexandru Malekshahian and Andrey Shapiro , year=. A linear upper bound for zero-sum

    work page

  17. [17]

    A Weighted

    Grynkiewicz, David , year =. A Weighted. Combinatorica , doi =

    work page

  18. [18]

    1996 , issn =

    Zero-sum Ramsey numbers modulo 3 , journal =. 1996 , issn =. doi:https://doi.org/10.1006/jcta.1996.0068 , author =

    work page doi:10.1006/jcta.1996.0068 1996