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

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.