SMF

Exposé Bourbaki 1121 : Nœuds, mouvements de Reidemeister et algorithmes (d'après Lackenby)

Exposé Bourbaki 1121 : Knots, Reidemeister moves and algorithms (after Lackenby)

Arnaud de MESMAY
Exposé Bourbaki 1121 : Nœuds, mouvements de Reidemeister et algorithmes (d'après Lackenby)
  • Consulter un extrait
  •  
                
  • Année : 2019
  • Tome : 407
  • Format : Électronique
  • Langue de l'ouvrage :
    Français
  • Class. Math. : 57M25, 57N10, 68Q25
  • Pages : 27-52
  • DOI : 10.24033/ast.1059

Un nœud  est souvent représenté par un diagramme de nœud, c'est-à-dire une projection sur deux dimensions, où l'on indique à chaque croisement lequel des deux brins passe au-dessus de l'autre. Deux diagrammes représentent alors le même nœud si et seulement si ils peuvent être reliés par une série de mouvements locaux, appelés mouvements de Reidemeister. Dans cet exposé, nous présenterons un résultat de Lackenby montrant que, partant d'un diagramme à  $c$ croisements du nœud trivial, un nombre polynomial en $c$ de tels mouvements suffit pour arriver au diagramme trivial. La preuve s'appuie sur la théorie des surfaces normales et les travaux de Dynnikov sur les présentations par arcs. En corollaire, cela fournit un algorithme (exponentiel) pour reconnaître les nœuds triviaux, et nous en profiterons pour discuter de quelques problèmes algorithmiques autour des nœuds et des entrelacs.

A knot can be conveniently represented by a knot diagram, which is a projection of this knot into two dimensions, where one specifies at each crossing which of the arcs is above the other one. Two knot diagrams correspond to the same knot if and only if they can be related through a series of local moves, called Reidemeister moves. In this presentation, we will explain a result of Lackenby showing that, starting with a diagram of the unknot with $c$ crossings, only a polynomial number (in $c$) of Reidemeister moves is needed to reach the trivial driagram. The proof relies on the theory of normal surfaces and the work of Dynnikov on arc presentations. As a corollary, this provides an exponential algorithm to recognize the unknot, and we will give some background on the current algorithmic challenges surrounding knots and links.

Nœud, nœud trivial, entrelacs, mouvement de Reidemeister, surface normale, présentation par arcs
Knot, unknot, link, Reidemeister move, normal surface, arc presentation

Électronique
Electronic
Prix public Public price 10.00 €
Prix membre Member price 7.00 €
Quantité
Quantity
- +