Quand on étudie un modèle de permutations (ou d’autres objets combinatoires) aléatoires $\sigma_n$, on regarde souvent une propriété donnée, et on cherche à savoir si elle est vérifiée ou non (ou avec quelle probabilité limite) quand la taille de l’objet tend vers l’infini. Dans une optique plus générale, au lieu de s’intéresser à une propriété particulière, on peut considérer un ensemble de propriétés donné. Ici, on travaillera avec la notion de propriétés logiques du premier ordre, venant de la théorie des modèles. Si pour toute propriété $\phi$ de ce type, la probabilité que $\sigma_n$ vérifie $\phi$ a une limite, on dit que $\sigma_n$ satisfait une loi de convergence.

Dans ce cours, après une introduction aux lois de convergence, je discuterai deux résultats sur les permutations aléatoires :
– si $\sigma_n$ est une permutation uniforme évitant le motif 231, alors $\sigma_n$ satisfait une loi de convergence. La preuve utilise de manière cruciale le théorème de Drmota-Lalley-Woods de combinatoire analytique.
– si $\sigma_n$ est une permutation uniforme sans contrainte, alors $\sigma_n$ ne satisfait pas de loi de convergence. La preuve utilise une remarquable méthode d’ « arithmétisation » développée par Shelah et Spencer pour obtenir des résultats similaires sur le graphe d’Erdös-Rényi.

Notes de cours

La génération aléatoire est un outil de choix pour étudier les structures combinatoires et notamment leurs propriétés asymptotiques. Bien qu’il soit parfois possible de concevoir des générateurs ad hoc efficaces pour certaines classes d’objets combinatoires, nous nous intéresserons plutôt aux méthodes de générations dites « automatiques » : la méthode récursive et la méthode de Boltzmann en particulier. Dans les deux cas, il est possible de traduire directement les spécifications combinatoires issues de la méthode symbolique de Flajolet et Sedgewick en algorithmes de génération aléatoire uniforme (tous les objets de même taille ont la même probabilité d’être tirés). Ces deux techniques s’appuient fortement sur l’utilisation des séries génératrices afin de garantir l’uniformité des tirages. Dans le cas de la méthode récursive, on exploitera les coefficients des séries formelles alors que la méthode de Boltzmann s’appuie sur l’évaluation numérique de ces mêmes séries. Durant la séance d’exercices vous pourrez programmer vos propres générateurs suivant l’une ou l’autre de ces méthodes.

Le modèle de dimères représente la répartition de molécules diatomiques sur la surface d’un cristal. Il est modélisé au moyen de couplages parfaits d’un graphe planaire choisis selon la mesure de Boltzmann. Lorsque le graphe est périodique et biparti, Kenyon, Okounkov et Sheffield montrent que le diagramme de phase est donné par la courbe spectrale du modèle, qui a la propriété remarquable d’être de Harnack. Un autre résultat important est la formule locale obtenue par Kenyon pour la mesure de Gibbs d’entropie maximale lorsque le graphe sous-jacent est isoradial et le modèle est critique. Dans une série de papiers avec Cédric Boutillier (Sorbonne université) et David Cimasoni (Université de Genève), nous étendons ces résultats dans un cadre unifié. Nous considérons le modèle sur les graphes minimaux et prouvons une correspondance explicite avec l’ensemble des courbes de Harnack; nous démontrons aussi des formules locales pour une famille à deux paramètres de mesure de Gibbs. Le premier exposé consistera en une introduction au modèle de dimères; le deuxième sera consacré à nos travaux récents avec Cédric Boutillier et David Cimasoni.