Universite Paris Diderot Paris et Universite Bordeaux I

De
Publié par

Niveau: Supérieur
Universite Paris.Diderot (Paris 7) et Universite Bordeaux I UFR d'Informatique These pour l'obtention du diplome 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-Franc¸ois LE GALL Examinateur Jean MAIRESSE Directeur de these Jean-Franc¸ois MARCKERT Directeur de these Gilles SCHAEFFER Rapporteur

  • ıdes

  • personnes du liafa, de pps et du labri

  • mono

  • tresses

  • universite bordeaux

  • ıde des empilements de pieces

  • equivalence entre empilements

  • seances de travail parti


Publié le : lundi 1 décembre 2008
Lecture(s) : 39
Source : lix.polytechnique.fr
Nombre de pages : 188
Voir plus Voir moins

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 . . . . . . . 83
5.3 Convergences des cha^nes de Markov cycliques . . . . . . . . . . . 83
6 Resultats d’enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.1 La famille de reseaux (L ) . . . . . . . . . . . . . . . . . . . . 85R R⊂N
6.2 Le reseau triangulaire . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.3 La famille de reseaux T . . . . . . . . . . . . . . . . . . . . . . . . 91n
II Des cartes planaires 95
3 Comportement asymptotique de cartes planaires en pile 97
1 Cartes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
1.1 Quelques rappels sur les graphes . . . . . . . . . . . . . . . . . . . 98
1.2 Cartes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
1.3 Enumeration de cartes planaires . . . . . . . . . . . . . . . . . . . 101
2 Convergence de cartes planaires aleatoires . . . . . . . . . . . . . . . . . . 102
2.1 Topologie de la convergence locale . . . . . . . . . . . . . . . . . . 102
2.2 Topologie de Gromov-Hausdor . . . . . . . . . . . . . . . . . . . . 103
2.3 Petit historique des resultats de convergence . . . . . . . . . . . . 104
3 Triangulations en pile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.1 De nition des triangulations en pile . . . . . . . . . . . . . . . . . 105
3.2 Lois de probabilites sur les triangulations en pile . . . . . . . . . . 105
3.3 Petit historique sur la convergence des triangulations en pile . . . 106
3.4 Triangulations en pile et arbres ternaires . . . . . . . . . . . . . . . 106
4 Arbres aleatoires et convergence . . . . . . . . . . . . . . . . . . . . . . . . 107
4.1 Rappels sur les arbres planaires . . . . . . . . . . . . . . . . . . . . 107
4.2 Arbres de Galton-Watson . . . . . . . . . . . . . . . . . . . . . . . 108
4.3 Convergence locale des arbres ternaires . . . . . . . . . . . . . . . 109
4.4 Arbre continu d’Aldous . . . . . . . . . . . . . . . . . . . . . . . . 110
5 Triangulations en pile et arbres ternaires . . . . . . . . . . . . . . . . . . . 112
5.1 Bijection entre les triangulations en pile et les arbres ternaires . . 112
5.2 Distance dans la triangulation . . . . . . . . . . . . . . . . . . . . 113
5.3 Loi induite sur les arbres . . . . . . . . . . . . . . . . . . . . . . . 114
6 Comportement asymptotique des triangulations en pile sous la loi uniforme115
6.1 Convergence pour Gromov-Hausdor . . . . . . . . . . . . . . . . . 115
6.2 Convergence locale sous la loi uniforme . . . . . . . . . . . . . . . 116
6.3 Comportement asymptotique du degre sous la loi uniforme . . . . 118Table des matieres vii
7 Comportement asymptotique des triangulations en pile sous la loi historique118
7.1 Convergence comme espace metrique . . . . . . . . . . . . . . . . . 118
7.2 Comportement asymptotique du degre de la racine . . . . . . . . . 119
8 Quadrangulations en pile . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
8.1 Un premier modele de quadrangulations en pile . . . . . . . . . . . 120
8.2 Un modele de quadrangulations en pile proche des arbres binaires 121
4 Some families of increasing planar maps 123
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
1.1 Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
1.2 Literature about stack-triangulations . . . . . . . . . . . . . . . . . 126
1.3 Literature about convergence of maps . . . . . . . . . . . . . . . . 127
2 Stack-triangulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
2.1 Planar maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
2.2 Formal construction of stack-triangulations . . . . . . . . . . . . . 129
2.3 Combinatorial facts . . . . . . . . . . . . . . . . . . . . . . . . . . 131
2.4 Induced distribution on the set of ternary trees . . . . . . . . . . . 137
3 Topologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
3.1 Topology of local convergence . . . . . . . . . . . . . . . . . . . . . 138
3.2 Gromov-Hausdor topology . . . . . . . . . . . . . . . . . . . . . . 138
4
4 Local convergence of stack-triangulations under U . . . . . . . . . . . . 1392n
4.1 Galton-Watson trees conditioned by the size . . . . . . . . . . . . . 139
4.2 Local convergence of uniform ternary trees . . . . . . . . . . . . . 140
4.3 Local convergence of stacked-triangulations . . . . . . . . . . . . . 140
5 Asymptotic under the Gromov-Hausdor topology . . . . . . . . . . . . . 143
5.1 Gromov-Hausdor convergence of rescaled GW trees . . . . . . . . 144
5.2 Gromov-Hausdor convergence of stack-triangulations . . . . . . . 145
6 Asymptotic behavior of the typical degree . . . . . . . . . . . . . . . . . . 147
47 Asymptotic behavior of stack-triangulations under Q . . . . . . . . . . . 1502n
7.1 Poisson-Dirichlet fragmentation . . . . . . . . . . . . . . . . . . . . 152
47.2 Some features of large maps under Q . . . . . . . . . . . . . . . . 154
8 Two families of increasing quadrangulations . . . . . . . . . . . . . . . . . 156
8.1 A rst model of growing quadrangulations . . . . . . . . . . . . . . 156
8.2 A family of stack-quadrangulations . . . . . . . . . . . . . . . . . . 157
08.3 The function Λ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
9 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
9.1 Proof of the Theorems of Section 5 . . . . . . . . . . . . . . . . . . 162
Bibliographie 176
Index 177
Index des notations 179viii Table des matieresIntroduction
Cette these est formee de deux parties independantes. La premiere se situe dans le
domaine de la combinatoire enumerative et la seconde dans le domaine des grandes cartes
planaires aleatoires qui forme une branche de la theorie des probabilites. Si les liens entre
ces deux domaines ne sont pas evidents a premiere vue, nous allons neanmoins essayer de
montrer que ceux-ci sont nombreux en illustrant sur des exemples varies les interactions
fructueuses entre la combinatoire et les probabilites.
Quelques interactions entre combinatoire et probabilites
Combinatoire enumerative
La combinatoire est l’etude de la structure d’objets discrets. Le premier probleme
auquel on s’interesse est l’enumeration de tels objets : c’est le sujet de la combinatoire
enumerative. Quel que soit le contexte dans lequel un probleme d’enumeration appara^ t,
le cadre est toujours a peu pres le suivant. Un ensembleA d’objets est donne tel qu’a
chaque objet deA est associee une taille sous forme d’un entier naturel. On suppose
que la taille est une fonction su samment discriminante pour qu’il n’y ait qu’un nombre

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi