Séminaire CAESAR
de combinatoire additive
Séance du 7 novembre 2013
(11 heures, École polytechnique, salle de conférence):
Éric BALANDRAUD
(IMJ, UPMC, Paris)
Une preuve algorithmique du théorème
d'Erdos-Ginzburg-Ziv d'après del Lungo Marini et Mori
Il s'agit d'un exposé type "groupe de travail" autour d'un article de del Lungo,
Marini et Mori paru en 2009. Ces auteurs s'appuient sur un
théorème de Hall (1952) redécouvert par Salzborn
et Szekeres(1979) qui, dans un groupe abélien d'ordre n,
permet d'écrire une suite de somme nulle d'éléments de
longueur n comme la somme terme à terme de deux suites
d'éléments distincts. Del Lungo, Marini et Mori
décrivent un algorithme donnant, pour une suite de 2n-1
éléments une sous-suite de somme nulle de longueur n.
Cet algorithme est quadratique en n. Il fournit une preuve tout
à fait original du théorème d'Erdos-Ginzburg-Ziv.
Retour à la page d'accueil du
séminaire