I would like to know whether the problem described below has appeared in the literature and/or whether similar questions have been studied. I would be very happy to find some references or, if none exist, other people that might enjoy thinking about these questions.

Fix a finite abelian group $G$. The Davenport constant $D(G)$ is the smallest integer $m$ such that for any sequence $g_1, \ldots, g_m$ of elements of $G$ (repetitions allowed), there is some non-empty subsequence with sum zero, that is $\exists J \subseteq [m]$ with $J \neq \emptyset$ and $\sum_{j \in J} g_j = 0$.

There is a very neat folklore proof showing that $D(G) \leq |G|$: given any sequence of $|G|$ elements, let $s_k$ denote the sum of the first $k$ entries of the sequence. If one of the $s_k$ is zero, we are done. Otherwise by the pigeon-hole principle, two of them are equal, say $s_i = s_j$ for $i < j$. But then $J = (i+1, \ldots, j)$ does it.

For cyclic groups, this bound is easily seen to be tight. In the general case, the situation is much more difficult and the determination of $D(G)$ is still an open problem. What I want to get at is the following: The proof above shows more than just the existence of any subsequence with sum zero, it tells us that we can find one among a much smaller collection of candidates, namely all the subsequences of consecutive elements! Quantitatively, this narrows the exponential-size collection of all subsequences down to one of quadratic size (wrt $|G|$ in both cases).

Taking a small step of abstraction, let's call a hyper-graph (a collection of non-empty subsets of some finite set $V$) $G$-zero if for every labelling $f$ of its vertices with the elements of $G$ (repetitions allowed), there is some hyper-edge $e$ such that $\sum_{v \in e} f(v) = 0$. By definition, the hyper graph of all non-empty subsets of $V$ is $G$-zero if and only if $|V| \geq D(G)$. By the proof above, the hyper graph of all subpaths of a path on $n$ vertices is $G$-zero for $n \geq |G|$ (it is not hard to show that this is also necessary). The Erdos-Ginzburg-Ziv Theorem asserts that the hyper graph of all $n$-element subsets is $\mathbb{Z} / n\mathbb{Z}$-zero if $|V| \geq 2n-1$.

The question I am asking is: Given $G$ and $n \geq D(G)$, what is the minimum number $m_G(n)$ of edges in a $G$-zero hyper graph with $n$ vertices? How does this quantity behave as a function of $n$? What are the extremal hyper graphs?

EDIT: Maybe I should add some more detail.

(1) What to aim for: Since determining $D(G)$ is in general very hard, a complete solution might be out of reach (although it is conceivable that minimising this parameter is much easier). But solving it for some restricted classes of groups might be possible; for example for cyclic groups of prime order there is quite a lot of algebraic machinery that might help.

(2) Some easy observations: The argument presented above shows that there is a $G$-zero hyper graph on $\binom{|G|+1}{2}$ edges. For a lower bound on $m_G(n)$, let $H$ be a $G$-zero hyper graph on $n$ vertices. Just as with vertex-colorings of graphs, it is easy to show that $H$ must have a sub-hypergraph with minimum-degree at least $|G|$. Unfortunately, the edges might be very large and so double-counting only gives us $$ |E(H)| \geq |G| + \frac{1}{n-1}(|G|-1). $$ Hence roughly speaking, $m_G(n)$ always lies somewhere between $|G|$ and $|G|^2$. In the case of $G = (\mathbb{Z}/2\mathbb{Z})^m$, the complete hyper graph on $D(G) = m+1$ vertices is a surprisingly good candidate with only $2|G| - 1$ edges, almost matching the lower bound. For cyclic groups, on the other hand, this hyper graph is quite terrible.


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.