GSCOP-RUB-OC-new

Soutenance de thèse de Quentin Fortier le 27 octobre 2017 à 14 H en amphi C - Site Viallet Grenoble INP

Intitulée : Aspects de la connectivité avec contraintes de matroïdes dans les graphes - Aspects of connectivity with matroid constraints in graphs
Les membres du jury :

  • Monsieur Denis Cornaz, Maître de conférences, Université Paris Dauphine, Rapporteur
  • Monsieur Yann Vaxès, Professeur des Universités, Université Aix-Marseille, Rapporteur
  • Monsieur Stéphane Bessy, Maître de conférences, Université de Montpellier, Examinateur
  • Monsieur Roland Grappe, Maître de conférences, Université Paris 13, Examinateur
  • Madame Nadia Brauner, Professeur des Universités, Université Grenoble Alpes, Présidente du jury
  • Monsieur Zoltán Szigeti, Professeur des Universités, Grenoble INP, Directeur de thèse

Résumé :

La notion de connectivité est fondamentale en théorie des graphes. Nous proposons une étude approfondie d’un récent développement dans ce domaine, en ajoutant des contraintes de matroïdes. Dans un premier temps, nous exhibons deux opérations de réduction sur les graphes connectés avec contraintes de matroïdes. Ces opérations permettent de généraliser le théorème de caractérisation de la connectivité de Menger et le théorème de packing d’arborescences d’Edmonds. Cependant, cette extension du théorème d’Edmonds ne garantie plus que les arborescences soient couvrantes. Il a été conjecturé que l’on peut toujours trouver de telles arborescences couvrantes. Nous prouvons cette conjecture dans certains cas particuliers, notamment pour les matroïdes de rang deux et pour les matroïdes transversaux. Nous réfutons cette conjecture dans le cas général en construisant un contre-exemple à plus de 300 sommets, sur une extension parallèle du matroïde de Fano. Enfin, nous explorons d’autres notions de connexité avec contraintes de matroïdes: pour des graphes mixtes, des hypergraphes, et avec condition d’atteignabilité.

Abstract :
 
The notion of connectivity is fundamental in graph theory. We study thoroughly a recent development in this field, with the addition of matroid constraints. Firstly, we exhibit two reduction operations on connected graphs with matroid constraints. Using these operations, we generalize Menger’s theorem on connectivity and Edmond’s theorem on packing of arborescences. However, this extension of Edmond’s theorem does not ensure that the arborescences are spanning. It has been conjectured that one can always find such spanning arborescences. We prove this conjecture in some cases, including matroids of rank two and transversal matroids. We disprove this conjecture in the general case by providing a counter-example with more than 300 vertices, on a parallel extension of the Fano matroid. Finally, we explore other generalizations of connectivity with matroid constraints: in mixed graphs, hypergraphs and with reachability conditions.