Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 248.20068
Autor: Eggleton, R.B.; Erdös, Paul
Title: Two combinatorial problems in group theory. (In English)
Source: Acta Arith. 21, 111-116 (1972).
Review: Sequences of elements from (additive) abelian groups are studied. Conditions under which a nonempty subsequence has sum equal to the group identity 0 are established. For example, an n-sequence with exactly k distinct terms represents 0 if the group has order g \leq n+\binom{k}{2} and n \geq k\binom{k}{2}.
The least number f(k) of distinct partial sums is also considered, for the case of k-sequences of distinct elements such that no nonempty partial sum is equal to 0. For example, 2k-1 \leq f(k) \leq [ 1/2 k2]+1.
In this paper a sequence is a selection of members of a set, possibly with repetitions, in which order is not important; elements are members of sets, and terms are members of sequences.
Definition. Let * be a binary operation on a set A, and let S = (ai)ni = 1 be a sequence of elements from A. S will be said to represent the element x in A if (i) x is a term in S, or (ii) there exist x,z in A such that x = y*z, and y and z are represented by disjoint subsequences of S. (Clearly this notion extends to general algebras.)
In particular, if < G,+> is an abelian group and S = (ai)ni = 1 is a sequence of elements from G, then S represents x in G just if there exists a sequence E = (\epsiloni)ni = 1 of elements from {0,1 }, not all 0, such that sum ni = 1 \epsiloniai = x.
We resolve here some aspects of the following two related problems. (1) Under what circumstances does an n-sequence of elements from an abelian group represent the zero element? (2) If an n-sequence of distinct elements from an abelian group does not represent the zero element, how many elements does it represent?
Classif.: * 20K99 Abelian groups
05A10 Combinatorial functions
05A20 Combinatorial inequalities
05-02 Research monographs (combinatorics)
00A07 Problem books
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag