Zero sum cycles in complete digraphs

Abstract

Given a non-trivial finite Abelian group $(A,+)$, let $n(A)\ge 2$ be the smallest integer such that for every labelling of the arcs of the bidirected complete graph of order $n(A)$ with elements from $A$ there exists a directed cycle for which the sum of the arc-labels is zero. The problem of determining $n({\mathbb{Z}}_q)$ for integers $q\ge 2$ was recently considered by Alon and Krivelevich, who proved that $n({\mathbb{Z}}_q)=O(q\log q)$. Here we improve their bound and show that $n({\mathbb{Z}}_q)$ grows linearly. More generally we prove that for every finite Abelian group $A$ we have $n(A)\le 8|A|$, while if $|A|$ is prime then $n(A)\le \frac{3}{2}|A|$. As a corollary we also obtain that every $K_{16q}$-minor contains a cycle of length divisible by $q$ for every integer $q\ge 2$, which improves a result by Alon and Krivelevich.

8 pages