MBKB Patrick Dehornoy talks
Patrick Dehornoy

Patrick Dehornoy

Exposés spécialisés / Specialized talks

The SD-world: a bridge between algebra, topology, and set theory (Fourth Mile High Conference, Denver, CO (USA), July-August 2017), slides without scrolling (800 kB), or with scrolling (4.7 MB)

Minicourse 1: The SD-world. A shelf is a set equipped with a binary operation that obeys the self-distributivity law (SD), in the left version x(yz) = (xy)(xz), or the right version (xy)z = (xz)(yz). We gave a general overview of shelves and their connection with low-dimensional topology, and explain two solutions of the word problem of SD: one semantical solution based on realizing the free shelf on one generator inside Artin's braid group B_infty, and one syntactical solution based on introducing the "Thompson's monoid of SD" (analogous to Thompson's group F for associativity).
Minicourse 2: Connection with set theory. Under some (unprovable) large cardinal assumption, a shelf naturally appears in set theory. This shelf was proved by R.Laver to have interesting properties: its divisibility relation has no cycle, and, for every n, it admits as a quotient the nth Laver table, a finite shelf with 2^n elements. The fascinating point is that this representation leads to combinatorial results about Laver tables with no set-theory-free proof known so far.

Garside germs for YBE structure groups, and an extension of Ore's theorem (Conference "Groups, Rings and the Yang-Baxter Equation", Spa, June 2017), slides without scrolling (430 kB), or with scrolling (2.8 MB)

We use the connection, due to W. Rump, between the structure groups attached with involutive nondegenerate set-theoretical solutions of the YBE and the right-cyclic law (xy)(xz) = (yx)(yz) to revisit the I-structure and the Garside structure of these groups, and, for each of them, we describe a finite "torsion" quotient exactly playing the role that a Coxeter group plays for the associated Artin-Tits group. In addition, we describe a new approach to the word problem of Artin-Tits groups based on an extension of Ore's classical result about embedding a monoid into a group of fractions. We conjecture that the rewrite system so obtained is "semi-convergent" for all Artin-Tits groups, what would suffice to solve the word problem of the latter.

The world of SD (minicourse) (Conference "Self-distributive system and quandle (co)homology theory in algebra and low-dimensional topology", KIAS, Pusan, June 2017), slides without scrolling (950 kB), or with scrolling (6.5 MB)

The purpose of these minicourses will be to present a general overview of what is known about the "world of SD (self-distributivity)", with a special emphasis on shelves that are not racks. Whether such structures can be useful in topology remains mostly unknown but, at least, it seems a good idea to share what we know so far. The main emphasis will be put on some particular shelves with rich and deep properties, namely (1) the braid shelf (Artin's braid group equipped with a sort of twisted conjugacy operation), (2) the free monogenerated shelf (and its nontrivial syntactic properties and their connection with the Thompson's monoid of SD), (3) the iteration shelf (constructed from an elementary embedding associated with a certain large cardinal in set theory), and (4) the Laver tables (here viewed as finite quotients of the iteration shelf).

Multifraction reduction in Artin-Tits groups (Workshop "Algebraic and geometric combinatorics of Coxeter groups", Montreal, June 2017), slides without scrolling (360 kB), or with scrolling (2.9 MB)

Artin-Tits groups are the braid groups associated with Coxeter groups, and their word problem remains unsolved in the general case. Multifraction reduction is a new rewrite system providing for certain Artin-Tits groups ("FC type") a normal form that extends Ore's fractional decomposition. In the general case, reduction need not give a unique normal form, but massive experiments and partial results support the conjecture that it still solves the word problem. The decidability of the method relies on results by Dyer and Hohlweg about low elements in the underlying Coxeter group, and it is reasonable to think that the main open question ("semiconvergence of reduction") is directly connected with combinatorial properties of the Coxeter group.

Multifraction reduction in Artin-Tits groups (Sevilla, Apr. 2016; Prague, May 2016; Amiens, May 2016; Strasbourg, Jun. 2016; Buenos Aires, Jul. 2016; Newcastle and Warwick, Nov. 2016; Guangzhou, Dec. 2016; Stuttgart, Apr. 2017) slides without scrolling (310 kB), or with scrolling (2.1 MB)

A classical result of Ore says that, if M is a cancellative monoid and any two elements of M admit a least common multiple, that every element of the enveloping group U(M) of M can be represented by a unique irreducible fraction on M. We extend this result by showing that, when common multiples need not exist but a certain "3-Ore condition" is satisfied, every elements of U(M) can be represented by a unique irreducible iterated fraction, leading to a solution of the Word Problem reminiscent of the Dehn algorithm for hyperbolic groups. This applies in particular to Artin-Tits groups of FC-type and, conjecturally, to all Artin-Tits groups.

Garside and quadratic normalisation: a survey (DTL Conference, Liverpool, July 2015), slides without scrolling (570 kB), or with scrolling (3 MB)

Starting from the seminal example of the greedy normal norm in braid monoids, we analyze the mechanism of the normal form in a Garside monoid and explain how it extends to the more general framework of Garside families. Extending the viewpoint even more, we then consider general quadratic normalisation procedures and characterise Garside normalisation among them.

The braid order: history and connection with knots (ILDT Conference, Kyoto, May 2015), slides without scrolling (500 kB), or with scrolling (2.9 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 many solutions for the isotopy problem of braids (N-KOOK Seminar, Osaka, May 2015), slides without scrolling (450 kB), or with scrolling (2.5 MB)

We shall review some of the (many) solutions for the word problem of Artin braids, with a special emphasis on three methods: one algebraic method, the Garside normal form of braids, and two more topological methods, namely Bressaud's algorithm and Dynnikov's coordinates, which both relie on a relaxation principle.

The alternating normal form of braids (Friday Seminar, Osaka City University, may 2015), slides without scrolling (400 kB), or with scrolling (2.2 MB)

Beside Artin's standard "combing normal form" and Garside-Adyan-Morton-Thurston equally well-known "greedy normal form", we develop another natural and simple normal form of braids based on the embedding of (n-1)-strand braids into n-strand braids. This approach is specially well adapted for analyzing the canonical ordering of positive braids and it leads to paradoxically long sequences and, from there (joint work with L.Carlucci and A.Weiermann), to unprovability statements for certain games involving braids.

The group of parenthesized braids (Todai Topology Seminar, Tokyo, May 2015), slides without scrolling (200 kB), or with scrolling (1 MB)

We describe a 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.

Coxeter-like groups for structure groups of set-theoretic solutions of the Yang-Baxter equation (Todai Topology Seminar, Tokyo, May 2015), slides without scrolling (300 kB), or with scrolling (1.1 MB)

We associate with every nondegenerate involutive set-theoretic solution of the Yang-Baxter equation a finite group that plays for the associated structure group the role played by a Coxeter group for the associated Artin-Tits group and its Garside structure. We shall explain the close connection with set-theoretic solutions of YBE, the algebraic law (xy)(xz) = (yx)(yz), I-type monoids, and Garside theory

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.

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.

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.

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 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.

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.

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 (Colloquium, Nantes, oct. 2007), 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.

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.

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.

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".