Journées MAS et Journée en l'honneur de Jacques Neveu

31 août - 3 septembre 2010 à Bordeaux

 
 
 

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 :

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.