A linear upper bound on zero-sum Ramsey numbers of d d -degenerate graphs in ℤ p \mathbb{Z}_{p}
Andrey Shapiro · 2026
Read A linear upper bound on zero-sum Ramsey numbers of d d -degenerate graphs in ℤ p \mathbb{Z}_{p} by Andrey Shapiro (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-10864.txt.
Introduction
Shapiro proves a linear upper bound on zero-sum Ramsey numbers of d-degenerate graphs over Z_p for prime p. The zero-sum Ramsey number is the smallest size forcing a graph copy whose edge colors sum to zero, under any coloring of graph edges with values in Z_p. He shows the number is at most n plus (3 plus 3d) times p, provided m is at least 2pd(d+1) squared, p divides m, and 2d is below p. The result extends Colucci and D'Emidio's bound for 1-degenerate graphs.
Catalog record
| CREATOR | Andrey Shapiro |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39522 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.10864
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A linear upper bound on zero-sum Ramsey numbers of d d -degenerate graphs in ℤ p \mathbb{Z}_{p} Andrey Shapiro Abstract Let p p be a prime number and let G G be a graph on n n vertices and m m edges. The zero-sum Ramsey number of G G over ℤ p \mathbb{Z}_{p} , denoted by R ( G , ℤ p ) R(G,\mathbb{Z}_{p}) , is the minimum ℓ ∈ ℕ \ell\in\mathbb{N} such that for any edge-coloring c : E ( K ℓ ) → ℤ p c:E(K_{\ell})\to\mathbb{Z}_{p} , there is a subgraph G ′ ⊂ K ℓ G^{\prime}\subset K_{\ell} isomorphic to G G and satisfying ∑ e ∈ E ( G ′ ) c ( e ) = 0 \sum_{e\in E(G^{\prime})}c(e)=0 . We prove that if G G is a d d -degenerate graph, then R ( G , ℤ p ) ≤ n + ( 3 + 3 d ) p R(G,\mathbb{Z}_{p})\leq n+(3+3d)p so long as m ≥ 2 p d ( d + 1 ) 2 m\geq 2pd(d+1)^{2} , p p divides m m , and 2 d < p 2d<p . This generalizes a result by Colucci and D’Emidio on 1 1 -degenerate graphs. 1 Introduction The question of how large a disordered system must be before it exhibits a desired ordered subsystem lies at the core of Ramsey theory. This main idea lends itself to many formulations. In the context of graph theory one such formulation is: given a graph G and a color set C , determine the least \ell\in\mathbb{N} such that any edge-coloring c:E(K_{\ell})\to C of the complete graph will accommodate some injection f:V(G)\to V(K_{\ell}) such that f exhibits some desired property under the coloring c . In the classical form C=\{\text{blue},\text{red}\} and the goal is for f to be monochromatic, that is, \{f(x),f(y)\} has the same color for all edges \{x,y\}\in E(G) . Ramsey’s theorem [ 16 ] states that the accompanying Ramsey number (the least \ell\in\mathbb{N} such that such an injection into K_{\ell} always exists) is finite. We denote the Ramsey number by R(G) , and when C is expanded to contain k colors the k -color (classical) Ramsey number is denoted by R_{k}(G) . Since the classical formulation, the problem has taken on many variations that change the requirement on f (see, for example, Section 3 of the survey by Conlon, Fox, and Sudakov [ 10 ] ). In this work we are looking at a variation with an algebraic flavor, known as zero-sum Ramsey numbers. Definition 1.1 . Given a graph G and a finite abelian group \Gamma , the zero-sum Ramsey number of G over \Gamma , denoted by R(G,\Gamma) , is the minimum \ell\in{\mathbb{N}} such that for any edge-coloring c:E(K_{\ell})\to\Gamma , there exists a zero-sum injection f:V(G)\to V(K_{\ell}) . That is, f satisfies \sum_{\{x,y\}\in E(G)}c(\{f(x),f(y)\})=0_{\Gamma}. Ramsey’s theorem has an earlier counterpart outside the context of graphs in the form of Van der Waerden’s theorem [ 17 ] which states that for each r and k there is some n=W(r,k) such that any r -coloring of [n]\coloneqq\{1,2,...,n\} contains in it a monochromatic arithmetic progression of length k . Similarly, the story of zero-sum Ramsey theory on graphs starts outside of graphs in the form of the Erdős-Ginzburg-Ziv theorem [ 11 ] , which states that given 2m-1 elements in \mathbb{Z}_{m} , there is a collection of m of them summing to zero. These results inspired the above notion of R(G,\Gamma) which was introduced by Bialostocki and Dierker [ 3 ] . It is important to note that although R_{k}(G) is finite for all G and even any finite size of C , the same is not true for R(G,\Gamma) . Indeed, recalling that the exponent \exp(\Gamma) is the smallest integer r>0 such that g\cdot r=0_{\Gamma} for all g\in\Gamma , we require that \exp(\Gamma) divides e(G) , the number of edges in G . Without this, for any \ell\in\mathbb{N} we could define the constant coloring c(\{x,y\})=g where g\in\Gamma has some order r that does not divide e(G) . Then for any embedding, the sum of the edges would be g\cdot e(G)\neq 0_{\Gamma} . On the other hand, it is easy to see that with this requirement, R(G,\Gamma)\leq R_{|\Gamma|}(G) and therefore R(G,\Gamma) is finite. Furthermore, when p=e(G) , we get that R(G,\mathbb{Z}_{p})\geq R(G) by treating a red-blue coloring as a 0 - 1 coloring. Hence, the zero-sum Ramsey number is fundamentally linked to the classical Ramsey number. A breakthrough result by Lee [ 15 ] (resolving a long-standing conjecture of Burr and Erdös) states that R(G) is linear in n for a particular class of graphs, called d -degenerate graphs: Definition 1.2 . A graph G is d -degenerate if its vertex set can be ordered V(G)=\{v_{1},...,v_{n}\} so that for all i\in[n] , |\{v_{i}v_{j}\in E(G):j>i\}|\leq d. Preceding the result in [ 15 ] was the work by Chvátal, Rödl, Szemerédi, and Trotter [ 8 ] which showed that for all G with maximum degree \Delta , R(G) is linear in n (here, and for the rest of the paper, n\coloneqq|V(G)| and m\coloneqq e(G) ). Likewise, the current author with Katz, Lian, and Malekshahian [ 13 ] showed that R(G,\Gamma) is linear in n in the regime where G has maximum degree \Delta and |\Gamma| divides m . Hence, mirroring the results on classical Ramsey numbers, it is natural to conjecture (Conjecture 1 in [ 13 ] ) that R(G,\Gamma) is linear in n for all d -degenerate graphs (when |\Gamma| divides m ). In the context of graphs without isolated vertices, the work by Colucci and D’Emidio [ 9 ] took the first step in proving this for d=1 and cyclic groups \Gamma=\mathbb{Z}_{p} where their result implies that for all forests (i.e. 1 -degenerate graphs) R(G,\Gamma)\leq n+9p-12 under the condition that m=\Omega(p^{2}) . We improve this to all d -degenerate graphs, and significantly improve the constraint on m to be \Omega(p) . We also offer a slight improvement to the upper bound on R(G,\mathbb{Z}_{p}) when d=1 . Our main result, then, is the following theorem: Theorem 1.3 . Let G be a d -degenerate graph on n vertices and m edges and let p\leq m/(2d(d+1)^{2}) be a prime dividing m such that 2d<p . Then R(G,\mathbb{Z}_{p})\leq n+(3+3d)p. Notice that unlike the work on bounded degree graphs [ 13 ] , we do not allow |\Gamma|=|\mathbb{Z}_{p}|=m . This is because some sort of separation between p and m is necessary for the constant in front of p to remain small (whereas in [ 13 ] they show that for bounded degree graphs, R(G,\Gamma)\leq C\cdot n for some large constant C super-exponential in \Delta ). Indeed, even in the case of bipartite graphs with maximal degree \Delta , the results due to Graham et al. [ 12 ] tell us that there exists a graph G such that C^{\Delta}n\leq R(G) . But then recall that when p=m , R(G)\leq R(G,\mathbb{Z}_{p}) . Combining this with our result shows that if p_{1}=m and p_{2}\leq m/2d(d+1)^{2} are primes, then there exist d -degenerate graphs G such that R(G,\mathbb{Z}_{p_{1}})=2^{\Omega(d)}\cdot n\text{ \quad\quad while \quad\quad}R(G,\mathbb{Z}_{p_{2}})<2\cdot n. In general, the strength of the known bounds depends quite heavily