On zero-sum Ramsey numbers of complete bipartite graphs
Cheng Chi, Jialin He · 2026
Read On zero-sum Ramsey numbers of complete bipartite graphs by Cheng Chi, Jialin He (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-2606-29216.txt.
Introduction
Chi and He pin down zero-sum Ramsey numbers for complete bipartite graphs. In this Ramsey problem, the edges of a large complete graph are labelled with numbers from a cyclic group. The zero-sum Ramsey number is the smallest size forcing a copy of a target graph whose edge labels add to zero. Their target is the complete bipartite graph, with vertices split into two sides joined by all cross edges.
They prove that for each modulus q there is an explicit threshold beyond which the number equals the obvious lower bound: the side sizes simply add. For the case q equals three they determine the number completely. It matches the bound except for a short list of small exceptions and one infinite family, where it is one larger. That case also shows their general threshold cannot be improved.
Catalog record
| CREATOR | Cheng Chi, Jialin He |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.29216
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On zero-sum Ramsey numbers of complete bipartite graphs Cheng Chi, Jialin He Abstract For an integer q ≥ 2 q\geq 2 and a graph F F satisfying q | e ( F ) q\mid e(F) , the zero-sum Ramsey number R ( F , ℤ q ) R(F,\mathbb{Z}_{q}) is the least integer n n such that every edge-labeling w : E ( K n ) → ℤ q w\colon E(K_{n})\to\mathbb{Z}_{q} contains a copy of F F whose edge-label sum is zero in ℤ q \mathbb{Z}_{q} . Write K s , t K_{s,t} for the complete bipartite graph with s s vertices on one side and t t vertices on the other side. We prove that for every integer q ≥ 2 q\geq 2 , there is an explicit threshold S ( q ) S(q) such that R ( K s , q k , ℤ q ) = s + q k R(K_{s,qk},\mathbb{Z}_{q})=s+qk for all s ≥ S ( q ) s\geq S(q) and all k ≥ 1 k\geq 1 . We also determine the zero-sum Ramsey number of K s , 3 k K_{s,3k} over ℤ 3 \mathbb{Z}_{3} completely. We show that R ( K s , 3 k , ℤ 3 ) = s + 3 k R(K_{s,3k},\mathbb{Z}_{3})=s+3k , except when s = 2 s=2 and k ≥ 1 k\geq 1 , or when s ∈ { 3 , 4 , 5 , 7 } s\in\{3,4,5,7\} and k = 1 k=1 . In these exceptional cases, R ( K s , 3 k , ℤ 3 ) = s + 3 k + 1 R(K_{s,3k},\mathbb{Z}_{3})=s+3k+1 . In particular, this implies that the threshold S ( q ) S(q) is best possible for q = 3 q=3 . 1 1 footnotetext: School of Mathematical Sciences, Shanghai Jiao Tong University, 800 Dongchuan Road, Shanghai 200240, China. Email: [email protected]. Supported by National Key R&D Program of China under grant No. 2022YFA1006400 and National Natural Science Foundation of China No. 12571376. 2 2 footnotetext: Corresponding Author. 4 4 footnotetext: School of Mathematical Sciences, Key Laboratory of MEA (Ministry of Education) and Shanghai Key Laboratory of PMMP, East China Normal University, Shanghai 200241, China. Email: [email protected]. Supported in part by Science and Technology Commission of Shanghai Municipality No. 22DZ2229014. 1 Introduction Zero-sum Ramsey theory is a group-labelled analogue of classical Ramsey theory. Instead of seeking a monochromatic copy of a prescribed graph, one labels the edges of a complete graph by elements of a finite abelian group and asks for a copy whose total edge-label is the identity. This area was initiated by Bialostocki and Dierker [ 3 , 4 ] , motivated in part by the Erdős–Ginzburg–Ziv theorem [ 19 ] and the Cauchy–Davenport theorem [ 14 , 18 ] ; see Caro’s survey [ 10 ] for background. Throughout the paper we work with the cyclic group \mathbb{Z}_{q} , where q\geq 2 . For a graph G , the zero-sum Ramsey number R(G,\mathbb{Z}_{q}) is the least integer n such that every edge-labeling w\colon E(K_{n})\to\mathbb{Z}_{q} contains a copy G^{\prime} of G with \sum_{e\in E(G^{\prime})}w(e)=0 in \mathbb{Z}_{q} . The divisibility condition q\mid e(G) is necessary, since the constant labeling w(e)=1 gives a nonzero sum on every copy of G . Conversely, if q\mid e(G) , then R(G,\mathbb{Z}_{q}) is finite by the ordinary multicolor Ramsey theorem [ 25 ] , because any monochromatic copy of G is zero-sum. A related bipartite-host version was studied earlier by Caro [ 8 ] . In that setting, one colors the edges of a complete bipartite host graph and asks for a zero-sum copy of a prescribed bipartite graph. This differs from the present parameter, where the host graph is complete and the target graph is K_{s,t} . Determining exact values of R(G,\mathbb{Z}_{q}) is difficult beyond a few special cases. For q=2 , Caro gave a complete characterization of R(G,\mathbb{Z}_{2}) for every graph G with an even number of edges [ 9 ] . For q\geq 3 , no comparable general theory is known. Even for complete graphs, substantial work of Alon and Caro [ 1 ] , Caro [ 6 , 11 ] , and Harborth and Piepmeyer [ 20 , 21 ] leaves some cases open, including residue classes over \mathbb{Z}_{3} ; see [ 12 ] . Other exact results are known for stars and matchings [ 4 , 7 ] . Trees and forests have also received considerable attention. Caro and Roditty posed a conjecture concerning the zero-sum Ramsey number of trees [ 13 ] . More recently, Caro and Mifsud initiated a systematic study over \mathbb{Z}_{3} , proving sharp n+O(1) -type bounds for forests [ 12 ] . Subsequently, Alvarado, Colucci and Parente determined the exact \mathbb{Z}_{3} -Ramsey numbers of forests without isolated vertices [ 2 ] . For graphs containing cycles, much less is known. Cycles are the most basic family in this direction. Related zero-sum cycle-existence results have been obtained for group-labelled complete digraphs [ 24 ] . For ordinary cycles of prescribed length, several ranges of zero-sum Ramsey numbers are known, but the general picture remains incomplete. For example, Caro [ 6 , 10 ] conjectured that R(C_{q},\mathbb{Z}_{q})=4q-3 for every odd q\geq 5 , a problem that remains open in general. See [ 15 , 22 ] for recent progress on cycles and wheels. Recent general results show that zero-sum Ramsey numbers are often close to the vertex-count lower bound for sparse or locally sparse graphs. Katz, Lian, Malekshahian and Shapiro proved linear bounds for bounded-degree graphs over finite abelian groups [ 23 ] ; for prime moduli, sharper n+O_{p}(1) -type bounds have been obtained for forests [ 17 ] , degenerate graphs under suitable hypotheses [ 26 ] , and graphs with large 2 -packings [ 22 ] . Complete bipartite graphs K_{s,t} , however, fall outside these frameworks when both parts grow: they have unbounded maximum degree and degeneracy, diameter two, and no large 2 -packing. Their natural lower bound is simply R(K_{s,t},\mathbb{Z}_{q})\geq s+t . Our first contribution is to show that for every integer q\geq 2 , this trivial lower bound is sharp for complete bipartite graphs, once s is sufficiently large as a function of q . For an integer q\geq 2 , let g=\gcd(q,2) , d=q/g and M(q)=R(K_{q},\mathbb{Z}_{d}) . When d=1 , we regard \mathbb{Z}_{1} as the trivial group and set R(K_{m},\mathbb{Z}_{1})=m . Let S(q)=gM(q)-q-g+1 . Theorem 1.1 . Let q\geq 2 be an integer. For every k\geq 1 and every s\geq S(q) , we have R(K_{s,qk},\mathbb{Z}_{q})=s+qk. Theorem 1.1 may be compared with the following elementary upper bound due to Erdős–Ginzburg–Ziv theorem [ 19 ] . For all integers q\geq 2 , s\geq 1 , and k\geq 1 , R(K_{s,qk},\mathbb{Z}_{q})\leq s+qk+q-1. Indeed, let N=s+qk+q-1 , and let w\colon E(K_{N})\to\mathbb{Z}_{q} be an arbitrary edge-labeling. Fix an s -set A=\{u_{1},\ldots,u_{s}\}\subseteq V(K_{N}) , and let C=V(K_{N})\setminus A . Then |C|=qk+q-1 . For each v\in C , define a_{v}=\sum_{u\in A}w(uv)\in\mathbb{Z}_{q}. By the Erdős–Ginzburg–Ziv theorem, the sequence (a_{v})_{v\in C} contains a subsequence indexed by a set B\subseteq C with |B|=qk and \sum_{v\in B}a_{v}=0 in \mathbb{Z}_{q} . Hence, \sum_{v\in B}\sum_{u\in A}w(uv)=0 in \mathbb{Z}_{q} . Thus the