Bases additives et flots dans les graphes

par Louis Esperet (G-SCOP, Grenoble)

mardi 28 mars 2017, 10:45 → 11:45 Europe/Paris

salle Fokko du Cloux (ICJ, UCBL - La Doua, Bât. Braconnier)

Il a été conjecturé par Jaeger, Linial, Payan, et Tarsi en 1992 que pour tout nombre premier p, il existe une constante c telle que pour tout n, l'union (avec répétition) des vecteurs de toute famille de c bases linéaires de (Z_p)^n forme une base additive de (Z_p)^n (i.e tout élément de de (Z_p)^n peut s'écrire comme la somme d'un sous-ensemble de ces vecteurs). J'expliquerai comment montrer la conjecture lorsque chaque vecteur contient au plus deux entrées non nulles. Ce cas contient déjà plusieurs applications non-triviales en théorie des graphes, en particulier liées à l'existence de flots non nuls et d'orientations particulières dans les graphes hautement connexes. J'expliquerai ces applications et les liens qui les unissent. Travail en commun avec Rémi de Joannis de Verclos, Tien-Nam Le, et Stéphan Thomassé.