GSCOP-RUB-OC-new

Soutenance de thèse de Rémi de Joannis de Verclos (OC) vendredi 20 juillet 2018 à 14h30 en amphi Gosse - Site Viallet - Grenoble INP

Intitulée : "Applications des limites de structures combinatoires en géométrie et en théorie des graphes"
Les membres du jury :

  • M. Louis Esperet, Chargé de recherche CNRS, G-SCOP, Co-encadrant.
  • M. Daniel Král', Professeur, Université de Warwick, Examinateur.
  • M. Frédéric Maffray, Directeur de recherche CNRS, G-SCOP, Directeur de thèse.
  • M. Patrice Ossona de Mendez, Chargé de recherche CNRS, EHESS, Paris, Rapporteur.
  • M. Jean-Sébastien Sereni, Chargé de recherche CNRS, Laboratoire ICube, Strasbourg, Co-encadrant.
  • M. Asaf Shapira, Professeur, Université de Tel Aviv, Rapporteur.
  • M. Stéphan Thomassé, Professeur, ENS de Lyon, Examinateur.

Résumé
:

La théorie des limites d'objets combinatoires est une récente théorie qui a permis de tisser des liens entre différents domaines tels que la combinatoire, l'analyse, la géométrie ou la théorie de la probabilité. Cette thèse applique des méthode venant de cette théorie à des problèmes de combinatoire extrémale.
Dans un premier chapitre, on développe une théorie des limites d'objets appelés types d'ordre, un objets qui encode des configurations d'ensembles de points du plan et qui caractérise de nombreuses propriétés essentielles de cet ensemble de point comme, par exemple, son enveloppe convexe. On étudie en particulier différentes manière de représenter ces limites de types d'ordre et les propriétés de ces représentation.
Un second chapitre traite de test de propriété. Un testeur de propriété est un algorithme aléatoire permettant de séparer les objets ayant une certaine propriété des objet à distance au moins ε de l'avoir, au sens de la distance d'édition. Ce domaine donne des algorithmes extrêmement rapides, et en particulier des algorithmes dont la complexité ne dépends pas de la taille de l'entrée mais seulement du paramètre de précision ε. Un résultat fondamental de cet domaine pour les graphes montré par Alon et Shapira est le suivant : toute classe de graphe héréditaire possède un tel testeur. Cette thèse contribue à la question suivante : Quelles classes de graphes possède un testeur dont la complexité est un polynôme en 1/ε ?
La théorie des algèbres de drapeaux est un outil lié aux limites de graphes qui permet de démontrer des bornes sur certains paramètres combinatoires à l'aide d'un ordinateur. Dans un troisième chapitre, je présente un programme écrit durant ma thèse qui implémente cette méthode. Ce programme est utilisé pour obtenir un nouvelle borne pour le cas triangulaire de la conjecture de Caccetta-Häggkvist.