Olson's Conjecture

This Spring we were working on some problems from additive number theory together with Matt DeVos and Luis Goddyn. There are some interesting combinatorial problems, some of which Matt has proposed as the next Problem of the month.

Olson's Conjecture ([2]): Let G be a (multiplicative) group of order n and let a₁, a₂, ..., a_2n-1 be a sequence of elements from G. Then there exist indices 0 < i₁ < i₂ < ... < i_n < 2n such that the product a_i1a_i2...a_in = 1.

Erdős, Ginzburg and Ziv proved this for G abelian. There are many interesting extensions of the EGZTheorem. However, for nonabelian groups, Olson proved a weaker version where reordering is permitted, but little else is known.

Bibliography:

[1] P. Erdős, A. Ginzburg and A. Ziv, A theorem in additive number theory, Bull. Res. Council Israel 10F (1961), 41-43.

[2] J. E. Olson, On a combinatorial problem of Erdős, Ginzburg, and Ziv. J. Number Theory 8 (1976), 52-57.

Send comments to Bojan.Mohar@uni-lj.si

Revised: avgust 05, 2006.