Auteur : Quentin FORTIER
Directeur de thèse : Zoltan SZIGETI
Date : 27 octobre 2017
Directeur de thèse : Zoltan SZIGETI
Date : 27 octobre 2017
Aspects de la connectivité avec contraintes de matroïdes dans les graphes
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.
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.