Accueil des participants

Flots non nuls et couplages parfaits

Louis Esperet

(G-SCOP)

Un k-flot non-nul dans un graphe est une orientation des arêtes et une assignation d'entiers entre 1 et k à chaque arête qui vérifie la loi de conservation du flot autour de chaque sommet. J'évoquerai plusieurs conjectures et problèmes ouverts classiques sur les flots non-nuls dans les graphes (en particulier les conjectures des 3-flots et 5-flots de Tutte), ainsi que des avancées récentes sur ces questions. Un couplage parfait dans un graphe est un ensemble d'arêtes qui couvre chaque sommet exactement une fois. Je mentionnerai également plusieurs problèmes importants autour des couplages parfaits dans les graphes cubiques (il existe des liens intéressants, plus ou moins compris, entre flots non-nuls et couverture par des couplages parfaits).

Pause

Quelques-uns des pROblèmes qui m'intriguent le PLus

Andras Sebo

G-SCOP

Je voudrais partager avec vous quelques problèmes combinatoires ouverts liés à la programmation linéaire (PL) avec leurs contextes et des nouvelles récentes les concernant. Certains sont utiles, d'autres pour le moment "seulement" intéressants peut-être. Trois exemples, nous en verrons d'autres si nous avons le temps: Existe-t-il un chemin Hamiltonien entre deux sommets donnés d'un graphe, 50% plus long que le résultat d'une relaxation PL naturelle ? Ceci a l'air de se laisser approcher plus facilement que les fameux 4/3 quand s=t. Existe-t-il une solution du probleme de bin packing qui utilise juste 1 bin de plus, que la relaxation PL ? Et pareil pour l'indexe chromatique si on le regarde comme packing de couplages. Et puis est-ce que ces problèmes sont-ils de la RO ? de l'OC ? Des mathématiques Discrètes ? De la théorie des Graphes ? Aucune connaissance ne sera requise, même la PL sera présente seulement par une proposition facile qui sera expliquée.

Pause déjeuner

An introduction to the 1-2-3 Conjecture and related problems

Julien Bensmail

I3S / INRIA

The 1-2-3 Conjecture, posed in 2004 by Karonski, Luczak and Thomason, asserts that, for every connected graph different from K_2, we can label its edges with labels 1,2,3 so that no two adjacent vertices receive the same sum of incident labels. Despite many efforts, this conjecture is still widely open to date; yet, many interesting works and approaches towards the understanding of both its main and side aspects have been initiated. This talk will be meant as a high-level introduction to the field, covering both the original conjecture and variants of it (including, notably, optimisation variants). For each of those problems, we will survey both most of all the results we know, as well as some of the numerous main and side questions that remain open.

Pause

La conjecture de Sands Sauer et Woodrow

William Lochet

University of Bergen

En 1982, Sands, Sauer et Woodrow montrent que tout graphe orienté dont les arcs sont bi-colorés admet un ensemble indépendant S (aucune paire de sommets de S ne peut être reliée par un chemin monochromatic) où chaque sommet peut être atteint par un chemin monochromatic partant de S. Ce résultat permet, entre autres, de donner une autre preuve du théorème de Gale-Shapley sur les mariages stables. Si les arcs du graphes orientés sont coloriés avec au moins 3 couleurs, ce résultat n'est plus vrai (il suffit de considérer un triangle orienté tri-colorié). Cependant, Sands Sauer et Woodrow conjecturent alors de l'existence d'une fonction f, telle que pour tout graphe orienté dont les arcs sont k-coloriés, il existe un ensemble de f(k) indépendants tels que chaque sommet peut être atteint par un chemin monochromatic partant de l'un de ces indépendants. L'existence de la fonction f reste ouverte dès k = 3. L'exposé présentera aussi la preuve de la conjecture de Sands Sauer et woodrow dans le cas des tournois qui a été prouvée récemment par Bousquet, Lochet et Thomassé.