Mathematics – Combinatorics
Scientific paper
2009-03-18
Mathematics
Combinatorics
Scientific paper
An old conjecture of Graham stated that if $n$ is a prime and $S$ is a sequence of $n$ terms from the cyclic group $C_n$ such that all (nontrivial) zero-sum subsequences have the same length, then $S$ must contain at most two distinct terms. In 1976, Erd\H{o}s and Szemeredi gave a proof of the conjecture for sufficiently large primes $n$. However, the proof was complicated enough that the details for small primes were never worked out. Both in the paper of Erd\H{o}s and Szemeredi and in a later survey by Erd\H{o}s and Graham, the complexity of the proof was lamented. Recently, a new proof, valid even for non-primes $n$, was given by Gao, Hamidoune and Wang, using Savchev and Chen's recently proved structure theorem for zero-sum free sequences of long length in $C_n$. However, as this is a fairly involved result, they did not believe it to be the simple proof sought by Erd\H{o}s, Graham and Szemeredi. In this paper, we give a short proof of the original conjecture that uses only the Cauchy-Davenport Theorem and pigeonhole principle, thus perhaps qualifying as a simple proof. Replacing the use of the Cauchy-Davenport Theorem with the Devos-Goddyn-Mohar Theorem, we obtain an alternate proof, albeit not as simple, of the non-prime case. Additionally, our method yields an exhaustive list detailing the precise structure of $S$ and works for an arbitrary finite abelian group, though the only non-cyclic group for which this is nontrivial is $C_2\oplus C_{2m}$.
No associations
LandOfFree
Note on a Conjecture of Graham does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Note on a Conjecture of Graham, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Note on a Conjecture of Graham will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-401952