On three zero‐sum Ramsey‐type problems

Noga Alon, Yair Caro

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

Abstract

For a graph G whose number of edges is divisible by k, let R(G,Zk) denote the minimum integer r such that for every function f: E(Kr) ↦ Zk there is a copy G1 of G in Kr so that Σe∈E(G1) f(e) = 0 (in Zk). We prove that for every integer k1 R(Kn, Zk) ≤ n + O(k3 log k) provided n is sufficiently large as a function of k and k divides ( 2n). If, in addition, k is an odd prime‐power then R(Kn, Zk) ≤ n + 2k ‐ 2 and this is tight if k is a prime that divides n. A related result is obtained for hypergraphs. It is further shown that for every graph G on n vertices with an even number of edges R(G,Z2) ≤ n + 2. This estimate is sharp. © 1993 John Wiley & Sons, Inc.

Original languageEnglish (US)
Pages (from-to)177-192
Number of pages16
JournalJournal of Graph Theory
Volume17
Issue number2
DOIs
StatePublished - Jun 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Fingerprint Dive into the research topics of 'On three zero‐sum Ramsey‐type problems'. Together they form a unique fingerprint.

Cite this