Liste par séminaire

Soutenances de thèses
Le 17 nov. 2014 à - Amphi St Priest

Albar Boris
Spécialité Doctorale Mathématiques
Etude des classes de graphes et de matroïdes closes par mineur : densité de triangles, coloration, rigidité et orientations


Jury:
Jorge RAMIREZ ALFONSIN, UM2, Co-directeur de thèse
Daniel GONCALVES, UM2, Co-directeur de thèse
Andras SEBO, UJF, Rapporteur
Patrice OSSONA DE MENDEZ, EHESS, Rapporteur
Victor CHEPOI, Université Aix Marseille

Résumé :
La théorie des mineurs de graphes est apparue dans la première partie du XXème siècle avec la caractérisation des graphes planaires par Kuratowski et Wagner. L'étude des classes de graphes closes par mineurs intervient dans de nombreux domaines en théorie des graphes (graphes plongés dans les surfaces, coloration, théorie extrémale des graphes, théorie de la rigidité, ...). Dans la première partie de cette thèse, nous prouverons l'existence de mineurs de graphes complets dans des graphes dont toutes les arêtes appartiennent à un certain nombre de triangles. Cette propriété trouve des applications dans la théorie de la rigidité des graphes ainsi qu'à la coloration de certaines classes de graphes closes par mineurs. Une seconde partie est consacrée à la généralisation de cette propriété des graphes vers les matroïdes. Les matroïdes sont des objets combinatoires introduits en 1935 par Whitney qui ont pour but d'axiomatiser le concept d'indépendance linéaire. En particulier, les notions de triangle et de mineur de graphe peuvent se généraliser à ces objets. Nous étudierons donc les matroïdes dont tous les éléments appartiennent à un certain nombre de triangles et montrerons que l'on peut trouver certains mineurs particuliers dans ces matroïdes. Enfin, une dernière partie de cette thèse sera consacrée à l'étude de certaines orientations des graphes plongés dans les surfaces.