Trees, Decompositions, and Knot theory

Arbres, décompositions, et théorie des Nœuds La théorie des graphes et la théorie des nœuds sont deux célèbres domaines mathématiques qui présentent de profondes interactions. Cette thèse se concentre sur l'étude de certains problèmes de théorie des nœuds d'un point de vue informatique et en s'inspirant de résultats et méthodes issus de la théorie des graphes.Le premier problème que nous abordons concerne la décidabilité d'un invariant de nœud. Le genre d'un nœud est un invariant classique : c'est le genre minimal d'une surface orientable plongée dans l'espace de dimension 3 qui est bordée par le nœud. De nos jours, il est assez bien compris d'un point de vue informatique. En revanche, aucun algorithme n'est connu pour ses variantes en dimension 4, à la fois dans la catégorie des variétés lisses et dans celle des variétés localement plates. Nous étudions une classe de nœuds et d'entrelacs appelés entrelacs arborescents de Hopf, qui sont obtenus comme bords de surfaces construites par des plombages itérés de bandes de Hopf. Nous montrons que sur ces entrelacs, le calcul des défauts de genre, qui mesurent à quel point les genres quadridimensionnels diffèrent du genre classique, est décidable. Notre preuve est non-constructive et est obtenue en prouvant qu'une relation d'inclusion sur les surfaces associées aux entrelacs arborescents de Hopf forme un bel ordre.Le deuxième problème que nous attaquons est motivé par l'existence d'algorithmes efficaces pour calculer de nombreux invariants et propriétés de nœuds sur des diagrammes de faible largeur arborescente (treewidth). Il a été récemment prouvé, par de complexes résultats de topologie en basse dimension, qu'il existe des nœuds qui n'admettent pas de diagrammes de faible largeur arborescente. Nous entamons ici une étude approfondie des décompositions arborescentes des diagrammes de nœuds (ou plus généralement, des diagrammes de graphes spatiaux) en utilisant des idées de la théorie structurelle des graphes. Nous définissons une obstruction sur les plongements dans l'espace qui s'oppose à des diagrammes de faible largeur arborescente. Nous prouvons de plus que cette obstruction est optimale vis-à-vis d'un invariant de largeur que nous définissons. Nous montrons ensuite l'existence d'une telle obstruction dès qu'il existe un plongement dans une surface avec haute représentativité. Cette dernière partie est toujours vérifiée sur les nœuds toriques: nous fournissons ainsi une nouvelle preuve que ces nœuds n'admettent aucun diagramme de faible largeur arborescente. Pour finir, nous nous concentrons sur la complexité des diagrammes de nœuds sous l'action de mouvements de Reidemeister. Reconnaître le nœud trivial est un problème fondamental de théorie des nœuds. Une façon naturelle de l'attaquer est d'appliquer des mouvements de Reidemeister sur un diagramme du nœud de manière exhaustive ou aléatoire jusqu'à ce que le diagramme corresponde à un cercle. Il s'avère que le nombre de croisements de certains diagrammes du nœud trivial doit nécessairement augmenter pendant l'exécution de cet algorithme. De plus, on ne connaît pas de borne inférieure meilleure que constante sur le nombre de croisements qui doivent être ajoutés pendant l'exécution d'algorithmes similaires. Cet algorithme peut aussi être appliqué au problème de décider si un entrelacs est séparé, c'est-à-dire, s'il existe une sphère qui sépare deux de ses composantes. Il présente le même problème de devoir ajouter des croisements à un diagramme pendant son exécution. Nous prouvons qu'il existe des diagrammes d'entrelacs qui nécessitent un nombre arbitrairement grand de croisements à ajouter pour être séparés en utilisant cet algorithme