9
$\begingroup$

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.

$\endgroup$

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.