A polynomial-time algorithm for finding zero-sums

Erdös, Ginzburg and Ziv proved that any sequence of 2 n − 1 (not necessary distinct) members of the cyclic group Z n contains a subsequence of length n the sum of whose elements is congruent to zero modulo n . There are several proofs of this celebrated theorem which combine combinatorial and algebr...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2009-05, Vol.309 (9), p.2658-2662
Main Authors: del Lungo, Alberto, Marini, Claudio, Mori, Elisa
Format: Article
Language:English
Subjects:
Abelian group
Algorithmics. Computability. Computer arithmetics
Applied sciences
Artificial intelligence
Combinatorial group theory
Combinatorial problem
Computer science
control theory
systems
Erdös–Ginzburg–Ziv Theorem
Exact sciences and technology
Group theory
Group theory and generalizations
Learning and adaptive systems
Mathematics
Permutation
Sciences and techniques of general use
Theoretical computing
Zero-sum Ramsey theory
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Erdös, Ginzburg and Ziv proved that any sequence of 2 n − 1 (not necessary distinct) members of the cyclic group Z n contains a subsequence of length n the sum of whose elements is congruent to zero modulo n . There are several proofs of this celebrated theorem which combine combinatorial and algebraic ideas. Our main result is an alternative and constructive proof of this result. From this proof, we deduce a polynomial-time algorithm for finding a zero-sum n -sequence of the given ( 2 n − 1 ) -sequence of an abelian group G with n elements (a fortiori for Z n ). To the best of our knowledge, this is the first efficient algorithm for finding zero-sum n -sequences.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2008.06.018