\documentclass[12pt]{article} % % Title: A generalization of Kneser's Addition Theorem % Authors: Matt DeVos, Luis Goddyn, and Bojan Mohar % Email: {mdevos,goddyn,mohar}@sfu.ca % \usepackage{graphicx} \title{A generalization of Kneser's Addition Theorem} \author{Matt DeVos, Luis Goddyn\thanks{Supported by a Canada NSERC Discovery Grant.}, and Bojan Mohar\thanks{Supported in part by Slovenian Research Grant P1--0297 and by Canadian NSERC Discovery Grant and by the CRC program.}~\thanks{On leave from: IMFM \& FMF, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia.}\\ {Department of Mathematics}\\ {Simon Fraser University}\\ {Burnaby, B.C. V5A 1S6} \\ email: {\tt [mdevos,goddyn,mohar]@sfu.ca} } \date{\today} \hsize=6in \vsize=9in \oddsidemargin 0pt % Left margin on odd-numbered pages. \evensidemargin 0pt % Left margin on even-numbered pages. \marginparwidth 40pt % Width of marginal notes. \marginparsep 10pt % Horizontal space between outer margin and % marginal note % VERTICAL SPACING: \topmargin 0pt % Nominal distance from top of page to top of % box containing running head. \headsep 10pt % Space between running head and text. % DIMENSION OF TEXT: \textheight 8.4in % Height of text(including footnotes and figures, % excluding running head and foot). \textwidth 6.5in % Width of text line. \renewcommand{\baselinestretch}{1.3} \topmargin 0pt \headsep 10pt \pagestyle{myheadings} \thispagestyle{empty} \usepackage{amsfonts} \usepackage{amsmath} \usepackage{enumitem} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{observation}[theorem]{Observation} \newtheorem{definition}[theorem]{Definition} \newtheorem{claim}{Claim} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{problem}[theorem]{Problem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Authors' definitions % \newcommand\A{{\bf A}} \newcommand\Aprime{{\bf A'}} \newcommand\Apprime{{\bf A''}} \newcommand\Appp{{\bf A'''}} \renewcommand\a{{\bf a}} \newcommand\subsetsum[1]{\Sigma^{#1}} \newcommand\subsetsumk{\subsetsum{k}} %\newcommand\rk{\mathrm{rk}} \DeclareMathOperator{\rk}{rk} \DeclareMathOperator{\stab}{stab} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \maketitle \begin{abstract} Let $\A = (A_1,\ldots,A_m)$ be a sequence of finite subsets from an additive abelian group~$G$. Let $\subsetsum{\ell}(\A)$ denote the set of all group elements representable as a sum of $\ell$ elements from distinct terms of $\A$, and set $H = \stab (\subsetsum{\ell}(\A)) = \{ g \in G : g + \subsetsum{\ell}(\A) = \subsetsum{\ell}(\A) \}$. Our main theorem is the following lower bound: \[|\subsetsum{\ell}(\A)| \ge |H| \Bigl(1 - \ell + \sum_{Q \in G/H} \min \bigl\{ \ell, | \{i \in \{1,\ldots,m\} : A_i \cap Q \neq \emptyset \} | \bigr\} \Bigr). \] In the special case when $m=\ell=2$, this is equivalent to Kneser's addition theorem, and indeed we obtain a new proof of this result. The special case when every $A_i$ has size one is a new result concerning subsequence sums which extends some recent work of Bollob\'as-Leader, Hamidoune, Hamidoune-Ordaz-Ortu\~{n}o, Grynkiewicz, and Gao, and resolves two recent conjectures of Gao, Thangadurai, and Zhuang. \end{abstract} \section{Introduction} Throughout we shall assume that $G$ is a (possibly infinite) additive abelian group. Let $A,B \subseteq G$ and $g \in G$. We define the {\it sumset} $A + B = \{ a + b : a \in A, b \in B \}$ and we define $g+A = A+g = \{g\} + A$. Any set of the form $g+A$ is called a {\it shift} of $A$. We define the {\it stabilizer} of $A$ to be $\stab (A) = \{ g \in G \mid g + A = A \}$. Note that $\stab(A) \le G$. The starting point for our subject is the following classical result of Cauchy \cite{Cau} and Davenport \cite{Dav} (see also \cite{Na}), which gives a lower bound on $|A+B|$ for groups of prime order. Here we let ${\mathbb Z}_n = {\mathbb Z}/n{\mathbb Z}$. \begin{theorem}[Cauchy-Davenport] If $p$ is prime and $A,B \subseteq {\mathbb Z}_p$ are nonempty, then $|A+B| \ge \min\{ p, |A| + |B| -1 \}$. \end{theorem} This theorem was generalized by Kneser \cite{Kn} to all abelian groups as follows. \begin{theorem}[Kneser] \label{kn_thm} If $A,B \subseteq G$ are finite and nonempty and $H =\stab(A+B)$, then $|A+B| \ge |A+H| + |B+H| - |H|$. \end{theorem} Our principal subject matter is sequences of sets. If $\A = (A_1,A_2,\ldots,A_m)$ is a sequence of finite subsets of $G$, and $\ell \le m$, we define \[ \subsetsum{\ell}(\A) = \{ a_{i_1} + \cdots + a_{i_{\ell}} : \mbox{$1 \le i_1 < \cdots < i_{\ell} \le m$ and $a_{i_j} \in A_{i_j}$ for every $1 \le j \le {\ell}$} \}. \] So $\subsetsum{\ell}(\A)$ is the set of all elements which can be represented as a sum of $\ell$ terms from distinct members of $\A$. The following is our main result. \begin{theorem} \label{main_thm} Let\/ $\A = (A_1,\ldots,A_m)$ be a sequence of finite subsets of\/ $G$, let $\ell \le m$, and let\/ $H = \stab(\subsetsum{\ell}(\A))$. If\/$\subsetsum{\ell}(\A)$ is nonempty, then \[ |\subsetsum{\ell}(\A)| \ge |H| \Bigl(1 - \ell + \sum_{Q \in G/H} \min \big\{\ell , | \{i \in \{1,\ldots,m\} : A_i \cap Q \neq \emptyset \} | \big\} \Bigr). \] \end{theorem} In the special case when $m=\ell=2$, our result is equivalent to Kneser's Theorem, and our argument gives a new proof of this theorem. In fact, this new proof was found by the first author somewhat earlier than this more general argument, and will be published elsewhere. \bigskip A rich subject closely related to sumsets is the study of subsequence sums. Given a sequence $\a = (a_1,a_2,\ldots,a_m)$ of elements of $G$, we define \[ \subsetsum{\ell}(\a) = \{ a_{i_1} + a_{i_2} + \cdots + a_{i_{\ell}} : 1 \le i_1 < i_2 < \cdots < i_{\ell} \le m \}. \] So $\subsetsum{\ell}(\a)$ is the set of all group elements representable as a sum of an $\ell$-term subsequence of $\a$. The study of subsequence sums features a wide expanse of interconnected results. In the remainder of the introduction, we shall take a tour of some of these theorems, and then move on to some related results on graphs and matroids. Our tour begins with the following classic theorem of Erd\H{o}s, Ginzburg, and Ziv \cite{EGZ}. \begin{theorem}[Erd\H{o}s, Ginzburg, Ziv] \label{egz_thm} If\/ $|G| = {\ell}$ and $\a=(a_1,a_2,\ldots,a_{2\ell-1})$ is a sequence of elements from $G$, then $0 \in \subsetsum{\ell}(\a)$. \end{theorem} This theorem has recently been generalized in a number of different directions, some of which we will discuss shortly. However, first let us point out that the special case of our theorem when each $A_i$ has size one gives a natural lower bound for subsequence sums. This is stated below as Corollary \ref{seq_cor}. This corollary may be used to derive Theorem \ref{egz_thm}, so we may view this as another generalization of Erd\H{o}s-Ginzburg-Ziv. However, as we shall show, this corollary is strong enough to imply several other generalizations of it. See Figure \ref{fig:dep}. \begin{corollary} \label{seq_cor} If\/ $\a = (a_1,a_2,\ldots,a_m)$ is a sequence of elements of\/ $G$, $\ell \le m$, and\/ $H = \stab(\subsetsum{\ell}(\a))$, then \begin{equation} \label{seq_eqn} |\subsetsum{\ell}(\a)| \ge |H| \Bigl(1 - {\ell} + \sum_{Q \in G/H} \min \big\{\ell, | \{i \in \{1,\ldots,m\}: a_i \in Q \} | \big\} \Bigr). \end{equation} \end{corollary} Note that if $\a = (a_1,\ldots,a_m)$ and $\ell \le m$, then it follows immediately that $\subsetsum{m - \ell}(\a) = (\sum_{i=1}^m a_i) - \subsetsum{\ell}(\a)$. Thus, the sets $\subsetsum{m-\ell}(\a)$ and $-\subsetsum{\ell}(\a)$ are shifts of one another, and in particular, these two sets have the same size and the same stabilizer. As such, our theorem may be applied in two different ways to a given sequence $\a$, and generally these two bounds will be different. Let us remark that Corollary \ref{seq_cor} is a slight strengthening of a result in \cite{Gr1} which follows from Grynkiewicz's ``partition analogue of the Cauchy-Davenport Theorem" (hereafter called {\it Grynkiewicz's partition theorem}). This theorem of Grynkiewicz concerns a refinement of a partition of a sequence into sets, and we shall not state it in full, but a key consequence of it is as follows. If $\a = (a_1,\ldots,a_m)$ is a sequence of elements from $G$, then there exists a subset $C \subseteq \subsetsum{\ell}(\a)$ and a subgroup $H \le \stab(C)$ for which inequality (\ref{seq_eqn}) holds with the left hand side replaced by $|C|$. \bigskip Now let us commence with our tour with some generalizations of the Erd\H{o}s-Ginzburg-Ziv Theorem. In this theorem, the authors study only sequences of length $2|G|-1$ and subsequences of length $|G|$. Perhaps the most obvious attempt at generalization would be to consider what happens when we consider different length sequences and subsequences (although it is not obvious how the conclusion should be modified). Indeed, Bollob\'as and Leader \cite{BL} found a nice generalization of Theorem \ref{egz_thm} by considering subsequences of length $|G|$ from an arbitrary sequence. Hamidoune \cite{Ha2} further generalized this with the following theorem, where subsequences of arbitrary length are considered. Here ${\mathbb N}$ denotes the set of nonnegative integers. \begin{theorem}[Hamidoune] \label{ham_thm} Let $\a = (a_1,\ldots,a_m)$ be a sequence of %L%elements from $G$, let $\ell \in {\mathbb N}$, and assume $\ell \le elements from $G$, let $\ell \in {\mathbb N}$, and assume $1 \le \ell \le m \le 2\ell-1$. Then one of the following holds: \begin{enumerate}[label={\rm (\roman{*}) \ }, ref={\rm (\arabic{*})}] \item $|\subsetsum{\ell}(\a)| \ge m-{\ell}+1$. \item There exists $i \in \{1,\ldots,m\}$, so that $\ell a_i \in \subsetsum{\ell}(\a)$. \end{enumerate} \end{theorem} Both Grynkiewicz's partition theorem and our Corollary \ref{seq_cor} imply Theorem~\ref{ham_thm}. To derive Theorem \ref{ham_thm} from Corollary \ref{seq_cor}, note that if there is an $H$-coset $Q \in G/H$ so that $| \{ 1 \le i \le m : a_i \in Q \} | \ge {\ell}$, then $\subsetsum{\ell}(\a)$ contains the $H$-coset $\ell Q$, so ${\ell} a_i \in \subsetsum{\ell}(\a)$ for every $1 \le i \le m$ with $a_i \in Q$. Otherwise, our bound immediately implies $|\subsetsum{\ell}(\a)| \ge m-\ell+1$. \bigskip Perhaps the most obvious way to limit the size of $\subsetsum{\ell}(\a)$ is to choose $\a$ so that all or almost all of its entries are the same. Accordingly, a number of authors have %L%studied the effect of limiting the maximum number of times a group %L%element may appear in the sequence. studied the effect of limiting the maximum multiplicity \[ \rho(\a) = \max_{g \in G} | \{ i \in \{1,\ldots,m\} : a_i = g\} | \] among elements in $\a$. Next we state a two-part conjecture due to Gao, Thangadurai, and Zhuang (Conjectures 1 and 2 in \cite{GTZ}) on this theme. %L% Moved the discussion to AFTER its statement %They prove this conjecture in the %special case when $\ell = p^n$ for a prime $p$. More recently, Cao %\cite{Ca} verified part (1). when $\ell = p^n q^{n'}$ where $p,q$ are %prime, and Gao \cite{Ga2} proved a slightly weaker form of part (1) %in general. %L% Before stating this conjecture, we need a little more %L%notation. If $\a = (a_1,\ldots,a_m)$ is a sequence in a group $G$, %L%we let $\rho(\a) = \max_{g \in G} |\{ 1 \le i \le m : a_i = g\}|$ %L%(so $\rho(\a)$ is the maximum multiplicity of an element). Also, we %let $\subsetsum{}(\a) = \cup_{i=0}^m \subsetsum{i}(\a)$. We use the notation $\subsetsum{}(\a) = \cup_{i=0}^m \subsetsum{i}(\a)$. \begin{conjecture}[Gao, Thangadurai, Zhuang] %L%\label{gao_conj} Let $\ell$ be a positive integer, let $p$ be the %L%\label{gao_conj} Let $\ell \in \mathbb N$, $\ell \ge 2$, let $p$ be the \label{gao_conj} Let $\ell>1$ be an integer, let $p$ be the smallest prime divisor of $\ell$, and let $\a = (a_1,a_2,\ldots,a_m)$ be a sequence of elements from ${\mathbb Z}_{\ell}$. If $m \ge \ell + \frac{\ell}{p} - 1$ and $\rho(\a) \le m - \ell$, then both of the following hold. %\begin{enumerate}[ref={\rm (\arabic{*})}] \begin{enumerate}[label={\rm (\arabic{*}) \ }, ref={\rm (\arabic{*})}] \item $0 \in \subsetsum{\ell}(\a)$. \item If\/ $0$ appears exactly $m-\ell$ times in $\a$, then $\subsetsum{m-\ell}(\a) = \subsetsum{}(\a)$. \end{enumerate} \end{conjecture} The proposers prove this conjecture in the case where $\ell$ is a prime power. More recently, Cao \cite{Ca} verified part (1) when $\ell$ is the product of two prime powers, % = p^n q^{n'}$ where $p,q$ are prime, and Gao \cite{Ga2} proved a slightly weaker form of part (1) for general $\ell$. %in general. Conjecture \ref{gao_conj} follows from our next corollary (proved in Section 3). \begin{corollary} \label{easy_cor} Let $G$ be a nontrivial finite abelian group and let $p$ be the smallest prime divisor of\/ $|G|$. Let $\a = (a_1,\ldots,a_m)$ be a sequence of elements from $G$, let $\ell \le m$ and set $H = \stab(\subsetsum{\ell}(\a))$. If $m \ge \ell + \frac{\ell}{p} - 1$ and $\rho(\a) \le m - \ell$, then one of the following holds. \begin{enumerate}[label={\rm (\roman{*}) \ }, ref={\rm (\arabic{*})}] \item $|\subsetsum{\ell}(\a)| \ge \ell$. \item $H \neq \{0\}$ and there exists $Q \in G/H$ so that~ $ |\{i \in \{1,\ldots,m\} : a_i \in Q \}| > \ell$. \end{enumerate} \end{corollary} Let us pause to show that the above corollary implies Conjecture \ref{gao_conj}. %L% Assuming the initial assumptions of Conjecture With the assumptions of Conjecture \ref{gao_conj}, both parts (1) and (2) %L%\ref{gao_conj} and applying the corollary, both part (1) and (2) follow from Corollary \ref{easy_cor} if conclusion (i) holds (as then $\subsetsum{\ell}(\a) = \subsetsum{m-\ell}(\a) = {\mathbb Z}_{\ell}$), so we may assume that (ii) holds. Then $H = \ell Q \subseteq \subsetsum{\ell}(\a)$ and part (1) follows. For part (2), note that since $0$ appears $m - \ell$ times, $Q$ must equal $H$, so the image of $\a$ under the canonical quotient mapping from ${\mathbb Z}_{\ell}$ to ${\mathbb Z}_{\ell}/H$, call it ${\bf b}$, is a sequence with fewer than $m - \ell$ nonzero terms. Thus $\subsetsum{m - \ell}({\bf b}) = \subsetsum{}({\bf b})$. It follows from this that $\subsetsum{m - \ell}(\a) = \subsetsum{}(\a)$. \bigskip Bialostocki and Dierker \cite{BD} generalized the Erd\H{o}s-Ginzburg-Ziv theorem by studying sequences of length $2|G|-2$ and characterizing those without zero-sum subsequences of length $|G|$. They prove that (for nontrivial groups), such sequences can only occur when $G$ is cyclic, and the sequence contains exactly two group elements, each occurring exactly $|G|-1$ times. Stated another way, every sequence of length $2|G|-2$ with at least three distinct terms must have a zero-sum subsequence of length $|G|$. Indeed, the assumption that a sequence has many distinct terms also tends to increase the number of distinct subsequence sums, and a number of authors have studied this phenomenon. Next we state a theorem of Grynkiewicz \cite{Gr2} which exploits a distinctness assumption. This theorem resolved a conjecture of Hamidoune \cite{Ha2}, and extended some earlier results of Hamidoune \cite{Ha2}, and Hamidoune, Ordaz, and Ortu\~{n}o \cite{HOO}, in addition to the Bialostocki-Dierker theorem mentioned above. \begin{theorem}[Grynkiewicz] \label{gry_thm} Let $G$ be an abelian group of order $\ell$ and let\/ $\a = (a_1,\ldots,a_m)$ be a sequence of elements from $G$ with $m > \ell$. If\/ $\a$ contains at least $k$ distinct terms and $\rho(\a) \le \ell - k + 2$, then one of the following holds. \begin{enumerate}[label={\rm (\roman{*}) \ }, ref={\rm (\arabic{*})}] \item $|\subsetsum{\ell}(\a)| \ge \min\{\ell, m-{\ell}+k-1\}$. \item There is a nontrivial subgroup $H \le \stab(\subsetsum{\ell}(\a))$ with $H \subseteq \subsetsum{\ell}(\a)$, there is an $H$-coset $Q$ which contains all but at most $t$ terms of\/$\a$ where $t \le \min \{ \lfloor \frac{ m - \ell + k - 2 }{|H|} \rfloor - 1, [G:H] - 2 \}$ and $|\subsetsum{\ell}(\a)| \ge (t+1)|H|$. \end{enumerate} \end{theorem} By setting $k=3$ and $m = 2\ell - 2$ and applying the above theorem, we deduce that $0 \in \subsetsum{\ell}(\a)$. This is the heart of the aforementioned result of Bialostocki-Dierker. Theorem \ref{gry_thm} appears to be close to the truth for small values of $k$, but we do not know in general when these lower bounds are tight. Our Corollary \ref{seq_cor} can also be used to derive Theorem \ref{gry_thm}. Indeed, it implies the following stronger result where the dependence on the order of the group has been removed. %L% Moved back %Here we let ${\mathbb N}$ denote the set of nonnegative integers. \begin{corollary} \label{tricky_cor} Let $m, k, \ell \in {\mathbb N}$ with $\ell < m$, let $\a = (a_1,\ldots,a_m)$ be a sequence of elements from $G$ with $H = \stab(\subsetsum{\ell}(\a))$. If $\a$ contains at least $k$ distinct terms, and $\rho(\a) \le \ell - k + 2$, then one of the following holds. \begin{enumerate}[label={\rm (\roman{*}) \ }, ref={\rm (\arabic{*})}] \item $|\subsetsum{\ell}(\a)| \ge \min\{\ell + 1, m - \ell + k - 1\}$ . \item $H \neq \{0\}$, there exists $Q \in G/H$ so that $| \{i \in \{1,\ldots,m\} : a_i \in Q \}| > \ell$. \end{enumerate} \end{corollary} Next, let us indicate how the above corollary implies Theorem \ref{gry_thm}. Given the assumptions of Theorem \ref{gry_thm} and applying Corollary \ref{tricky_cor}, we are done immediately if conclusion (i) holds, so we may assume that conclusion (ii) holds. Assuming further that $|\subsetsum{\ell}(\a)| < \ell$ (otherwise we are done) the bound from Corollary \ref{seq_cor} shows that $Q$ is the only $H$-coset containing $\ge \ell$ terms of $\a$, and further, setting %L%$t = 1 + | \{ 1 \le i \le m : a_i \not\in Q \} |$ we have $t = | \{ 1 \le i \le m : a_i \not\in Q \}|$ we have $|\subsetsum{\ell}(\a)| \ge |H|(t+1)$. Assuming $|\subsetsum{\ell}(\a)| < \min\{\ell, m-{\ell}+k-1\}$ (otherwise we are done), this yields the upper bound on $t$ given in Theorem \ref{gry_thm}. \bigskip Finally, we introduce a fundamental result of Gao \cite{Ga}. For %L%any finite abelian group $G$, we define the {\it Davenport constant} every finite abelian group $G$, the {\it Davenport constant} of $G$, denoted $s(G)$, is the smallest positive integer $k$ so that every sequence of elements of $G$ with length $\ge k$ has a nontrivial subsequence which sums to $0$. Similarly, we define $s'(G)$ to be the smallest positive integer $k$ so that every sequence of elements of $G$ with length $\ge k$ has a subsequence of length $|G|$ which sums to $0$. So the Erd\H{o}s-Ginzburg-Ziv theorem asserts that $s'(G) \le 2|G| - 1$ for every finite abelian group $G$. It is an easy exercise to show that $s(G) \le |G|$ for every $G$. In light of this, the following theorem of Gao \cite{Ga} may also be viewed as a generalization of Theorem \ref{egz_thm}. \begin{theorem}[Gao] \label{gao_thm} $s'(G) = s(G) + |G| - 1$ for every finite abelian group $G$. \end{theorem} In the third section of our paper we will use Corollary \ref{seq_cor} to obtain a new proof of Gao's Theorem. Although our proof of Gao's Theorem is no shorter than existing proofs, we have included it since it follows naturally from our result in a manner similar to that of the other generalizations of Erd\H{o}s-Ginzburg-Ziv. \bigskip Instead of considering all possible $\ell$-element subsequences of a given sequence $\a$, one might introduce some additional structure on $\a$ and consider only certain special types of subsequences. Bialostocki and Dierker \cite{BD2} did this by introducing an underlying geometry in the form of a graph. Let $X$ be a graph and let $w : E(X) \rightarrow G$ be a map. %For every $S \subseteq E(X)$, we let $w(S) = \sum_{x \in S} w(x)$ and We define $w(X) = \{ \sum_{e \in E(T)} w(e) : \mbox{$T$ is %the edge set of a spanning tree of $X$} \}$. \begin{theorem}[Bialostocki-Dierker] \label{bd_thm} Let $p$ be prime, let $X$ be a complete graph on $p+1$ vertices, and let $w : E(X) \rightarrow {\mathbb Z}_p$ be a map. Then $0 \in w(X)$. \end{theorem} This theorem suggested a rather different type of zero-sum problem, and was soon extended in a number of different directions. F\"{u}redi and Kleitman \cite{FK} proved that a similar result holds for arbitrary (even nonabelian) groups. More precisely, they prove that for every multiplicative group $G$ of order $n$, and every edge-labeling of the complete graph on $n+1$ vertices with elements of $G$, there exists a spanning tree whose edges may be ordered so that the product of the labels (in this order) is the identity. Schrijver and Seymour \cite{SS2} generalized the Bialostocki-Dierker theorem to hypergraphs, thus obtaining a new proof of the F\"{u}redi-Kleitman theorem for abelian groups. %L%Perhaps even more excitingly, Schrijver and Seymour, generalized the Perhaps even more excitingly, Schrijver and Seymour \cite{SS} generalized the underlying geometry further to matroids. If $M$ is a matroid on $E$, and $w : E \rightarrow G$ is a map, we define $w(M) = \{ \sum_{b \in B} w(b) : \mbox{$B$ is a base of $M$}\}$. %L%Schrijver and Seymour \cite{SS} made the following conjecture for %L%general abelian groups. \begin{conjecture}[Schrijver-Seymour] \label{ss_conj} Let $M$ be a matroid on $E$ with rank function $\rk$. Let $w : E \rightarrow G$ where $G$ is an abelian group. If\/ $H = \stab(w(M))$, then \[ |w(M)| \ge |H| \Bigl( 1 - \rk(M) + \sum_{Q \in G/H} \rk(w^{-1}(Q)) \Bigr). \] \end{conjecture} We consider this conjecture to be very important. Indeed, our main theorem is a very special case of it. Corollary \ref{seq_cor} is equivalent to the above conjecture for uniform matroids. Our main theorem is equivalent to the above conjecture for matroids obtained from uniform matroids by adding parallel elements. Schrijver and Seymour \cite{SS} proved their conjecture in the %L%special case when $|G|$ is prime. In this paper, they state ``we special case when $|G|$ is prime. In their paper, they state ``we have convinced ourselves that it is true when $|G|$ is a power of a prime, or the product of two primes. But this last, if it is correct, will appear in a later paper." Unfortunately, this later paper was never written. In the final section of our paper, we prove their conjecture for two special types of groups. %These arguments are closely based on the original method %of Schrijver and Seymour. \begin{theorem} \label{mat_thm} Conjecture \ref{ss_conj} holds whenever $|G| = pq$ for primes $p,q$ or $G \cong {\mathbb Z}_{p^n}$ for a prime $p$ and a positive integer $n$. \end{theorem} %L%In addition to the lower bound for weights of bases, Schrijver and %L%Seymour noted the following. There is a unifying framework for some above-mentioned results. If a matroid $M$ of rank $n$ has two disjoint cocircuits and $w\colon E(M)\to\{0,1\} \subseteq \mathbb Z_n$ is a weighting whose support is one of these cocircuits, then $0 \notin w(M)$. Schrijver and Seymour \cite{SS} (essentially) observe that Conjecture~\ref{ss_conj} implies a converse to this statement. %that a converse statement would follow from Conjecture \ref{ss_conj}. %Also in \cite{SS}, Schrijver and Seymour (essentially) make the following %observation, which serves as a unifying framework for two %earlier-mentioned results. \begin{proposition}[Schrijver-Seymour] \label{prop:SS} %L%Assume that $G$ is a group for which Conjecture \ref{ss_conj} holds. Let $G$ be an abelian group. Let $M$ be a matroid of rank $|G|$ in which every two cocircuits meet. If Conjecture \ref{ss_conj} holds for $G$ and the dual matroid $M^*$, then for any map $w:E(M) \rightarrow G$ we have $0 \in w(M)$. \end{proposition} We have already seen two matroids to which this proposition applies. When $M$ is the uniform matroid with rank $|G|$ on $2|G|-1$ points, we obtain the Erd\H{o}s-Ginzburg-Ziv theorem, since $M^*$ is uniform and satisfies Conjecture \ref{ss_conj} %for any abelian group $G$ by Corollary \ref{seq_cor}. When $M$ is a complete graph on $|G|+1$ vertices and $|G|$ is prime, we obtain the Bialostocki-Dierker theorem, as was observed in \cite{SS}. %%Begin Optional Part%%%% %Both of these results have been superseded, respectively, by %F\"uredi-Kleitman \cite{FK} and Olson \cite{Ol1}. In both cases %they show that for any weighting of $M$ with elements of a (possibly %nonabelian) group $G$ with $|G|=\rk(M)$, there exists a basis whose %weights sum (in some order) to zero. %%End Optional Part%%%% Both of these matroids are minimal in the sense that deleting any element results in a matroid with two disjoint cocircuits. It appears hopeless to characterize such minimal matroids. For example, $M$ is a \emph{dual-paving matroid} if all its cocircuits have size at least $|M|-\rk(M)$. Such matroids are easily constructed by modifying a uniform matroid, and they form a very rich class (it is suspected \cite{Welsh} that most matroids of a given size are paving matroids). When constructing a dual-paving matroid $M$ of size $2\rk(M)$ or $2\rk(M)+1$, it is easy to arrange that $M$ is minimal with respect to not containing disjoint cocircuits. This shows the existence of %Such minimal dual-paving matroids $M$ form a large class of minimal matroids $M$ to which we can apply Theorem~\ref{mat_thm}; if $G$ is a cyclic group and $\rk(M)=|G|$ %has at most two prime divisors, is a prime power or the product of two primes, then $0\in w(M)$ for every $w\colon M\to G$. \begin{figure}[htb] \center{\includegraphics[width=12cm]{dependence6.eps}} % \center{\includegraphics[width=12cm]{dependence6.pdf}} \caption{Implications among statements in in Section 1. New results have bold borders.} \label{fig:dep} \end{figure} \bigskip The remainder of this paper is organized as follows. We prove our main theorem in the next section. We prove three consequences of the main theorem for sequences (Corollaries \ref{easy_cor}, \ref{tricky_cor}, and Theorem \ref{gao_thm}) in Section 3. Then, in the final section, we prove our matroidal result, Theorem \ref{mat_thm}. \section{Main Theorem} The goal of this section is to prove our main theorem. In fact, for the purpose of our induction, we will prove a slightly stronger statement. We continue with some further notation. If $K \le G$ and ${\ell} \in {\mathbb N}$, we call a map $\mu : G/K \rightarrow {\mathbb N}$ a $K$-{\it pattern} of {\it weight} $\ell$ if $\sum_{Q \in G/K} \mu(Q) = {\ell}$. If $\A = (A_1,A_2,\ldots,A_m)$ is a sequence of finite subsets of $G$ and $\mu$ is a $K$-pattern of weight $\ell$, we call a sequence $(b_1, b_2, \ldots, b_{\ell} )$ $\mu$-{\it feasible} (in $\A$) if there exist $1 \le i_1 < i_2 < \cdots < i_{\ell} \le m$ which satisfy the following properties: \begin{itemize} \item $b_j \in A_{i_j}$ for every $1 \le j \le \ell$. \item $\mu(Q) = |\{ j \in \{1,\ldots,{\ell}\} : b_j \in Q \}|$ for every $Q \in G/K$. \end{itemize} Expanding our earlier notation, we now make the following definition. \[ \subsetsum{\mu}(\A) = \{ b_1 + \cdots + b_{\ell} : \mbox{$(b_1,b_2,\ldots,b_{\ell})$ is $\mu$-feasible in $\A$} \}. \] For every ${\ell} \in {\mathbb N}$ and $H \le G$ we define \[ \Theta_H^{\ell}(\A) = \sum_{Q \in G/H} \min \{\ell, | \{ 1 \le i \le m : A_i \cap Q \neq \emptyset \}| \}. \] We are now ready to state our main result in its most general form. \begin{theorem} \label{big_thm} Let $\A = (A_1,\ldots,A_m)$ be a sequence of finite subsets of $G$, let $K \le G$ and let $\mu : G/K \rightarrow {\mathbb N}$ be a $K$-pattern of weight $\ell$. If\/ $\subsetsum{\mu}(\A) \neq \emptyset$ and $\stab(\subsetsum{\mu}(\A)) = J$, then \[ |\subsetsum{\mu}(\A)| \ge |J| ( \Theta_J^{\ell}(\A) - {\ell} + 1 ) - |K| (\Theta_K^{\ell}(\A) - {\ell}). \] \end{theorem} Before we prove Theorem \ref{big_thm}, let us show that it implies our main theorem. To see this, let $\A = (A_1,\ldots,A_m)$ be a sequence of subsets of $G$ and let $\ell$ be a positive integer. Now set $K = G$ and define $\mu : G/K \rightarrow {\mathbb N}$ by the rule $\mu(G) = \ell$. Then $\subsetsum{\ell}(\A) = \subsetsum{\mu}(\A)$ and $\Theta_K^{\ell}(\A) = {\ell}$. Now it is obvious that the bound in Theorem \ref{big_thm} implies Theorem \ref{main_thm}. In particular, Theorem \ref{big_thm} implies Kneser's Theorem. In our proof, we will argue by considering a counterexample which is in some sense minimal, and we will use the fact that our main theorem (and hence Kneser's Theorem) hold for all smaller examples. \bigskip \noindent{\bf Proof:} We shall assume (for a contradiction) that the theorem is false and choose a counterexample $\A = (A_1,\ldots,A_m)$ so that (i) $|\subsetsum{\mu}(\A)|$ is minimum. (ii) $\sum_{i=1}^m |A_i|$ is minimum (subject to (i)). (iii) $\sum_{i=1}^m |A_i|^2$ is maximum (subject to (i),(ii)). (iv) $m$ is minimum (subject to (i), (ii), (iii)). It follows from (iv) that $A_i$ is nonempty for every $1 \le i \le m$. Next we will show that our assumptions imply $J = \{0\}$. It is immediate that $\Sigma^{\mu}(\A)$ is contained in the $K$-coset $\sum_{Q \in G/K} \mu(Q) Q$, so in particular $J \le K$. Suppose (for a contradiction) that $J \neq \{0\}$ and let $\phi : G \rightarrow G/J$ be the canonical homomorphism. Let $\A_{\phi} = (\phi(A_1), \ldots, \phi(A_m))$, let $K_{\phi} = \phi(K)$ and let $\mu_{\phi} : (G/J)/K_{\phi} \rightarrow {\mathbb N}$ be given by the rule $\mu_{\phi}(Q) = \mu( \cup Q )$ for every $Q \in (G/J)/K_{\phi}$. Then $\subsetsum{\mu_{\phi}}(\A_{\phi}) = \phi(\subsetsum{\mu}(\A))$ has trivial stabilizer, so by the minimality of our counterexample we have \begin{eqnarray*} |\subsetsum{\mu}(\A)| & = & |J| \cdot |\subsetsum{\mu_{\phi}}(\A_{\phi})| \\ &\ge& |J| \left( \Theta_{ \{0\} }^{\ell}(\A_{\phi}) - {\ell} + 1 - |K_{\phi}|( \Theta_{K_{\phi}}^{\ell}(\A_{\phi}) - \ell )\right) \\ & = & |J| (\Theta_J^{\ell}(\A) - {\ell} + 1) - |K| ( \Theta_K^{\ell}(\A) - \ell). \end{eqnarray*} This contradiction implies that $J = \{0\}$ as desired. The next step in our proof is to handle one rather special case, when $\ell = m$, and there exists $1 \le j \le m$ so that $|A_j + K| > |K|$. Although the induction we will apply here is different than that used in the general case, the remainder of the argument is similar (but much easier in this special case). The idea is to iteratively build nested subsets of $\subsetsum{\mu}(\A)$ with increasing size and decreasing stabilizers. We will call the subsets produced in this process ``convergents" -- a term borrowed from approximations to continued fractions. Define a set $C \subseteq \subsetsum{\mu}(\A)$ with $H = \stab(C)$ to be a {\it convergent} if it satisfies the following property \[ |C| \ge |H|( \Theta_{H}^{\ell}(\A) - \ell + 1 ) - |K|( \Theta_K^{\ell}(\A) - \ell). \] As in the general argument, we will first show (using an inductive application of our theorem) that a convergent exists. Choose a $\mu$-feasible sequence $(a_1,\ldots,a_m)$ and for every $1 \le i \le m$ let $A_i' = A_i \cap (a_i + K)$. Then set $C_0 = \sum_{i=1}^m A_i'$ and $H_0 = \stab(C_0)$. Note that $|A_j'| < |A_j|$, so we can apply our theorem to the sequence $A_1',A_2',\ldots,A_m'$ to find that $|C_0| \ge \sum_{i=1}^m |A_i' + H_0| - (m-1)|H_0|$. Now we have \begin{eqnarray*} |K| (\Theta_{K}^m(\A) - m ) & = & \sum_{i=1}^m |(A_i \setminus A_i') + K| \\ &\ge& \sum_{i=1}^m |(A_i \setminus A_i') + H_0| \\ & = & |H_0| (\Theta_{H_0}^m(\A) ) - \sum_{i=1}^m |A_i' + H_0|. \end{eqnarray*} Thus, $|C_0| \ge \sum_{i=1}^m |A_i' + H_0| - (m-1)|H_0| \ge |H_0|( 1 - m + \Theta_{H_0}^m(\A) ) - |K|(\Theta_K^m(\A) - m)$. It follows from this that $C_0$ is a convergent, and we may now choose a convergent $C$ with $H = \stab(C)$ minimal. If $H = \{0\}$, then since $\subsetsum{\mu}(\A) \supseteq C$ our proof is complete. Thus, we may assume that $H$ is nontrivial. Since $J = \{0\}$, we may choose a $\mu$-feasible sequence $(b_1,b_2,\ldots,b_m)$ for which $\sum_{i=1}^m b_i + H \not\subseteq \subsetsum{\mu}(\A)$. Let $\nu : G/H \rightarrow {\mathbb N}$ be the $H$-pattern of weight $\ell=m$ given by the rule $\nu(R) = |\{ 1 \le i \le m : b_i + H = R \}|$. Now set $D = \subsetsum{\nu}(\A)$ and $H' = \stab(D)$, and note that $\stab(C \cup D) = H' < H$ since $D$ is properly included in some $H$-coset disjoint from $C$. By the assumption that $C$ is a convergent and an application of our bound to $D = \subsetsum{\nu}(\A)$ we have \begin{eqnarray*} |C \cup D| & = & |C| + |D| \\ & \ge & |H|(\Theta_{H}^{\ell}(\A) - \ell + 1) - |K|(\Theta_K^{\ell}(\A) - \ell ) \\ & & + \, |H'|( \Theta_{H'}^{\ell}(\A) - \ell + 1) - |H|( \Theta_H^{\ell}(\A) - \ell) \\ & > & |H'|( \Theta_{H'}^{\ell}(\A) - \ell + 1 ) - |K|( \Theta_K^{\ell}(\A) - \ell ). \end{eqnarray*} It follows that $C \cup D$ is a convergent with stabilizer $H' < H$ contradicting our choice of $C$. This completes the proof of this special case. For the general argument, we shall arrange (after some adjusting) that our first two sets $A_1$ and $A_2$ satisfy $A_1 \setminus A_2 \neq \emptyset$ and $A_2 \setminus A_1 \neq \emptyset$. Further, we will arrange that the sequence $\Aprime = (A_1 \cap A_2, A_1 \cup A_2, A_3, \ldots, A_m)$ satisfies $\subsetsum{\mu}(\Aprime) \neq \emptyset$. It will then follow from our choice of $\A$ that the theorem applies (nontrivially) to $\Aprime$. This application will be our initial building block (giving us the existence of a convergent). The preparation for this intersection-union operation is slightly different depending on whether $\ell = m$ or $\ell < m$ so we shall consider these two cases separately. First suppose that $\ell < m$. For every $1 \le i \le m$ let $\A^{i} = (A_1,\ldots,A_{i-1},A_{i+1},\ldots,A_m)$. By possibly rearranging our sequence, we may assume that $A_1$ has minimum size over all sets $A_i$ for which $\subsetsum{\mu}(\A^{i}) \neq \emptyset$. If $A_1 \subseteq A_i$ for every $1 \le i \le m$, then $\subsetsum{\mu}(\A) = \subsetsum{\mu}(\A^1)$, $\Theta_K^{\ell}(\A) = \Theta_K^{\ell}(\A^1)$, and $\Theta_{ \{0\} }^{\ell}(\A) = \Theta_{ \{0\} }^{\ell}(\A^1)$ so $\A^1$ contradicts the choice of $\A$ for (ii). Thus, by rearranging (keeping $A_1$ fixed), we may assume that $A_1 \not\subseteq A_2$. If $A_2\subset A_1$, then $\subsetsum{\mu}(\A^2) \supseteq \subsetsum{\mu}(\A^1) \neq \emptyset$ contradicting our choice of $A_1$. Hence, $A_2 \not\subseteq A_1$. Thus, we have $A_1 \setminus A_2 \neq \emptyset$, $A_2 \setminus A_1 \neq \emptyset$, and defining $\Aprime = (A_1 \cap A_2, A_1 \cup A_2,A_3,\ldots,A_m)$, we have $\subsetsum{\mu}(\Aprime) \supseteq \subsetsum{\mu}(\A^1) \neq \emptyset$ as desired. Next suppose that $\ell = m$. Since we have already handled the case when $|A_i + K| > |K|$ for some $1 \le i \le m$ we may further assume that every $A_i$ is included in a $K$-coset. Thus $\subsetsum{\mu}(\A) = \subsetsum{m}(\A) = \sum_{i=1}^m A_i$ and we may assume that $K = G$ since this has no effect on the bound. By possibly rearranging our sets, we may assume that $|A_1| \le |A_2|$. If $A_1 = \{a\}$ for some $a \in G$ then the result follows by applying the theorem to the sequence $(A_2,A_3,\ldots,A_m)$. Otherwise, choose distinct $a,a' \in A_1$. Note that $\stab(A_2) \subseteq \stab(\subsetsum{m}(\A)) = \{0\}$. Therefore, $a'-a \notin \stab(A_2)$, so there exists $b \in A_2$ so that $b+a'-a \not\in A_2$. Now replace $A_2$ by $A_2 - b + a$ (and use the notation $A_2$ for this shifted set henceforth). This has the effect of shifting $\subsetsum{m}(\A)$, but does not affect the size of this set or its stabilizer. By construction, $a \in A_1 \cap A_2$, $a' \in A_1 \setminus A_2$, and $A_2 \setminus A_1 \neq \emptyset$ (this last fact follows from the second and $|A_1| \le |A_2|$). Now setting $\Aprime = (A_1 \cap A_2, A_1 \cup A_2,A_3,\ldots,A_m)$ we have $\subsetsum{\mu}(\Aprime) \neq \emptyset$ as desired. Let us observe that in both cases, the new sequence $\A'$ satisfies $\emptyset \neq \subsetsum{\mu}(\A') \subseteq \subsetsum{\mu}(\A)$. Further, since $A_1 \setminus A_2 \neq \emptyset$ and $A_2 \setminus A_1 \neq \emptyset$ our theorem applies to $\A'$ by minimality assumption (i) or (iii). Now we will {\it redefine} our notion of convergent. We define a set $C$ to be a {\it convergent} if $\subsetsum{\mu}(\Aprime) \subseteq C \subseteq \subsetsum{\mu}(\A)$ and if setting $H = \stab(C)$ we have \[ |C| \ge |H|(\Theta_{H}^{\ell}(\Aprime) - \ell + 1) - |K|(\Theta_{K}^{\ell}(\A) - \ell). \] Next we will show that $C_0 = \subsetsum{\mu}(\Aprime) \neq \emptyset$ is a convergent. To see this, let $H_0 = \stab(C_0)$ and apply the theorem inductively to $\Aprime$ to get the following: \begin{eqnarray*} |C_0| &\ge& |H_0|(\Theta_{H_0}^{\ell}(\Aprime) - \ell + 1) - |K|(\Theta_{K}^{\ell}(\Aprime) - \ell) \\ &\ge& |H_0|(\Theta_{H_0}^{\ell}(\Aprime) - \ell + 1) - |K|(\Theta_{K}^{\ell}(\A) - \ell). \end{eqnarray*} Thus, $C_0$ is a convergent, and we may now choose a convergent $C$ with stabilizer $H$ so that $H$ is minimal. If $H = \{0\}$, then we have \begin{eqnarray*} |\subsetsum{\mu}(\A)| &\ge& |C| \\ &\ge& \Theta_{ \{0\} }^{\ell}(\Aprime) - \ell + 1 - |K|(\Theta_K(\A) - \ell) \\ & = & \Theta_{ \{0\} }^{\ell}(\A) - \ell + 1 - |K|(\Theta_K(\A) - \ell). \end{eqnarray*} This contradiction implies that $H \neq \{0\}$. Our plan is to construct three new sets $C^1$, $C^2$, and $C^{12}$, each of which will be a superset of $C$ with stabilizer $\le H$. We will then derive a contradiction under the assumption that none of them is a convergent with strictly smaller stabilizer than $C$. Since $\subsetsum{\mu}(\A)$ has trivial stabilizer and $\stab(C) = H \neq \{0\}$ we may choose a $\mu$-feasible sequence $(b_1,b_2,\ldots,b_{\ell})$ so that $R = \sum_{j=1}^{\ell} b_j + H \not\subseteq \subsetsum{\mu}(\A)$. Note that $R \cap C = \emptyset$. Further, it follows from $\subsetsum{\mu}(\Aprime) \subseteq C$ that $b_1 \in A_1$ and $b_2 \in A_2$. Let $\nu : G/H \rightarrow {\mathbb N}$ be the $H$-pattern of weight $\ell$ given by the rule $\nu(Q) = | \{ j \in \{1,\ldots,\ell\} : b_j + H = Q\}|$ and note that $\subsetsum{\nu}(\A) \subseteq R$. Next, let $\A^* = (A_3,A_4,\ldots,A_m)$ and let $\nu^*$ be the $H$-pattern of weight $\ell-2$ given by the rule $\nu^*(Q) = |\{ j \in \{3,\ldots,\ell\} : b_j + H = Q\}|$. Then, for $\delta=1,2$, set $A_1^{\delta} = A_1 \cap (b_{\delta} + H)$ and set $A_2^{\delta} = A_2 \cap (b_{3-{\delta}} + H)$ (here the reader should note a deliberate ``crossing" of our indices). Note further that $b_1 \in A_1^1$ and $b_2 \in A_2^1$ so $A_1^1 \neq \emptyset \neq A_2^1$. Then set $B^1 = A_1^1 + A_2^1$, set $B^2 = A_1^2 + A_2^2$ and set $B^{12} = B^1 \cup B^2$. Next we give a few definitions, culminating with $C^1$, $C^2$, and $C^{12}$. \[ D^{12} = B^{12} + \subsetsum{\nu^*}(\A^*), \qquad H^{12} = \stab(D^{12}). \] Now for $\delta=1,2$ we define the set $D^{\delta}$ and name its stabilizer as follows. \[ D^{\delta} = B^{\delta} + \subsetsum{\nu^*}(\A^*) + H^{12}, \qquad H^{\delta} = \stab(D^{\delta}). \] Finally, for $\epsilon = 1,2,12$ we define the set $C^{\epsilon}$ as follows (for clarity, we will continue to let $\delta$ be a variable ranging over $1,2$ and let $\epsilon$ range over $1,2,12$) \[ C^{\epsilon} = C \cup D^{\epsilon}. \] Let us make a few simple observations concerning these newly defined sets. First, note that by construction, $D^1 \neq \emptyset$ and $D^{12} \neq \emptyset$. Further, $D^{\epsilon} \subseteq \subsetsum{\nu}(\A) \subset R$ for every $\epsilon =1,2,12$ so each of these sets is disjoint from $C$. Since each $D^{\epsilon}$ is a proper subset of the $H$-coset $R$, it follows that $\stab(C^{\epsilon}) = H^{\epsilon}$ whenever $D^{\epsilon} \neq \emptyset$. %L% Figure @@ shows the relationships between some of these sets and their stabilizers. Figure \ref{fig:conv} shows the containment relationships among the sets $C^{\epsilon}$ and their stabilizers $H^\epsilon$. \begin{figure}[htb] % \epsfxsize=11.5truecm %optional \center{\includegraphics[width=6.0cm]{convergents6.eps}} % \center{\includegraphics[width=6.0cm]{convergents6.pdf}} \caption{Containment relations among the sets $C^\epsilon$ and their stabilizers.} \label{fig:conv} \end{figure} Let us pause to note that by (i) of our choice of $\A$, and the observation that $|\subsetsum{\mu}(\A)| > |C| \ge |H|$, it follows that our theorem holds true (and Kneser's theorem holds) whenever the associated sumset is contained in some $H$-coset. This fact will be used repeatedly in the remainder of the argument. Next we shall make two claims which hold for $\epsilon = 1,12$ and also hold for $\epsilon = 2$ if $D^2 \neq \emptyset$. Both of these claims will help us to simplify the equations which result from inductive applications of our theorem. \bigskip \noindent{\sl Claim 1:} $|\Sigma^{\nu^*}(\A^*) + H^{\epsilon}| \ge |H^{\epsilon}|( \Theta_{H^{\epsilon}}^{\ell - 2}(\A^*) - \ell + 3) - |H|( \Theta_H^{\ell - 2}(\A^*) - \ell + 2 )$. \bigskip \noindent{\sl Proof of Claim:} Set ${\bf B} = (A_3 + H^{\epsilon}, A_4 + H^{\epsilon}, \ldots, A_m + H^{\epsilon})$ and note that $\Sigma^{\nu^*}({\bf B}) = \Sigma^{\nu^*}(\A^*) + H^{\epsilon}$. Further, it follows from the definition of $D^{\epsilon}$ and $H^{\epsilon}$ that $\stab(\Sigma^{\nu^*}({\bf B})) = H^{\epsilon}$. Thus, by applying our theorem inductively to $\Sigma^{\nu^*}({\bf B})$ we have \begin{eqnarray*} |\Sigma^{\nu^*}(\A^*) + H^{\epsilon}| & = & |\Sigma^{\nu^*}({\bf B})| \\ &\ge& |H^{\epsilon}|( \Theta_{H^{\epsilon}}^{\ell - 2}({\bf B}) - \ell + 3) - |H|( \Theta_H^{\ell - 2}({\bf B}) - \ell + 2 ) \\ & = & |H^{\epsilon}|( \Theta_{H^{\epsilon}}^{\ell - 2}(\A^*) - \ell + 3) - |H|( \Theta_H^{\ell - 2}(\A^*) - \ell + 2 ) \end{eqnarray*} as desired. \bigskip For $\epsilon = 1,2,12$ we define $X^{\epsilon}$ and $Y^{\epsilon}$ as follows: \begin{eqnarray*} X^{\epsilon} & = & (b_1 + H) \setminus ((A_1^1 \cup A_2^2) + H^{\epsilon}), \\ Y^{\epsilon} & = & (b_2 + H) \setminus ((A_1^2 \cup A_2^1) + H^{\epsilon}). \end{eqnarray*} \noindent{\sl Claim 2:} $ |H|(\Theta_H^{\ell}(\Aprime) - \Theta_H^{\ell-2}(\A^*)) - |H^{\epsilon}|(\Theta_{H^{\epsilon}}^{\ell}(\Aprime) - \Theta_{H^{\epsilon}}^{\ell-2}(\A^*)) \ge |X^{\epsilon} \cup Y^{\epsilon}|. $ \bigskip \noindent{\it Proof of Claim:} First observe that contribution of an $H$-coset $Q$ to $|H| (\Theta_H^{\ell}(\Aprime) - \Theta_H^{\ell-2}(\A^*))$ (which must be either $0$, $|H|$, or $2|H|$) is always at least the contribution of the $H^{\epsilon}$-cosets contained in $Q$ to $|H^{\epsilon}|(\Theta_{H^{\epsilon}}^{\ell}(\Aprime) - \Theta_{H^{\epsilon}}^{\ell-2}(\A^*))$. Next, consider the coset $b_1 + H$. If this coset has nontrivial intersection with $A_1 \cap A_2$ or has nontrivial intersection with $> \ell-2$ members of $\A^*$, then $\subsetsum{\nu}(\Aprime) \neq \emptyset$. However, this contradicts the assumption that $\subsetsum{\nu}(\A) \subseteq R$ is disjoint from $C$ since $\subsetsum{\nu}(\A) \supseteq \subsetsum{\nu}(\Aprime) \subseteq \subsetsum{\mu}(\Aprime) \subseteq C$. It follows that the contribution of $b_1 + H$ to $|H| (\Theta_H^{\ell}(\Aprime) - \Theta_H^{\ell-2}(\A^*))$ is exactly $|H|$. By a similar argument, the contribution of the $H^{\epsilon}$-cosets contained in $b_1 + H$ to $|H^{\epsilon}|(\Theta_{H^{\epsilon}}^{\ell}(\Aprime) - \Theta_{H^{\epsilon}}^{\ell-2}(\A^*))$ is exactly $|(A_1^1 \cup A_2^2) + H^{\epsilon}|$. Thus, the contribution of $b_1 + H$ and its $H^{\epsilon}$-cosets to the left hand side of the equation in the claim is $|X^{\epsilon}|$. Similarly, the coset $b_2 + H$ contributes $|Y^{\epsilon}|$. Whether or not $b_1 + H = b_2 + H$, our claim follows immediately. \bigskip The next equation holds for $\epsilon =1,12$ and for $\epsilon = 2$ if $D^2 \neq \emptyset$. It follows from the assumption that $C$ is a convergent, but $C^{\epsilon}$ is not. \begin{eqnarray} \label{eq1} |D^{\epsilon}| & = & |C^{\epsilon}| - |C| \nonumber \\ & < & |H^{\epsilon}|(\Theta_{H^{\epsilon}}^{\ell}(\Aprime) - \ell + 1) - |H|(\Theta_H^{\ell}(\Aprime) - \ell + 1) \end{eqnarray} On the other hand, $D^{\epsilon}$ is defined by a sumset to which we may apply our theorem inductively. In the following equation, we have repeatedly applied our theorem inductively in the form of Kneser's theorem, and we have also applied Claim 1. This equation holds for $\epsilon = 1,12$ and also holds for $\epsilon = 2$ if $D^2 \neq \emptyset$. \begin{eqnarray} \label{eq2} |D^{\epsilon}| & = & |B^{\epsilon} + \subsetsum{\nu^*}(\A^*) + H^{\epsilon} | \nonumber \\ &\ge& |B^{\epsilon} + H^{\epsilon}| + |\subsetsum{\nu^*}(\A^*) + H^{\epsilon}| - |H^{\epsilon}| \nonumber \\ &\ge& |B^{\epsilon} + H^{\epsilon}| + |H^{\epsilon}| (\Theta_{H^{\epsilon}}^{\ell-2}(\A^*) - \ell + 2) - |H|(\Theta_H^{\ell-2}(\A^*) - \ell + 2) \end{eqnarray} Combining equations \ref{eq1} and \ref{eq2} and applying Claim 2 gives us the following equation which holds for $\epsilon = 1,12$ and also holds for $\epsilon = 2$ if $D^2 \neq \emptyset$. \begin{equation} \label{eq3} |H| > |B^{\epsilon} + H^{\epsilon}| + |X^{\epsilon} \cup Y^{\epsilon}| + |H^{\epsilon}| \end{equation} Using equation (\ref{eq3}) and an inductive application of our theorem (again in the form of Kneser's theorem) gives us the following equation which holds for $\delta = 1$ and holds for $\delta = 2$ if $D^2 \neq \emptyset$. \[ |H| > |A_1^{\delta} + H^{\delta}| + |A_2^{\delta} + H^{\delta}| + |X^{\delta} \cup Y^{\delta}|. \] Consider the above equation with $\delta = 1$. If $A_2^2 = \emptyset$, then $|X^1| = |H| - |A_1^1 + H^1|$ and we have a contradiction. Thus $A_2^2 \neq \emptyset$. We get a similar contradiction (by considering $Y^1$) under the assumption that $A_2^1 = \emptyset$. It follows that $D^2 \neq \emptyset$, so equations (\ref{eq1}), (\ref{eq2}), and (\ref{eq3}) hold for $\epsilon = 2$, and the above equation holds for $\delta = 2$. If $b_1 + H = b_2 + H$, then $A_2^1 = A_2^2$ so $|X^1| = |(b_1 + H) \setminus ((A_1^1 \cup A_2^1) + H^1)| \ge |H| - |A_1^1 + H^1| - |A_2^1 + H^1|$, but again this contradicts the above equation for $\delta = 1$. Thus $b_1 + H \neq b_2 + H$, and we have that $X^{\epsilon}$ and $Y^{\epsilon}$ are disjoint for $\epsilon =1,2,12$. Our next equation follows from the previous equation, and the observation that $|H|$, $|A_1^{\delta} + H^{\delta}|$, and $|A_2^{\delta} + H^{\delta}|$ are all multiples of $|H^{\delta}|$. It holds for $\delta=1,2$: \begin{eqnarray} \label{eq4} |H| &\ge& |A_1^{\delta} + H^{\delta}| + |A_2^{\delta} + H^{\delta}| + |H^{\delta}| \nonumber \\ &\ge& |A_1^{\delta} + H^{12}| + |A_2^{\delta} + H^{12}| + |H^{\delta}| \end{eqnarray} The next equation follows from equation (\ref{eq3}) for $\epsilon = 12$ and another application of Kneser's theorem. Here the application of Kneser's theorem requires the observation that the stabilizer of the sumset $(A_1^{\delta} + H^{12}) + (A_2^{\delta} + H^{12}) = B^{\delta} + H^{12}$ is a subgroup of $H^{\delta}$ - a fact which follows from the definition of $D^{\delta}$. \begin{eqnarray} \label{eq5} |H| &\ge& |B^{12} + H^{12}| + |X^{12} \cup Y^{12}| \nonumber \\ &\ge& |B^{\delta} + H^{12}| + |X^{12}| + |Y^{12}| \nonumber \\ &\ge& |A_1^{\delta} + H^{12}| + |A_2^{\delta} + H^{12}| - |H^{\delta}| + |X^{12}| + |Y^{12}| \end{eqnarray} Summing the four inequalities obtained by taking equations \ref{eq4} and \ref{eq5} for $\delta = 1,2$ and then dividing by two yields \[ 2|H| > |A_1^1 + H^{12}| + |A_1^2 + H^{12}| + |A_2^1 + H^{12}| + |A_2^2 + H^{12}| + |X^{12}| + |Y^{12}|. \] However, $b_1 + H = X^{12} \cup (A_1^1 + H^{12}) \cup (A_2^2 + H^{12})$ and $b_2 + H = Y^{12} \cup (A_1^2 + H^{12}) \cup (A_2^1 + H^{12})$. This yields the final contradiction and completes the proof. \quad\quad$\Box$ \section{Corollaries} %L%The goal for this section we use our main corollary for In this section use our main corollary for subsequence sums (Corollary \ref{seq_cor}) to derive Corollaries \ref{easy_cor} and \ref{tricky_cor}, and to give a new proof of Gao's Theorem (\ref{gao_thm}). %L%Before proceeding, we require one added bit of notation. We use the following notation. If $\a = (a_1,\ldots,a_m)$ is a sequence of elements from $G$ and $S \subseteq G$, we let $\rho_S(\a) = |\{ 1 \le i \le m : a_i \in S \}|$. Similarly, if $g \in G$ we define $\rho_g(\a) = \rho_{ \{g\} }(\a)$. The function $\rho$ defined in the introduction (the maximum multiplicity of an element) is then $\rho(\a) = \max_{g \in G} \rho_g(\a)$. For convenience we have restated Corollary \ref{seq_cor} below with this new notation. \bigskip \noindent{\bf Corollary \ref{seq_cor}} {\it If $\a = (a_1,\ldots,a_m)$ is a sequence of elements of\/ $G$ and $H = \stab(\subsetsum{\ell}(\a))$, then \[ |\subsetsum{\ell}(\a)| \ge |H| \Bigl(1 - \ell + \sum_{Q \in G/H} \min \big\{\ell, \rho_Q(\a) \big\} \Bigr). \] } \bigskip \noindent{\it Proof of Corollary \ref{easy_cor}}: Recall that the sets $\subsetsum{\ell}(\a)$ and $\subsetsum{m-\ell}(\a)$ have the same size and the same stabilizer (one is just a shift of the (additive) inverse of the other), so we may apply Corollary \ref{seq_cor} both for $\subsetsum{\ell}(\a)$ and $\subsetsum{m-\ell}(\a)$. Let $H = \stab(\subsetsum{\ell}(\a)) = \stab(\subsetsum{m-\ell}(\a))$. If $H = \{0\}$, then applying Corollary \ref{seq_cor} to $\subsetsum{m-\ell}(\a)$ shows that $|\subsetsum{\ell}(\a)| = |\subsetsum{m-\ell}(\a)| \ge \ell + 1$ (since $\rho(\a) \le m - \ell$), so (i) holds. Otherwise, applying this bound to $\subsetsum{\ell}(\a)$ shows that either (ii) holds, or $|\subsetsum{\ell}(\a)| \ge |H| (1 + m - \ell) \ge |H| \cdot \ell/p \ge \ell$ which implies (i). \quad\quad$\Box$ \bigskip \noindent{\it Proof of Corollary \ref{tricky_cor}:} We shall assume that neither (i) nor (ii) holds and derive a contradiction. Set $h = |H|$ and set $t = |\{ Q \in G/H : \rho_Q(\a) \ge m - \ell \}|$. If $t = 0$, then Corollary \ref{seq_cor} (applied with $m-\ell$ in place of $\ell$) shows that $|\subsetsum{\ell}(\a)| = |\subsetsum{m-\ell}(\a)| \ge h(1 - (m-\ell) + m) = h(1 + \ell)$, so (i) holds. Thus $t \ge 1$. Suppose that $H = \{0\}$. If $t = 1$, then let $g_0 \in G$ be the unique element with $\rho_{g_0}(\a) \ge m - \ell$, and note that since $\rho_{g_0}(\a) \le \ell -k + 2$, we must have $\sum_{g \in G} \min \{ m - \ell, \rho_g(\a) \} = m - (\rho_{g_0}(\a) - (m - \ell)) \ge 2m - 2 \ell + k - 2$. If $t \ge 2$, then since $\a$ contains at least $k$ distinct terms, we have $\sum_{g \in G} \min\{ m - \ell, \rho_g(\a) \} \ge t(m-\ell) + k-t = t(m-\ell-1) + k \ge 2m - 2 \ell + k - 2$. Since this inequality holds for all possible values of $t$, Corollary \ref{seq_cor} shows that $|\subsetsum{m-\ell}(\a)| \ge 1 - (m-\ell) + (2m - 2\ell + k - 2) = m-\ell + k -1$ and conclusion (i) holds. Thus $H \neq \{0\}$, i.e., $h > 1$. Assuming that (i) and (ii) do not hold, Corollary \ref{seq_cor} gives \begin{eqnarray*} m-\ell + k & > & |\subsetsum{\ell}(\a)| \\ &\ge& |H| \Bigl( 1 - \ell + \sum_{Q \in G/H} \rho_Q(\a) \Bigr) \\ & = & h(m-\ell + 1) \end{eqnarray*} so we have \begin{equation} \label{ml} k - h > (h-1)(m- \ell). \end{equation} Note that this implies in particular that $k \ge h + 2$. Since $t \ge 1$, we may choose $R \in G/H$ so that $\rho_R(\a) \ge m - \ell$. Then our bound gives \begin{eqnarray} \label{t1} |\subsetsum{m-\ell}(\a)| &\ge& h \Bigl(1 - m + \ell + \sum_{Q \in G/H} \min\{ m-\ell, \rho_Q(\a) \} \Bigr) \nonumber \\ & = & h \Bigl( 1 + \sum_{Q \in (G/H) \setminus \{R\}} \min\{ m-\ell, \rho_Q(\a) \} \Bigr). \end{eqnarray} First suppose that $m - \ell \ge h$. Then the $\Sigma$-term in the right hand side of equation (\ref{t1}) must be at least the number of distinct elements in $G \setminus R$ which appear at least once in $\a$. Thus, in this case we have $|\subsetsum{m-\ell}(\a)| \ge h(1+k-|R|) = h(1+k-h)$. Combining this with Equation (\ref{ml}) and the assumption that (i) does not hold we have \begin{eqnarray*} (k-h)/(h-1) & > & m - \ell \\ & > & |\subsetsum{\ell}(\a)| - k \\ & = & |\subsetsum{m-\ell}(\a)| - k \\ &\ge& h(1 + k - h) - k \\ & = & (k-h)(h-1). \end{eqnarray*} However, this is contradictory since $k \ge h + 2$ and $h \ge 2$. Thus we may now assume $m - \ell < h$. Again let us consider the $\Sigma$-term in the right hand side of equation (\ref{t1}). There are at least $k-|R| = k-h$ distinct elements in $G \setminus R$ which appear in $\a$. If $Q \in G/H \setminus \{R\}$ contains $s$ distinct elements of $G$ which appear in $\a$, then the contribution of this coset to the $\Sigma$-term will be at least $\min \{ s, m - \ell \} \ge \frac{m-\ell}{h} s $. Thus, the $\Sigma$-term in the right hand side of (\ref{t1}) is at least $\frac{m-\ell}{h}(k-h)$. Combining this with the assumption that (i) does not hold we have \begin{eqnarray*} (m - \ell) + (k - h) & > & |\subsetsum{m-\ell}(\a)| - h \\ &\ge& (k-h)(m-\ell). \end{eqnarray*} Since we have already observed that $k \ge h + 2$, the above equation implies that $m = \ell + 1$ (recall that $m> \ell$ by assumption). But then $|\subsetsum{1}(\a)| \ge k$ since $\a$ contains $k$ distinct terms, so we find $|\subsetsum{\ell}(\a)| = |\subsetsum{1}(\a)| \ge k = m - \ell + k - 1$ and conclusion (i) holds. This completes the proof. \quad\quad$\Box$ \bigskip \noindent{\it Proof of Theorem \ref{gao_thm}:} To see that $s'(G) \ge s(G) + |G| - 1$, choose a sequence $\a$ of length $s(G) - 1$ without a nontrivial subsequence which sums to $0$ and append $|G|-1$ copies of $0$ to $\a$. This new sequence demonstrates $s'(G) \ge s(G) + |G| - 1$. Next we shall prove $s'(G) \le s(G) + |G| - 1$ by induction on $|G|$. Let $m = s(G) + |G| - 1$ and let $\a = (a_1,a_2,\ldots,a_m)$ be a sequence of elements from $G$. We need to show that $0 \in \subsetsum{|G|}(\a)$. Set $H = \stab(\subsetsum{|G|}(\a) )$. If $H \neq \{0\}$, then let $\phi : G \rightarrow G/H$ be the canonical homomorphism and consider the sequence $\a_{\phi} = ( \phi(a_1), \phi(a_2), \ldots, \phi(a_m) )$. Since $s(G/H) \le s(G)$, we may apply our theorem inductively to get a subsequence of length $[G:H]$ and sum zero in $G/H$. After removing this subsequence from $\a_{\phi}$, we apply the theorem again to get another such sequence. After $|H|$ repetitions, we have $|H|$ disjoint subsequences of $\a_{\phi}$ each with length $[G:H]$ and sum equal to zero in $G/H$. Combining the corresponding subsequences of $\a$ gives a subsequence of length $|G|$ whose sum is in $H$. Since $H = \stab(\subsetsum{|G|}(\a))$, it follows that $0 \in \subsetsum{|G|}(\a)$. Thus, we may assume that $H = \{0\}$. If $\rho(\a) < s(G)$, then by Corollary \ref{seq_cor} we have \[ |\subsetsum{s(G)-1}(\a)| \ge 2 - s(G) + \sum_{g \in G} \min\{ s(G)-1, \rho_g(\a) \} \ge |G| + 1 \] which is contradictory. It follows that there exists $g \in G$ so that $\rho_g(\a) \ge s(G)$. By replacing $\a$ by $(a_1 - g, a_2 - g, \ldots, a_m - g)$ we do not affect the set $\subsetsum{|G|}(\a)$ but may now assume that $\rho_0(\a) \ge s(G)$. By rearranging our sequence, we may further assume that $a_{|G| + 1}, a_{|G| + 2}, \ldots a_{|G| + s(G) - 1}$ are all 0. Now, by the definition of the Davenport constant $s(G)$, we may repeatedly choose disjoint subsequences of $(a_1,a_2,\ldots,a_{|G|})$ each of which has zero sum, so that the number of leftover elements is at most $s(G) - 1$. By concatenating these sequences, and then adding an appropriate number of zero terms $a_i$ with $i > |G|$, we obtain a subsequence of length $|G|$ with zero sum, as required. \quad\quad$\Box$ \section{Matroids} The goal of this section is to prove Theorem \ref{mat_thm}. %L%two special cases of Conjecture \ref{ss_conj}. Fix an abelian group $G$, a matroid $M$ on $E$ with rank function $\rk$, and let ${\mathcal B}(M)$ denote the set of bases of $M$. Departing from the original treatment of Schrijver and Seymour, we let $W$ be a weight function which assigns to each element $e \in E$ a nonempty set $W(e) \subseteq G$. For every $S \subseteq G$ let $E_S = \{ e \in E : S \cap W(e) \neq \emptyset \}$ %L%and if $g \in G$ let $E_g = E_{ \{g\} }$. and abbreviate $E_g = E_{ \{g\} }$. %L%Now we set We define \[ W(M) = \bigcup_{B \in {\mathcal B}(M)} \sum_{b \in B} W(b). \] With this notation we restate Theorem \ref{mat_thm}. \begin{theorem} Let $p,q$ be primes and assume that $G \cong {\mathbb Z}_{p^n}$ or $G \cong {\mathbb Z}_p \times {\mathbb Z}_q$. If $H = \stab(W(M))$, then \[ |W(M)| \ge |H| \Bigl( 1 - \rk(M) + \sum_{Q \in G/H} \rk (E_Q) \Bigr). \] \end{theorem} \noindent{\it Proof:} We proceed by induction on $|E|$. We may assume that $M$ has no loops %L%(as deleting them has no effect) or parallel elements (if $e,f \in E$ are parallel, %L%then the result follows by replacing $W(e)$ by $W(e) \cup W(f)$, deleting $f$, and then applying induction). then replace $W(e)$ by $W(e) \cup W(f)$, delete $f$ and apply induction). If $\rk(M) = 1$, then the result is trivial, so we may further assume that $\rk(M) \ge 2$. For every $e \in E$, we define the subgroup \[ H_e = \stab(W(e)). \] By possibly replacing $W(e)$ with a superset, we may assume that for every $e \in E$ and every $g \in G \setminus W(e)$, the weight function $W'$ obtained from $W$ by the adjustment $W'(e) = W(e) \cup \{g\}$ satisfies $W'(M) \neq W(M)$. The inequality below follows from this maximality assumption. \begin{equation} \label{max-stab} \mbox{$H \le H_e$ for every $e \in E$}. \end{equation} If $g \in G$ and $E_g$ spans $e$, then replacing $W(e)$ by $W(e) \cup \{g\}$ does not change the set $W(M)$. To see this %let $h$ be a group element in the set $g + \sum_{b\in B-e}W(b)$ let $h \in g + \sum_{b\in B-e}W(b)$ where $B$ is a basis containing $e$. Then $B-e+f$ is a basis for some $f\in E_g\backslash B$, whence $h \in \sum_{b\in B-e+f} W(b)$. %L%since any group element formed by taking weight $g$ from %L%$W(e)$ under a basis $B \in {\mathcal B}(M)$ can also be produced by %L%replacing $e$ with another element $f\notin B$ whose set $W(f)$ %L%contained $g$ (for the basis $B-e+f$). By repeating this process, we may assume that $W(e) = \{ g \in G : E_g \mbox{ spans } e\}$ for every $e \in E$. Equivalently (in light of equation (\ref{max-stab})), we have \begin{equation} \label{coset-span} W(e) = \cup\{ Q \in G/H : \mbox{$E_Q$ spans $e$}\} \end{equation} Let $M/e$ denote the matroid obtained from $M$ by contracting $e$ and consider the set $W(e) + W(M/e)$. By construction, this is a subset of $W(M)$ and has stabilizer $\ge H_e = \stab(W(e))$. However, the maximality of $W(e)$ further implies that \begin{equation} \label{cont-stab} H_e = \stab( W(e)+W(M/e) ). \end{equation} Suppose now that $G \cong {\mathbb Z}_p \times {\mathbb Z}_q$. If there exist $e,f \in E$ with $H_e$ and $H_f$ being distinct nontrivial subgroups, then we may choose a base $B$ containing $e$ and $f$, and we find that $\stab\left(\sum_{b \in B}W(b)\right) \ge H_e + H_f = G$ so $W(M) = G$, and we have $H = G$ which contradicts either $H \le H_e$ or $H \le H_f$. It follows from this argument that the subgroups $\{ H_e : e \in E \}$ are nested when $G \cong {\mathbb Z}_p \times {\mathbb Z}_q$. Since any two subgroups of ${\mathbb Z})_{p^n}$ are nested, the same conclusion also holds for this case. Thus, we may choose $f \in E$ so that $H_f \le H_e$ for every $e \in E$. It follows immediately from this that $H_f \le \stab(W(M)) = H$, and $H_f \le \stab(W(M/f))$. The first of these inequalities and (\ref{max-stab}) imply that $H_f = H$. It follows from the second and equation (\ref{cont-stab}) that $\stab(W(M/f)) = H_f = H$. So, all three sets $W(M)$, $W(M/f)$, and $W(f) + W(M/f)$ have stabilizer $H$. Now, applying Kneser's Theorem (Theorem \ref{kn_thm}), equation (\ref{coset-span}), and the induction hypothesis, we have: \begin{eqnarray*} |W(M)| &\ge& |W(f) + W(M/f)| \\ &\ge& |W(f)| + |W(M/f)| - |H| \\ &\ge& |H| \Bigl( |\{ Q \in G/H : \mbox{ $E_Q$ spans $f$ } \}| + 1 - \rk(M/f) + \sum_{Q \in G/H} \rk_{M/f}(E_Q) \Bigr) - |H| \\ & = & |H| \Bigl( 1 - \rk(M) + \sum_{Q \in G/H} \rk_M(E_Q) \Bigr) \end{eqnarray*} which completes the proof. \quad\quad$\Box$ \begin{thebibliography}{10} \bibitem{BD2} A. Bialostocki, P. Dierker, Zero sum Ramsey theorems, Congr. Numer. 70 (1990), 119--130. \bibitem{BD} A. Bialostocki, P. Dierker, On the Erd\H{o}s-Ginzburg-Ziv Theorem and the Ramsey numbers for stars and matchings, Discrete Math. 110 (1992), 1--8. \bibitem{BL} B. Bollob\'{a}s, I. Leader, The number of $k$-sums modulo $k$, J. Number Theory 78 (1999), 27--35. \bibitem{Ca} H. Q. Cao, An addition theorem on the cyclic group ${\mathbb Z}_{p^{\alpha}q^{\beta}}$, The Electronic J. of Combinatorics 13 (2006), N9. \bibitem{Cau} A. L. Cauchy, Recherches sur les nombres, J. \'{E}cole polytech.\ 9 (1813), 99--116. \bibitem{Dav} H. Davenport, On the addition of residue classes, J. London Math.\ Soc. 10 (1935), 30--32. \bibitem{EGZ} P. Erd\H{o}s, A. Ginzburg, A. Ziv, Theorem in the additive number theory, Bull.\ Res.\ Coucil 10F (1961), 41--43. \bibitem{FK} Z. F\"uredi, D. J. Kleitman, On zero-trees. J.~Graph Theory 16 (1992), 107--120. \bibitem{Ga} W. Gao, A combinatorial problem on finite abelian groups, J. Number Theory 58 (1996), 100--103. \bibitem{Ga2} W. D. Gao, Three addition Theorems on ${\mathbb Z}_n$, preprint. \bibitem{GTZ} W. D. Gao, R. Thangadurai, J. Zhuang, Addition Theorems on the cyclic groups ${\mathbb Z}_{p^n}$, preprint. \bibitem{Gr1} D. Grynkiewicz, On a partition analog of the Cauchy-Davenport Theorem, Acta Math.\ Hungar.\ 107 (2005), 167--181. \bibitem{Gr2} D. Grynkiewicz, On a conjecture of Hamidoune for subsequence sums, Integers: Electr.\ J.\ Comb.\ Number Theory 5 (2) (2005) A07. %\bibitem{Ha1} Y. O. Hamidoune, %On weighted sums in abelian groups, %Discrete Math.\ 162 (1996), 127--132. \bibitem{Ha2} Y. O. Hamidoune, Subsequence sums, Combin.\ Probab.\ Comput.~12 (2003), 413--425. \bibitem{HOO} Y. O. Hamidoune, O. Ordaz, A. Ortu\~{n}o, On a combinatorial theorem of Erd\H{o}s, Ginzburg, and Ziv, Combin.\ Probab.\ Comput.~7 (1998), 403--412. %\bibitem{Ke} J. H. B. Kempermann, %On small sumsets in an abelian group, %Acta Math.~103 (1960), 63--88. \bibitem{Kn} M. Kneser, Absch\"{a}tzung der asymptotischen Dichte von Summenmengen, Math.\ Z. 58 (1953), 459--484. \bibitem{Na} M. B. Nathanson, {\it Additive Number Theory. Inverse Problems and the Geometry of Sumsets}, Graduate Texts in Mathematics 165, Springer-Verlag, New York, 1996. %\bibitem{Ol1} J. E. Olson, %On a combinatorial problem of Erd\H{o}s, Ginzburg, and Ziv, %J. Number Theory 8 (1976), 52--57. %\bibitem{Ol2} J. E. Olson, %An addition theorem for finite abelian groups, %J. Number Theory 9 (1977), 63--70. \bibitem{SS} A. Schrijver, P. D. Seymour, Spanning trees of different weights, DIMACS Series in Discrete Math.\ and Theoret.\ Comp.\ Sci., Vol 1 (1990), 281--288. \bibitem{SS2} A. Schrijver, P. D. Seymour, A simpler proof and a generalization of the zero-trees theorem, J. Combin. Theory Ser. A 58 (1991), 301--305. \bibitem{Welsh} D. J. A. Welsh, Matroid theory, Academic Press [Harcourt Brace Jovanovich Publishers], London, 1976. L. M. S. Monographs, No. 8. \end{thebibliography} \end{document}