MBKB Patrick Dehornoy talks
Patrick Dehornoy

Patrick Dehornoy

Exposés / Talks


  • Braid combinatorics, permutations, and noncrossing partitions (Workshop "Non-crossing partitions in representation theory", Bielefeld, June 2014), slides without scrolling (530 kB), or with scrolling (2.9 MB)
  • We survey some of the (many) combinatorial problems involving Artin braid groups and the associated Garside structures, which are connected with finite state automata and directly lead to counting questions. We shall mention some results arising in the so-called classical case, where the relevant objects are permutations and the Solomon descent algebras, and address the so-called dual case, where the relevant objects are noncrossing partitions. This approach leads to seemingly new questions about the latter. We shall mention some recent observations by Ph. Biane in this direction.


  • Thompson's groups and its cousins as geometry groups of algebraic laws (Workshop on the Extended Family of Richard Thompson's Group, St Andrews, May 2014), scan of handwritten notes (860 kB)
  • We explain how to associate with every algebraic law (or family of algebraic laws) a monoid of partial transformations, and possibly a group, that capture some specific geometrical properties of that law. As can be expected, the group that arises in the case of associativity is Thompson's group F -- as already known to Richard Thompson -- and the group that arises in the case of associativity together with commutativity is Thompson's group V. We shall sketch a general approach and in particular address the case of exotic laws like x(yz) = (xy)(xz), or x(yz) = x(y(x(z)): in the latter case, there arises a sort of amusing mixture of Thompson's group F and Artin's braid group B_infty.


  • Laver tables (Workshop on the Extended Family of Richard Thompson's Group, St Andrews, May 2014), slides without scrolling (490 kB), or with scrolling (2.9 MB)
  • Discovered (or invented?) by Richard Laver in the 1990s, the tables that are now known as Laver tables are finite structures obeying the self-distributivity law x(yz)=(xy)(xz). Although their construction is totally explicit, some of their combinatorial properties are (so far) established only using unprovable set theoretical axioms, a quite unusual and paradoxical situation. We shall explain the construction of Laver tables, their connection with set theory, and their potential applications in low-dimensional topology via the recent computation of some associated cocycles.


  • Il était une fois la théorie des ensembles, ou l'histoire d'un malentendu (Forum régional du savoir, Rouen, février 2014), transparents sans défilement (4.2 MB), or avec défilement (7.8 MB); video.
  • Il y a longtemps, une bien étrange maladie envahit les écoles et les lycées de France, la théorie des ensembles. Personne n'en mourut, mais grandes furent la perplexité et l'incompréhension, et bien des gens en gardèrent une durable rancœur contre les mathématiques. Heureusement, l'épidémie s'éteignit d'elle-même au bout de quelques années, les professeurs et leurs élèves retrouvèrent le nord, et on finit par oublier ce qui, un temps, avait créé un si grand émoi. C'est sur cette histoire qu'on reviendra ici, pour chercher à comprendre comment la magnifique aventure scientifique lancée à la fin du dix-neuvième siècle par un visionnaire, Georg Cantor, et développée au vingtième par les génies que furent Kurt Goedel et Paul Cohen a pu, par une sorte de malentendu dû à ses succès eux-mêmes, se transformer en un dogme abscons envahissant jusqu'à l'enseignement élémentaire. L'aventure au demeurant n'est pas terminée, et on essaiera également d'expliquer un peu ce qu'est vraiment, aujourd'hui comme au temps de Cantor, la théorie des ensembles, à savoir une élaboration de la notion de l'infini, cette chose mystérieuse et fascinante dont les humains partagent l'intuition mais qu'ils comprennent toujours si mal.


  • Les tables de Laver (Colloquium, Paris, Lyon, février 2014), transparents sans défilement (520 kB), ou avec défilement (2.9 MB)
  • Découvertes (ou inventées ?) par Richard Laver au début des années 1990, les tables maintenant appelées tables de Laver sont une suite de structures finies à 2^n éléments qui obéissent à la loi x(yz)=(xy)(xz) et jouent un rôle fondamental dans l'étude de cette loi. Ce qui est étonnant, c'est que, alors que leur construction est totalement explicite, certaines des propriétés combinatoires de ces structures ne sont établies (pour le moment) qu'à l'aide d'arguments mettant en jeu des axiomes de grand cardinal dont ni la validité, ni même la non-contradiction ne peuvent être démontrées. L'exposé expliquera la construction des tables, puis les liens avec la théorie des ensembles et les abîmes de perplexité qu'ils ouvrent, et enfin quelques pistes en vue d'applications éventuelles à la théorie des tresses et des nœuds en topologie de basse dimension via des calculs de cocycles.


  • Set Theory fifty years after Cohen (Colloquium, Clermont, February 2014), slides without scrolling (600 kB), or with scrolling (1.7 MB)
  • We present a few results of modern Set Theory, with a special emphasis on the Continuum Hypothesis and the possibility of solving the question after the well known negative results of Gödel and Cohen. The developments of the past two decades arguably prove that the problem makes sense, and very recent results seem to pave the way for a possible solution.


  • Isolated orderings on an orderable group (Rolfsenfest, Marseille, July 2013), slides without scrolling (400 kB), or with scrolling (1.7 MB)
  • We describe a simple scheme for constructing finitely generated monoids in which left-divisibility is a linear ordering. The approach is connected with Garside theory, here in a non-Noetherian context. As an application we describe families of ordered groups whose space of orderings has isolated points.


  • Three termination problems (2nd International Workshop on Confluence, Eindhoven, June 2013), slides without scrolling (470 kB), or with scrolling (2.9 MB)
  • We describe three termination problems originating from various areas of algebra, namely termination of the Polish algorithm for the left-selfdistributive law, where termination is not yet proved, termination of handle reduction of braids, where termination is proved but with a very coarse complexity bound, and termination of subword reversing in semigroup theory, where termination is proved in some cases. In all three situations, the results known so far relie on the specific properties of the underlying objects, and it would be highly desirable to know whether general techniques might help.


  • Combinatoire des tresses et des structures de Garside (Séminaire Flajolet, Paris IHP, septembre 2012), transparents sans défilement (680 kB), or avec défilement (4.1 MB)
  • On passera en revue quelques problèmes combinatoires mettant en jeu les groupes de tresses et, plus généralement, les structures de Garside dont ils fournissent des exemples. Le point commun unificateur est l'existence pour les éléments des structures considérées d'un certain type de forme normale définie par des conditions locales et, de ce fait, liée à un automate et à une série rationnelle. Si le temps le permet, on mentionnera une application à des résultats de non-prouvabilité un peu paradoxaux.


  • Garside families and germs (Garside theory, state of the art and perspectives, Saint Valéry-sur-Somme, May-June 2012), slides (630 kB) and handwritten notes (proofs) (2.7 MB)
  • The general purpose of the minicourse is to show that the framework of Garside families is natural, efficient, and enables one to recover (and extend) the results about Garside groups at no extra cost. In practice, we shall summarize the main known properties of Garside families, with an emphasis on their various characterizations. Introduced as "what is needed to guarantee the existence of a greedy normal form", Garside families admit both extrinsic definitions (recognizing that a subfamily of an given monoid or category is a Garside family) and intrinsic ones (recognizing that a family generates a monoid or a category in which it embeds as a Garside family).


  • Subword reversing and ordered groups (Ordered groups and topology, Banff, February 2012), slides without scrolling (512 kB), or with scrolling (3.6 MB)
  • We show how to use subword reversing, a general method of combinatorial group theory, to construct examples of finitely generated monoids in which the left-divisibility relation is a linear ordering, leading to ordered groups whose space of left-invariant orderings has isolated points. This approach provides one more proof of the orderability of Artin's group of 3-strand braids.


  • A quoi sert l'infini ?
    (Mathematic park, Paris IHP, janvier 2012, version 90') ; transparents sans défilement (2,2 Mo) ou avec défilement (5 Mo),
    (Rouen, janvier 2012, version 60') ; transparents sans défilement (2,1 Mo) ou avec défilement (4,1 Mo) ; enregistrement video.
  • Qu'il faille faire appel à des outils infinis pour démontrer des propriétés des objets infinis n'est pas tres étonnant. Par contre, il est moins intuitif que le passage par l'infini soit déterminant quand il s'agit des propriétés d'objets finis, par exemple les nombres entiers. On montrera pourtant sur quelques exemples que l'utilisation de méthodes ou d'intuitions mettant en jeu l'infini, voire même de très spéculatifs "hyper-infinis", peut permettre de démontrer ou de découvrir des propriétés nouvelles des objets finis.


  • News from Garside theory (Braids 2011, Sevilla, June 2011), slides (900 kB)
  • About fifteen years ago, it was shown that most of the algebraic properties of braid groups extend to a larger family of groups known as Garside groups. A crucial role is played by the existence of remarkable decompositions for the elements of the involved groups, the so-called greedy normal form. Analyzing the mechanism of this normal form more closely leads to further generalizations. Removing superfluous hypotheses helps us to capture new examples, better understand the essential elements, and derive new applications.


  • A conjecture about Artin-Tits groups, plus news from the Garside theory (Ecole de physique, Les Houches, Jan. 2011), slides (240 KB)
  • We conjecture that the word problem of Artin-Tits groups can be solved without introducing trivial patterns ss^{-1} or s^{-1}s. We shall make this statement (which does not imply the decidability of the word problem) precise, and discuss particular cases and consequences.

    We shall also mention some recent developments of the Garside theory centered on Garside families and Garside maps.


  • The braid order: history and connection with knots (ICTP, Trieste, Italy, May 2008), slides without scrolling (1.1 MB), or with scrolling (3.5 MB)
  • We review some of the many aspects of the standard braid order, including its origins connected with some bizarre questions of set theory. A special emphasis will be put on the few known connections with knot theory, and on recent seemingly promising developments in this direction.


  • The subword reversing method (ICGS, Lincoln, Nebraska, May 2008), slides without scrolling (730 KB), or with scrolling (3.4 MB)
  • Subword reversing is an algorithmic method for constructing van Kampen diagrams by referring to a preferred direction. Although reversing cannot work for every (semi)group presentation, it proves to be relevant in many nontrivial cases. Analyzing one example in detail, we shall summarize the main known results about the range of the method, its uses, and its efficiency.


  • Cantor et les infinis (Un texte, un mathématicien, BNF Paris, mars 2009), transparents sans défilement (1.1 Mo), ou avec défilement (3.5 Mo) ; voir videos ici.
  • En 1874, Georg Cantor publie dans le journal de Crelle un article où il démontre qu'il n'existe pas plus de nombres algébriques que de nombres entiers mais que, par contre, il existe strictement plus de nombres réels. Cet article est révolutionnaire car, pour la première fois, l'infini est considéré non plus comme une limite inatteignable mais comme un possible objet d'investigation. Sa descendance est extraordinaire : non seulement il marque la naissance de la théorie des ensembles — en fait une théorie de l'infini -- mais il contient deja en germe le problème du continu qui a occupé toute la fin de la vie de Cantor, et a été et continue d'être le moteur du développement de cette théorie, un temps objet d'une fascination déraisonnable reposant sur un malentendu, et aujourd'hui largement méconnue.


  • Sur la distance de rotation entre deux arbres binaires (Bordeaux, février 2009), transparents sans défilement (920 KB), or avec défilement (3.2 Mo)
  • Le problème est de construire des arbres binaires de taille n qui soient éloignés vis-à-vis de la distance de rotation, ce qui équivaut à construire des expressions parenthésées à n variables éloignées vis-à-vis du déplacement de parenthèses par associativité, ou encore des triangulations d'un (n+2)-gone éloignées vis-à-vis de l'échange de diagonales. On présente la magnifique solution de Sleator-Tarjan-Thurston basée sur la géometrie hyperbolique, qui est optimale mais valable seulement pour n grand (non effectif), ainsi qu'une solution combinatoire récente basée sur une notion de séparatrice dans les associaèdres, qui est — pour le moment — non optimale, mais valable pour tout n.


  • The subword reversing method (Edinburgh, December 2008), slides without scrolling (660 KB), or with scrolling (2.1 MB)
  • Subword reversing is an algorithmic method for constructing van Kampen diagrams by referring to a preferred direction. Although reversing cannot work for every (semi)group presentation, it proves to be relevant in many nontrivial cases, including the classical and dual presentations of Artin-Tits groups. We shall summarize the known results, and the many open questions that involve the algorithmic complexity of the method and its actual range, as well as recent applications to the determination of the combinatorial distance between various reduced expressions of a permutation in terms of transpositions.


  • Braids, self-distributivity, and Garside categories (Paris, September 2008), slides without scrolling (640 KB), or with scrolling (3.4 MB)
  • Recently identified by Krammer and others, the notion of a Garside category allows to revisit the connection between braids and the self-distributive law, and to summarize it as follows: associated with the self-distributivity law is a certain left-Garside category, of which the standard Garside structure of braid groups is a projection. This approach leads in particular to a simple restatement of the Embedding Conjecture, the main open question in the area, and to a realistic program to solve it.


  • Le problème d'isotopie des tresses (Leçon de mathématiques d'aujourd'hui, Bordeaux, avril 2008), transparents partie 1 avec défilement (2.8 Mo), sans défilement (830 Ko) ; transparents partie 2 avec défilement (5 Mo), sans défilement (1.3 Mo) ; voir videos ici.
  • Le problème d'isotopie des tresses est la question de reconnaître si deux diagrammes de tresse peuvent être déformés continûment l'un en l'autre. C'est un problème de difficulté moyenne : ni trop facile — aucune solution n'est triviale — ni trop difficile — des solutions explicites existent. On présentera quelques-unes des (très) nombreuses solutions connues à ce jour, l'intérêt principal étant la multiplicité des approches possibles — algébriques, combinatoires, géométriques, topologiques, etc. — et la diversité des solutions qui en résultent.


  • Dual presentation of Thompson's group F and flip distance between triangulations (CIRM, June 2008), slides without scrolling (523 KB), or with scrolling (1.76 MB);
  • Viewing the group F as the geometry group of associativity -- as in Thompson's original approach -- leads to expressing F as the group of fractions of a monoid F+* that is larger than the submonoid F+ generated by the standard elements x_i. We show that F+* admits left and right least common multiples and greatest common divisors. This gives a lattice structure on F, connected with the Tamari lattices. The associated metric is rather strange, as F+* does not quasi-isometrically embed in F. As an application, we consider the rotation distance problem, which is also the problem of finding the flip distance between triangulations of a polygon, and the diameter of the associahedra. The problem was asymptotically solved by Sleator, Tarjan, and Thurston using hyperbolic geometry. Using combinatorial arguments derived from the above approach, we prove lower bound results that are not optimal, but nevertheless are non-trivial.


  • Théorèmes de non-prouvabilité (Nantes, octobre 2007), transparents (2.1 Mo)
  • Sans viser à aucune exhaustivivité, on passe en revue quelques-uns des nombreux résultats affirmant que telle ou telle assertion n'est pas démontrable dans tel ou tel système, depuis les fameux théorèmes d'incomplétude de Godel jusqu'aux résultats de Paris-Harrington; on mentionne également des résultats récents mettant en jeu les tresses, obtenus en collaboration avec L.Carlucci et A.Weiermann.


  • Unprovability statements involving braids, slides (2.1 MB)
  • (joint work with A.Weiermann, L.Carlucci) We construct long sequences of braids that are descending with respect to the standard order of braids (``Dehornoy order''), and we deduce that, contrary to all usual algebraic properties of braids, certain simple combinatorial statements involving the braid order are true, but not provable in the subsystems ISigma1 or ISigma2 of the standard Peano system.


  • The many solutions for the isotopy problem of braids, slides (1.5 MB)
  • We review some of the (many) solutions for the word problem of Artin braids, with a special emphasis on the so-called handle reduction method and the proof of its convergence, which relies both on the Garside structure and on a canonical ordering of braids. We shall show that the subject is connected with intriguing conjectures about the symmetric group and mention recent results by J.Fromentin about the Birman-Ko-Lee monoid.


  • Alternating normal form of braids and applications (Banff, April 2007), slides (1.2 MB)
  • We describe new types of normal forms for braid monoids, Artin-Tits monoids, and, more generally, all monoids in which divisibility has some convenient lattice properties (``locally Garside monoids''). We show that, in the case of braids, one of these normal forms turns out to coincides with the normal form introduced by Burckel. This approach leads to a new, simple description for the canonical well-order of B_n in terms of that of B_{n-1}. In a joint work with A.Bovykin, L.Carlucci and A.Weiermann, we apply the latter to establish unprovability statements for certain games involving braids.


  • Combinatorics of normal sequences of braids (Clermont, September 2006), slides (1.2 MB)
  • Many natural counting problems arise in connection with the normal form of braids---and seem to have not been much considered so far. Here we solve some of them by analysing the normality condition in terms of the associated permutations, their descents and the corresponding partitions. A number of different induction schemes appear in that framework.


  • Algorithms for Garside groups (GTG Prague, June 2006, and GATGA Barcelona, September 2006), slides (1.5 MB)
  • The family of Garside groups is a generalization of braid groups and, more generally, of spherical Artin-Tits groups. They share with the latter the existence of efficient computational methods connected with a bi-automatic structure, and, for this reason, they may appear as natural platforms for group-based cryptography. We shall review the existing solutions to two distinct questions: (i) recognizing whether a given finite presentation defines a Garside group, and, if so, (ii) computing in this group by means of the so-called greedy normal form.


  • From sets to braids, slides (1.8 MB)
  • We show how studying large cardinals in Set Theory (which are objects whose existence is, and will remain, an unprovable assumption) has led to constructing new examples of algebraic systems satisfying the left self-distributivity law, and, from there, quite naturally, to the discovery of a linear ordering on Artin's braid groups. The latter has led to new braid applications, and it has now received several equivalent purely geometrical or topological constructions.

  • Des ensembles aux tresses (LIGC, Paris, novembre 2005; SMF, Paris, mai 2006), transparents version longue (1.8 Mo), version courte (1.1 Mo)
  • On montre comment l'étude des grands cardinaux en théorie des ensembles a mené à la construction de systèmes algébriques d'un type nouveau, et, de là, à la découverte d'un ordre total sur les tresses et à celle d'une nouvelle solution particulièrement efficace de leur problème d'isotopie.


  • The group of parenthesized braids (Leigh, March 2006), slides (1.2 MB)
  • We describe a seemingly new and interesting group B obtained by gluing in a natural way two well-known groups, namely Artin's braid group B_infty and Thompson's group F. The elements of B correspond to braid diagrams in which the distances between the strands are non uniform and some rescaling operators may change these distances. The group B shares many properties with B_infty: as the latter, it can be realized as a subgroup of a mapping class group, namely that of a sphere with a Cantor set removed, and as a group of automorphisms of a free group. Technically, the key point is the existence of a self-distributive operation on B.


  • Braid-based cryptography (Bochum, Nov. 2005), slides (1.8 MB)
  • In the recent years, several authors began to develop braid-based cryptographical protocols. The talk aims at giving a general overview of this quickly developing field, insisting on the various cryptographical questions one has to address, and on the theoretical and practical problems arising from using braids: choice of a difficult problem (often conjugacy), representation of the data (normal vs. reduced forms), security proofs (lower complexity bounds) and possible attacks.


  • Le calcul des tresses (Journées APMEP, Caen, octobre 2005), transparents (2.6 Mo)
  • Les tresses n'intéressent pas seulement les coiffeurs et les artistes, elles donnent également lieu a une théorie mathématique profonde qui a des ramifications dans de nombreux domaines: algebre, combinatoire, géométrie, topologie, informatique, et meme physique mathématique et théorie des ensembles. L'exposé vide à montrer qu'il existe un véritable calcul des tresses, qui est une sorte d'extension non commutative du calcul avec les nombres entiers. On presentera quelques développements récents, notamment un algorithme de démelage que chacun peut programmer sur une calculette mais dont l'efficacité étonnante reste pour le moment mystérieuse. On évoquera aussi les possibles applications du calcul des tresses en cryptographie.


  • The self-distributive structure of parenthesized braids (Mile High Conference, Denver, July 2005), slides
  • Artin's braid group B_infty is equipped with a remarkable left self distributive operation that reflects a deep connection between braids and the self-distributive law. A similar connection exists between R. Thompson's group F and the associativity law. Mixing the two laws leads to introducing a new group B_\bullet that extends both B_\infty and F, and whose elements can be viewed as braids in which the distances between the strands need not be uniform. Many properties of B_\infty extend to B_\bullet, in particular the connection with the fundamental group of a punctured surface, the embeddability in the automorphisms of a free group, and the existence of a self-distributive structure.


  • Still another approach to the braid ordering (Journées Tresses, Luminy, June 2005), slides
  • We develop a new approach to the linear ordering of the braid group B_n, based on investigating its restriction to the set Div(Delta_n^d) of all divisors of Delta_n^d in the monoid B_infty^+, i.e., to positive n-braids whose normal form has length at most d. In the general case, we compute several numerical parameters attached with the finite orders (Div(Delta_n^d), <). In the case of 3 strands, we moreover give a complete description of the increasing enumeration of (Div(Delta_3^d), <). We deduce a new, specially direct construction of the ordering on B_3, and a new proof of the result that its restriction to B_3^+ is a well-ordering of ordinal type omega^omega.


  • Poster "Tresses" slides
  • Quelques images de la théorie des tresses


  • Braid colourings (First East Asian School on Knots, Links and Related Topics, Seoul, Feb. 2004), slides
  • We review results involving arc colourings in a braid or a link diagram. The left self-distributivity idendity then appears as an algebraic counterpart to Reidemeister move of type III. Using classical and less classical self-distributive operations leads to a number of different results, as well as to many open questions.


  • Progres récents sur l'hypothèse du continu (d'après Woodin) (Séminaire Bourbaki, Paris, mars 2003), transparents
  • Les travaux récents de Woodin ont considérablement renouvelé la théorie des ensembles en lui apportant une intelligibilité globale et en restaurant son unité. Pour la première fois, ses résultats ouvrent une perspective réaliste de résoudre le problème du continu, et, à tout le moins, ils établissent le caractère irréfutablement signifiant et précis de celui-ci.

  • Recent results about the Continuum Hypothesis, after Woodin, slides
  • The work of Hugh Woodin has deeply renewed Set Theory, making it more intelligible and restoring its unity. For the first time, there exists a reasonable perspective to solve the Continuum Problem. At the least these developments definitely demonstrate that the problem is meaningful.


  • Homology of Gaussian groups (London Topology Day, London, Dec. 2001), slides
  • (joint with Yves Lafont) We give one (actually two) explicit method(s) for computing the homology of a Gaussian group, or, more generally, of a monoid where division is Noetherian and least common multiples exist when common multiples do. We construct two exact chain complexes, one relying on the greedy normal form, and the other on using some preordering after Kobayashi.


  • The geometry monoid of an algebraic law (AMS-SMF Joint Meeting, Lyon, July 2001), slides
  • One can associate with every algebraic law (or family of algebraic laws) a monoid that describes some geometrical phenomena specific to the considered law. In good cases, the algebraic study of this so-called geometry monoid enables one to prove results about the law, typically to solve the word problem or to construct concrete realizations of the free objects in the associated variety. Interesting examples are provided by associativity---in which case the geometry monoid is closely connected with R. Thompson's group F---and self-distributivity---in which case the geometry monoid is an extension of Artin's braid group B_infty. At the technical level, the point is to switch from a monoid to a group by using presentations, and to internalize the action of the geometry monoid on abstract terms by representing the latter inside the geometry monoid.


  • Dynnikov's formulas for the linear ordering of braids (AMS Meeting, New York, Nov. 2000), slides
  • We review several equivalent definitions of the linear ordering of braids, in particular the recent approach by Dynnikov in terms of laminations. The latter leads to a very quick decision method: quadratic complexity independently of the number of strands.


  • Gaussian groups (Magnus Seminar, New York, Nov. 2000), slides
  • Define a small Gaussian group to be the group of fractions of a cancellative monoid where left and right least common multiples exist, and an additional finiteness condition holds. Artin's braid groups, and, more generally, all Artin groups of finite Coxeter type, are examples of small Gaussian groups. We show that most of the classical properties of the braid groups, e.g. automaticity, torsion freeness, description of the center extend to small Gaussian groups; we also prove that for a presentation to define a small Gaussian group is a recursively enumerable property, and wedescribe a concrete, tractable method for recognizing such groups. REMARK: Small Gaussian groups are now called "Garside groups".