Journées MAS 2010

Etude probabiliste de structures combinatoires (pdf)

Session organisée par Jean-François Marckert (Université Bordeaux 1)

La combinatoire consiste en l'étude des structures discrètes, comme par exemple, les chemins, les graphes, les arbres, les quadrangulations, les tableaux de Young, les pavages d'une région du plan par des polygones, automates, certaines matrices aléatoires... Etudier une famille d'objets combinatoires consiste premièrement à comprendre la structure des objets, les décomposer si possible, compter combien d'objets de taille n existent, chercher des bijections entre notre famille et d'autres familles bien étudiées, etc. Lorsque cela est possible on s'intéresse également à des paramètres des ces objets (par exemple, la hauteur des arbres à n noeuds). En terme probabiliste, on munit la famille des objets de taille n de la loi uniforme, ou d'une autre loi, et on regarde la moyenne, ou la distribution, exacte ou limite, du paramètre en question ; ce paramètre n'est rien de plus (ni de moins) qu'une variable aléatoire.
L'étude des structures combinatoires par le truchement des probabilités apporte beaucoup à la compréhension des objets combinatoires :

elle donne une explication souvent simple à des phénomènes observés uniquement par des simulations, ou par des calculs fort compliqués,

elle permet la description globale de certains objets limites (par exemple, les chemins composés de +1 et -1 de taille n normalisés convergent vers le Brownien, les arbres binaires à n noeuds, normalisés, convergent vers un arbre continu "Brownien"; il s'agit d'une convergence de l'objet global). Ceci est l'apanage des méthodes probabilistes.

elle permet une approche discrète des objets continus,

elle permet d'ajouter parfois une composante temporelle dans l'étude des objets combinatoires (par exemple, on construit un arbre en ajoutant successivement des noeuds... au lieu de regarder la loi de l'arbre t_n de taille n obtenu seulement, on peut dire des choses sur la suite (t_k), donnant une description des phénomènes en jeu beaucoup plus claire).

Dans les exposés de la session, les orateurs vont illustrer ces liens riches qui existent entre combinatoire et probabilité.

Exposé de 40 minutes Charles Bordenave (CNRS, Université de Toulouse) Combinatoire sur des structures aléatoires transparents

Sur un graphe fini, il existe de nombreux objets combinatoires dignes d'intérêt : ses arbres couvrants, ses appariements, ses ensembles stables, ses cycles et ainsi de suite. Dénombrer ces objets n'est pas évident d'un point de vue algorithmique. En revanche, la situation se simplifie si au lieu d'un graphe donné on considère un graphe aléatoire. Lorsque la taille du graphe aléatoire tend vers l'infini, il est parfois possible de calculer les limites d'échelle de ces objets combinatoires et obtenir des formules asymptotiques.
Dans cet exposé, nous présenterons des problèmes ouverts et des résultats récents dans cette direction. Nous discuterons notamment un travail récent avec Marc Lelarge et Justin Salez sur les appariements.

Exposé de 20 minutes Cédric Boutillier (LPMA, Université Pierre et Marie Curie) Produit de valeurs d'une courbe de Harnack sur un tore et asymptotiques de fonctions de partition de dimères transparents

Un modèle de dimères sur un graphe plan biparti périodique est un modèle de mécanique statistique exactement soluble, pour lequels de nombreuses quantités peuvent s'exprimer à l'aide du polynôme caractéristique associé P(z,w). Kenyon et Okounkov ont démontré que les polynômes caractéristiques de tels modèles de dimères sont exactement les polynômes définissant les courbes de Harnack, des courbes algébriques aux propriétés de maximalité très intéressantes. Je donnerai une formule asymptotique pour le produit de valeurs d'un tel polynôme P pour z et w des racines n-ièmes. J'en déduirai des informations probabilistes pour les modèles de dimères sur des grands tores (comme la distribution du nombre d'enroulement) mais aussi pour d'autres modèles : le modèle d'Ising et les forêts couvrantes enracinées sur des cycles.

Exposé de 20 minutes Lucas Gerin (Modélisation aléatoire de Paris Ouest Nanterre La Défense) Règle de minorité : aspects probabilistes transparents

Pour un graphe G, la règle de minorité sur G est le processus à valeurs dans {0,1}^G défini de la façon suivante : à chaque instant on tire certains sites au hasard, et on met chacune dans l'état qui est minoritaire dans son voisinage.
On s'est rendu compte récemment dans la communauté algorithmes/combinatoire que des questions très simples (existence de points fixes, temps d'atteinte) sur des graphes très simples (grille finie ou infinie, arbres, cercle, ...) pouvaient poser des problèmes très jolis, liés à des thèmes connus en probabilités : transitions de phase, percolation, interactions entre marches aléatoires, etc. J'essaierai d'expliquer ces liens.

Exposé de 20 minutes Laurent Ménard (Laboratoire de Probabilités) Cartes infinies uniformes du plan transparents

Nous allons présenter différents types de cartes planaires aléatoires infinies, qui sont des limites locales de cartes planaires aléatoires finies. Nous verrons que certaines propriétés de ces objets peuvent être étudiées par des méthodes bijectives, à l'instar de la carte brownienne. Nous verrons aussi comment un procédé d'échantillonnage par faces permet d'étudier la percolation sur ces cartes infinies aléatoires.