Auteur : Rémi DE JOANNIS DE VERCLOS
Directeur de thèse : Frédéric MAFFRAY
Co directeur : Louis ESPERET
Date : 20 juillet 2018
Directeur de thèse : Frédéric MAFFRAY
Co directeur : Louis ESPERET
Date : 20 juillet 2018
Applications des limites de structures combinatoires
en géométrie et en théorie des graphes
en géométrie et en théorie des graphes
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.
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.