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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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