Universite Paris Diderot Paris et Universite Bordeaux I

Universite Paris.Diderot (Paris 7) et Universite Bordeaux I
UFR d’Informatique
These
pour l’obtention du dipl^ome de
Docteur de l’Universite Paris Diderot, specialite informatique
Tresses, Animaux, Cartes : A
l’interaction entre combinatoire et
probabilite
presentee et soutenue publiquement par
Marie Albenque
le 3 decembre 2008
devant le jury compose de
Christian CHOFFRUT Examinateur
Patrick DEHORNOY Examinateur
Christian KRATTENTHALER Rapporteur
Jean-Fran cois LE GALL Examinateur
Jean MAIRESSE Directeur de these
Jean-Fran cois MARCKERT Directeur de these
Gilles SCHAEFFER Rapporteuriii
Tout au long de cette these, Jean a su me guider et m’encourager. J’ai trouve dans
ses nombreuses questions et son sens du detail un moteur stimulant notamment lors de
la redaction de ce manuscrit, je l’en remercie chaleureusement.
Je ne remercierai jamais assez Jean-Fran cois d’avoir accepte de relever le de que
constituait l’encadrement de cette these a distance. Sa reactivite et ses qualites peda-
gogiques telephoniques m’ont bien souvent fait oublier les 600kms qui separent Paris de
Bordeaux. Le plus remarquable lorsque l’on travaille avec Jean-Fran cois, outre ses quali-
tes indeniables de chercheur, est sa foi en les «belles mathematiques» qui s’accompagne
d’un enthousiasme communicatif : il n’en fallait pas moins pour maintenir au top mon
moral souvent vacillant! Pour tous ses conseils, ses encouragements et son soutien sans
faille, je lui temoigne aujourd’hui ma profonde gratitude et une amitie sincere.
Je remercie vivement Gilles Schae er et Christian Krattenthaler d’avoir pris le temps
de lire mon manuscrit et de participer au jury de cette these. Je remercie egalement Gilles
de m’avoir invitee a mes premieres journees alea qui m’ont de nitivement convertie aux
probabilites discretes et de m’avoir ensuite donne a plusieurs reprises l’occasion d’exposer
mes travaux au lix.
Ma decouverte des probabilites s’est deroulee sous les meilleurs auspices grace^ au
cours de Jean-Francois Le Gall «Integration et Probabilites» et a son encadrement de
mon memoire de ma^trise qui reste un de mes meilleurs souvenirs de ma scolarite a l’ens.
Ses conseils avises m’ont ete tres precieux tout au long de mes etudes ; c’est un veritable
honneur de le voir participer a ce jury.
Patrick Dehornoy m’a invite a Caen pour presenter mes resultats devant une assem-
blee d’algebristes, sa gentillesse a eu raison de mes angoisses devant une telle invitation.
Ses grandes qualites pedagogiques et ses nombreux conseils sont parvenus a faire de la
redaction de sa «lcone » sur les tresses un exercice agreable et m’ont rendu bien des ser-
vices lors de la redaction de ce manuscrit. Je le remercie chaleureusement d’avoir accepte
de participer au jury de cette these.
Je remercie vivement Christian Cho rut d’avoir accepte de participer a ce jury de
these.
Philippe a reussi a trouver a mes resultats des consequences algebriques dont j’etais
loin de soupconner l’existence et a me supporter comme co-auteure : je ne sais pas ce
qui est le plus remarquable, mais l’en remercie egalement! Son enthousiasme, son sens de
l’humour et sa capacite a trouver des bijections ont rendu nos seances de travail parti-
culierement agreables.
Noelle Delgado et Michele Wasse ont su aplanir toute les di cultes administatives
que j’ai pu rencontrer au cours de cette these ; je ne saurai les remercier assez de leur
disponibilite et de leur e cacite.iv
Je remercie egalement toutes les personnes du liafa, de pps et du labri qui font
de ces labos des endroits ou il fait bon travailler. Une pensee toute particuliere a la ne
equipe de redacteurs de l’ete : Sylvain, Samuel et Nicolas qui ont transforme la corvee
de redaction estivale en un moment (presque) agreable et a Christine et Severine pour
nos discussions de «lles» au milieu de tous ces informaticiens et, par ordre d’appari-
tion, merci a Laura, Mathias, Fabien, Samuel, Mathilde, Philippe, Claire, Glenn, Cezara,
Constantin et a tous ceux que j’oublie : bonne route a tous!
M^eme si j’ai passe l’essentiel de mon temps a Paris, je n’oublie pas les Bordelais qui
m’ont chaleureusement accueillie a chacune de mes visites au labri.
Mes aller-retour Paris-Bordeaux ont ete rendus possibles et agreables par Patrick
qui a accepte de m’heberger a chacune de mes visites et qui en a pro te pour me faire
decouvrir la scene musicale bordelaise : merci !
La n de la redaction | moment critique en soi | aurait pu tourner a la catastrophe,
si je n’avais pu compter sur le soutien indefectible de toute la Marx Do family qui m’a une
fois de plus hebergee alors que je me retrouvais sans-abri : Antoine, Benjamin, Corentin,
Jeremie, Julien, Sylvain, Thomas, merci d’avoir supporte le squattage regulier de votre
canape. Un enorme merci egalement a Carole, Elise et Vincent sans qui le desencrassage
de mon appartement aurait ete bien di cile.
Il reste bien des personnes sans qui ces trois annees auraient ete plus ternes : Lucas,
mon bin^ ome de probas de toujours, les violettes devenues vertes avec le temps et tout
particulierement Nath et Caro, les membres de grenat qui ont presque reussi a me faire
aimer la geologie et tous les autres : Cyril, Faustine, Joe, Juliette, Laure, Laurent, Ma-
thieu, Mathilde, Stephane, Tali,. . .
Il manque evidemment a cette liste toute ma famille aupres de laquelle je suis assuree
de trouver un reconfort et un soutien constant : mon pere, mes s urs Elise et Pauline,
mon frere Etienne et bien su^r ma mere qui m’a toujours encouragee, stimulee et soutenue
dans mes choix durant toutes mes etudes et bien avant.Table des matieres
Introduction 1
I Des tresses et des animaux 15
1 Combinatoire de monodes 17
1 Inventaire : monodes, poset et fonction de Mobius . . . . . . . . . . . . 18
1.1 Rappels sur les monodes . . . . . . . . . . . . . . . . . . . . . . . 18
1.2 Les POSET et la fonction de Mob ius . . . . . . . . . . . . . . . . . 22
2 Monode des empilements de pieces . . . . . . . . . . . . . . . . . . . . . . 25
2.1 Empilements de pieces . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Equivalence entre empilements et monodes de Cartier-Foata . . . 27
2.3 Enumeration d’empilements . . . . . . . . . . . . . . . . . . . . . . 28
3 Enumeration de tresses positives . . . . . . . . . . . . . . . . . . . . . . . 30
3.1 Presentation du monode de tresses . . . . . . . . . . . . . . . . . . 30
3.2 De nition d’un ensemble de tresses «triviales» . . . . . . . . . . . 31
3.3 Serie de croissance des tresses positives . . . . . . . . . . . . . . . 32
+3.4 De nition d’une involution sur T×B . . . . . . . . . . . . . . . 33
4 Extension a une classe de monodes . . . . . . . . . . . . . . . . . . . . . . 34
4.1 Preuve du theoreme 1.28 . . . . . . . . . . . . . . . . . . . . . . . 36
4.2 Preuve du corollaire 1.29 par inclusion-exclusion . . . . . . . . . . 37
4.3 Quelques exemples de monodes . . . . . . . . . . . . . . . . . . . . 38
5 Application aux monodes de tresses duaux . . . . . . . . . . . . . . . . . 39
+?5.1 Presentation de B . . . . . . . . . . . . . . . . . . . . . . . . . . 40n
+?5.2 Un peu d’arithmetique dans B . . . . . . . . . . . . . . . . . . . 41n
5.3 Des con gurations d’ar^etes aux for^ets alternantes non-croisees . . . 42
5.4 For^ets alternantes-non croisees et arbres unaires-binaires . . . . . . 44
5.5 Ou l’on retrouve la fonction de Mobius . . . . . . . . . . . . . . . . 47
6 Perspectives et problemes ouverts . . . . . . . . . . . . . . . . . . . . . . . 49
6.1 Hauteur des empilements . . . . . . . . . . . . . . . . . . . . . . . 49
6.2 Combinatoire du groupe . . . . . . . . . . . . . . . . . . . . . . . . 51
6.3 Tresser aleatoirement . . . . . . . . . . . . . . . . . . . . . . . . . 57
2 Gaz markoviens et enumeration d’animaux diriges 61
1 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
1.1 Terminologie sur les graphes . . . . . . . . . . . . . . . . . . . . . 62
1.2 Animal : De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
1.3 Quelques rappels de percolation . . . . . . . . . . . . . . . . . . . . 64
1.4 Animaux et percolation . . . . . . . . . . . . . . . . . . . . . . . . 66vi Table des matieres
2 Animaux diriges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.1 De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.2 Premiers resultats d’enumeration d’animaux diriges . . . . . . . . 68
2.3 Animaux diriges et modeles de gaz . . . . . . . . . . . . . . . . . . 69
2.4 Animaux diriges et empilements . . . . . . . . . . . . . . . . . . . 71
3 Modeles de gaz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.1 Modele de gaz sur un cylindre . . . . . . . . . . . . . . . . . . . . . 73
3.2 Modele de gaz sur le graphe entier . . . . . . . . . . . . . . . . . . 76
4 Convergence de graphes et animaux . . . . . . . . . . . . . . . . . . . . . 79
4.1 De nition d’une topologie sur les graphes marques . . . . . . . . . 80
4.2 Compatible avec les animaux . . . . . . . . . . . . . . . . . . . . . 81
5 Cha^nes de Markov cycliques et animaux . . . . . . . . . . . . . . . . . . . 82
5.1 De nition des cha^nes de Markov cycliques . . . . . . . . . . . . . 82
5.2 Premieres proprietes des cha^ nes de Markov cycliques . .