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.

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.

Pendant cet exposé je donnerai un aperçu des méthodes galoisiennes appliquées aux équations fonctionnelles, afin de présenter des résultats sur la nature de certaines séries génératrices issues de la combinatoire, et en particulier de la combinatoire énumérative, récemment obtenus par plusieurs auteurs. L'objectif est de donner l'intuition du principe commun de ces preuves.

Si l'hypothèse P\neq NP a pour conséquence que les problèmes NP-difficiles ne sont pas résolubles en temps polynomial, l'obtention de résultats négatifs plus précis nécessite le recours à des hypothèses plus fortes. Dans cet exposé, nous présenterons certains résultats négatifs (bornes inférieures de complexité) obtenus à partir des hypothèses ETH (exponential time hypothesis) et SETH (strong exponential time hypothesis). Il y sera question de SAT, de graphes, de complexité (classique et parfois paramétrée), de problèmes difficiles mais aussi de problèmes polynomiaux.

A travers des exemples applicatifs, j’expliquerai comment l’approche champ moyen permet d’analyser les grands réseaux stochastiques. Si le fait que les états d’un nombre fini de noeuds du réseau deviennent indépendants à la limite est connu, je montrerai comment certaines interactions disparaissent aussi à la limite. Je parlerai sur des exemples du problème d'unicité du point d’équilibre de la limite champ moyen, et d’autres avancées récentes.

Les mélanges de cartes ont été étudiés en détail aussi bien du point de vue pratique que mathématique. Un résultat célèbre de Diaconis et Bayer dit essentiellement que 7 mélanges suffisent pour qu'un jeu de 52 cartes soit bien mélangé (c'est-à-dire, la mesure de probabilité sur les différentes permutations est presque la mesure uniforme). Du point de vue algébrique, ceci est relié à l'existence d'une sous-algèbre de l'algèbre du groupe symétrique, appelée algèbre des descentes. De nombreuses notions différentes de mélanges peuvent être traitées via une construction géométrique de Bidigare, Hanlon et Rockmore. Je ferai un survol de cette approche ainsi que de quelques résultats plus récents.

We introduce a family of geometrical lattice models generalising the well-known loop model on the hexagonal lattice. These models have a $U_q(sl_n)$ quantum group symmetry, the loop model being the $n=2$ case. The general models give rise to branching webs and describe, at a special point, the interfaces in $Z_n$ symmetric spin models. We mainly discuss the $n=3$ case of bipartite cubic webs, which is based on the Kuperberg $A_2$ spider. We exhibit a local vertex-model reformulation, analogous to the well-known correspondence between the loop model and the nineteen-vertex model. The local formulation allows us in particular to study the model by means of transfer matrices and conformal field theory. We find that it has a rich phase diagram, including a dense and a dilute phase that generalise those known for the loop model. Based on joint work with Augustin Lafay and Azat Gainutdinov (arXiv:2101.00282 and 2107.10106).

We consider a class of multiple-drawing opposite-reinforcing urns with time-dependent replacement rules. The class has the symmetric property of a Friedman-type urn. We divide the class into a small-increment regime and a large-increment regime. For small-increment schemes, we prove almost-sure convergence and a central limit theorem for the proportion of white balls by stochastic approximation. For large-increment schemes, by assuming the affinity condition, we show almost-sure convergence of the proportion of white balls by martingale theory and present a way to identify the limit distribution of the proportion of white balls.

Soient R_0, B_0 et (X_n)n∈N^∗ des variables aléatoires indépendantes, de loi uniforme sur [0, 1]^d. On pense à R_0 (resp. B_0) comme un point initial rouge (resp. bleu), puis on imagine que X_1, X_2, . . . tombent consécutivement dans l’hypercube, et on fait prendre à chaque point qui arrive la couleur du point le plus proche déjà tombé. Cela fournit un coloriage de [0, 1]^d, et on s’intéresse aux propriétés de la frontière rouge/bleu à la limite. Dans un travail en commun avec Anne-Laure Basdevant, Nicolas Curien et Arvind Singh, nous montrons que la dimension de Hausdorff de la frontière est comprise entre (d − 1) et d strictement, répondant positivement à une conjecture d’Aldous.

En 2012, Addario--Berry, Broutin, et Goldschmidt ont montré que les composantes connexes des graphes d'Erd\"os--Rényi critique convergent vers des graphes continus limites (taille+GHP). Ces résultats ont ensuite été généralisés pour divers graphes, dont le modèle de configuration et les graphes multiplicatifs. Dans cet exposé, je présenterai comment étendre ces limites pour la percolation par arête sur l'hypercube. Notre approche est totalement nouvelle, et est basée sur une comparaison entre percolation, coalescent multiplicatif, et graphe multiplicatif. (Travail en cours avec Nicolas Broutin et Asaf Nachmias)

Walks confined to a cone have been studied for a long times, as a lot of combinatorial objects reduce to the study of such walks (mainly maps). More specifically, their systematic study started around ten years ago, and their classification is complete in some cases, as for small steps in the quarter plane, using a wide range of mathematics. The framework of this talk is the extension to this classification to large steps models in the quarter plane. As an illustration of the methods that can be used, the first proof of the algebraicity of some large steps models is presented. Les marches confinées dans un cône ont été étudiées depuis longtemps, car beaucoup d’objets combinatoire s’y réduisent (notamment des familles de cartes). Plus précisément, leur étude systématique qui a débuté il y a une dizaine d’années donne lieu à une classification dans certains cas, par exemple celle des petits pas dans le quart de plan, qui fait appel à des domaines mathématiques très variés. Cet exposé se situe dans le contexte d’une extension de cette classification aux modèles à grands pas. Comme illustration des méthodes qui peuvent être utilisées dans le cadre de cette classification, la première preuve d’algébricité de deux de ces modèles à grands pas sera présentée.

En 2006, F. Chapoton a établi que le nombre d'intervalles dans un certain poset défini sur les chemins de Dyck de longueur 2n, appelé treillis de Tamari, était aussi le nombre de triangulations de taille n. Ce phénomène a ensuite été expliqué bijectivement par Bernardi et Bonichon. Plus tard, le dénombrement de ces intervalles a été généralisé à une famille de treillis dits de m-Tamari (ici, m désigne un entier), par É. Fusy et L.-F. Préville-Ratelle et l'oratrice. Pour un m général, les nombres restent très simples, mais ne sont pas connus pour compter des cartes. Nous montrerons en revanche, que si on considère un ordre de m-Tamari ``glouton'', alors le nombre d'intervalles est bien le nombre de certaines cartes, connues sous le nom de (m+1)-constellations. Notre preuve est récursive, et procède par équations fonctionnelles. Une preuve bijective reste à construire. Il s'agit d'un travail en commun avec Frédéric Chapoton (Strasbourg).

La combinatoire énumérative et bijective des cartes est un sujet classique à Aléa. Une nouvelle approche bijective, la décomposition en tranches, a été introduite il y a quelques années. Elle consiste à découper les cartes le long de géodésiques, ce qui permet de les décomposer récursivement comme des arbres, mais aussi de faire de nouvelles opérations analogues à des manipulations de surfaces continues. Dans un travail en cours avec Marie Albenque, nous étendons la décomposition en tranches aux «hypercartes» (cartes munies d'un bicoloriage propre des faces). Ceci nous permet de donner des preuves bijectives de formules provenant de la physique théorique.

On considère deux arbres binaires dont les feuilles sont étiquetées de 1 à n. Quelle est la taille du plus grand ensemble d'étiquettes telle que la généalogie de ces étiquettes est la même dans les deux arbres ? Dans le cas où les deux arbres sont aléatoires uniformes et indépendants, un argument brutal montre que cette taille est au plus en racine carrée de n. On montre que cette borne n'est en fait pas optimale. De manière peut-être un peu surprenante, le problème est relié à l'étude de la régularité des homéomorphismes entre deux arbres Browniens indépendants. Travail en cours avec Delphin Sénizergues.

The paradox of Condorcet (1785) is a phenomenon that occurs when people express their preferences amongst candidates. Calculating the limiting probability of the Condorcet paradox can be done by probabilistic methods. Krishnamoorthy and Raghavachari (2005) in particular, found results for the General Independent Culture. During this talk, I will first introduce some required knowledge in social choice theory and explain the problem. Then, I will give an intuition on Krishnamoorthy and Raghavachari (2005) work. Finally, I will present an analytic combinatorics method that permits to obtain the same kind of results. References: Marie Jean Antoine Nicolas de Caritat, marquis de Condorcet. Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. Imprimerie royale, 1785. Mukkai Krishnamoorthy and Madabhushi Raghavachari. Condorcet winner probabilities - A statistical perspective, 2005. URL https://arxiv.org/abs/math/0511140.

Cet exposé porte sur l’étude de la taille de l’arbre de fragmentation associé à un processus de fragmentation bidimenn- sionnel dont une particule d’une forme rectangulaire de cotés (x,y) subit à des divisions successives selon un certain vecteur aléatoire (U,V) et une probabilté de dislocation qui dépend de (x,y). Notre processus s’arrêtera presque surement en lais- sant lieu à un nombre fini de sous-rectangle. On note N(x,y) le nombre total des sous-rectangles instables. N(x,y) satisfait une équation en loi multidimensionnelle dont on décrit la solution dans un cadre général. De plus, l’espérance m(x,y) et la variance σ^2(x,y) de N(x,y) satisfont deux équations de renouvellement bi-variée dont on a besoin d’une approximation de la fonction densité de renouvellement pour établir les approximations de m(x,y) et σ^2(x,y) le long d’une ligne bien déterminée et de décrire le comportement asymptotique de N(x,y)

The enumeration of linear λ-terms has attracted quite some attention recently, partly due to their link to combinatorial maps. Zeilberger and Giorgetti (2015) gave a recursive bijection between planar linear normal λ-terms and planar maps, which, when restricted to 2-connected λ-terms (i.e., without closed sub-terms), leads to bridgeless planar maps. Inspired by this restriction, Zeilberger and Reed (2019) conjectured that 3-connected planar linear normal λ-terms have the same counting formula as bipartite planar maps. In this talk, we settle this conjecture by giving a direct bijection between these two families. Furthermore, using a similar approach, we give a direct bijection between planar linear normal λ-terms and planar maps, whose restriction to 2-connected λ-terms leads to loopless planar maps. This bijection seems different from that of Zeilberger and Giorgetti, even after taking the map dual. We also explore enumerative consequences of our bijections.

La technique d’origami ADN permet de concevoir des nanostructures à partir de brins d’ADN qui s’auto-assemblent en une forme voulue. Cette technique utilise la spécificité de l’appariement de deux séquences d’ADN complémentaires : le principe est de replier un long brin d’ADN naturel en le mélangeant à de courtes “agrafes” d’ADN synthétiques; en refroidissant, les agrafes relient certaines régions du long brin entre elles et produisent la forme voulue. Bien que cette méthode soit très efficace en pratique, le processus d’auto-assemblage de l’origami est encore mal compris. Nous commençons par présenter des résultats expérimentaux qui démontrent qu'il est possible de contrôler mathématiquement la correction de l'assemblage de ces structures l'aide d'un programme linéaire. Nous proposons ensuite un modèle probabiliste de la séquence d’événements aboutissant à la formation de cet origami. En utilisant la méthode de Monte-Caro cinétique, cela nous permettra de simuler et d’étudier en détails le processus de repliement d’un origami d’ADN et ainsi de mieux comprendre comment utiliser et améliorer cette méthode dans la pratique.

Il est bien connu que le nombre de permutations de taille N avec des positions de descentes fixées peut s'écrire sous la forme d'un joli déterminant. Dans une collaboration en cours avec Natasha Blitvić et Einar Steingrímsson, on veut faire la même combinatoire, mais en remplaçant les descentes par un motif consécutif. On montre que certains de ces motifs font apparaître les moments des lois classiques venant des probabilités libres (la loi semi-circulaire, les lois de Bessel libres etc.).

Un langage algébrique est dit intrinsèquement ambigu si toute grammaire qui le reconnaît est ambiguë : elle génère au moins un mot de deux manières différentes. Décider l'intrinsèque ambiguïté d'un langage algébrique est un problème difficile, indécidable en général. Les premiers exemples de langages intrinsèquement ambigus ont été découverts dans les années 1960, en utilisant des techniques d'itération sur les arbres de dérivation. Ils appartenaient à une sous-famille particulière de langages algébriques, les langages algébriques bornés. Bien qu'elles aient permis de prouver l'intrinsèque ambiguïté de plusieurs langages, comme par exemple le langage L = a^n b^m c^p avec n=m ou m=p, les techniques d'itération restent très laborieuses à mettre en œuvre, sont très spécifiques au langage étudié, et semblent même parfois inadaptées. Par exemple, la relative simplicité de la preuve de l'intrinsèque ambiguïté de L s'effondre complètement en remplaçant la contrainte "n=m ou m=p" par "n≠m ou m≠p". Dans cet exposé, je présenterai deux critères utiles basés sur les séries génératrices pour prouver facilement l'intrinsèque ambiguïté de certains langages algébriques bornés. Ces langages, qui ont une série génératrice rationnelle, résistaient à la fois aux techniques d'itération classiques développées dans les années 1960 et aux méthodes analytiques introduites par Philippe Flajolet en 1987.

TBA

We shall take a look at a new type of lattice paths, called "Dyck paths with air pockets". After getting acquainted with them, we shall see how they are related to all sorts of combinatorial objects, such as other, classical lattice paths or certain integer compositions.

Les fonctions de parking sont des objets centraux de la combinatoire énumérative et algébrique. Nous généralisons l'algorithme qui les définit pour obtenir une large classe d'algorithmes "bilatères". Si un tel algorithme A vérifie certaines propriétés locales, les fonctions de A-parking de taille r associées sont "universellement" comptées par (r+1)^(r-1). Nous expliquerons également comment ces algorithmes sont liés aux arbres binaires, et étendrons nos résultats à un cadre probabiliste.

Le but de cet exposé sera de donner une introduction aux fonction polyharmoniques discrètes et d’illustrer quelques questions naturelles. Je commencerai par le problème combinatoire qui était le point de départ de l’étude de ces fonctions; c’est à dire le comptage des chemins dans le quart de plan. Ensuite, je vais parler sur quelques propriétés basiques de fonctions polyharmoniques, et donner un aperçu comment on peut les calculer. Au final, je vais parler de la classification, en particulier s’il est possible de décider quelles de nos fonctions pourraient vraiment apparaître dans une expansion asymptotique.

We propose a new method for obtaining the coefficients of complete asymptotic expansions in a sys- tematic way, which is suitable for various graph families. The core idea is to introduce a new kind of (bivariate) generating series for the expansion coefficients, which we call a coefficient generating function. In this talk, we show that coefficient generating functions satisfy some general properties that allow to express asymptotics in a short closed form and give a combinatorial meaning to their coefficients. Applications of our method include calculating asymptotics of connected graphs, irreducible tournaments, strongly connected digraphs, satisfiable 2-SAT formulae and contradictory strongly connected 2-SAT formulae. Moreover, for each of the above cases, we obtain expressions for the cases with a fixed number of connected, irreducible, strongly connected and contradictory components, respectively. This is joint work with Sergey Dovgal.

Directed Acyclic Graphs (DAGs) are directed graphs in which there is no path from a vertex to itself. They are an omnipresent data structure in computer science and the problem of counting the DAGs of given number of vertices has been solved in the 70's by Robinson. In this talk, I will introduce a new class of DAGs (DOAGs for Directed Ordered Acyclic Graphs), endowed with an independent ordering of the children of each vertex. They offer a new modelling tool for objects arising from the compaction of tree-like structures. For this class I will describe a recursive decomposition scheme that is amenable to effective random sampling with control over the number of edges. I will also present an optimised uniform sampler, for the case when the number of edges is free, whose design follows naturally from our asymptotic enumeration results.

Le modèle de corner percolation a été introduit par Bálint Tóth. C’est un modèle de percolation par arêtes sur Z2, dans lequel on fixe la contrainte suivante : chaque sommet doit avoir exactement deux arêtes incidentes, perpen- diculaires entre elles. Gábor Pete a prouvé en 2008 que sous la mesure d’entropie maximale, toutes les composantes connexes sont des cycles finis presque sûre- ment. Je parlerai ici d’un régime où les directions Nord et Ouest sont privilégiées avec probabilité p et q respectivement, avec (p, q)\neq ( 1/2, 1/2). Je présenterai le résultat suivant, que nous avons montré avec Régine Marchand et Irène Mar- covici : il existe presque sûrement une infinité de composantes connexes infinies, qui sont en fait des chemins infinis. De plus, ces chemins ont tous la même pente asymptotique, qui vaut (2q−1)/(1-2p).

English: In 2008, Goulden and Jackson derived what was, in their words, a "remarkably simple recurrence'' for triangulations with a given genus and number of faces. A direct combinatorial argument for this recurrence remains an open problem in its full generality, though some cases of it have been resolved - most notably the planar case, which was treated by Baptiste Louf as recently as 2019. In this talk, we revisit the planar case through the lens of the planar lambda-calculus and its combinatorial interaction with planar trivalent maps, giving a bijective proof whose interpretation in terms of maps is equivalent to the one presented by Baptiste Louf. Français : En 2008, Goulden et Jackson ont dérivé ce qui était, selon eux, une "récurrence remarquablement simple" pour les triangulations avec un genre et un nombre de faces donnés. Un argument combinatoire direct pour cette récurrence reste un problème ouvert, bien que certains cas aient été résolus - notamment le cas planaire, qui a été traité par Baptiste Louf en 2019. Dans cet exposé, nous revisitons le cas planaire par le prisme du lambda-calcul planaire et de son interaction combinatoire avec les cartes cubiques planaires, en donnant une preuve bijective dont l'interprétation en termes de cartes est équivalente à celle présentée par Baptiste Louf.

The aim of this talk is to present a formula describing certain Toeplitz determinants appearing in some random partitions models, in terms of solutions of a discrete Painlevé II hierarchy. This result is a nontrivial generalization of Borodin's formula for the classical random partitions model when the measure is the Poissonized Plancharel measure. The result is obtained by using the Riemann-Hilbert problem (due to Baik-Deift-Johansson) associated to the family of orthogonal polynomials on the unit circle connected to the Toeplitz determinants of interest. The talk is based on a joint work with Thomas Chouteau (Université d'Angers) ArXiv2211.16898.

On considère un modèle de golf aléatoire, ou parking aléatoire, sur un graphe fini connexe. On assigne des balles et des trous à chaque sommet (aléatoirement ou non), puis les balles sont activées une par une, chacune réalisant une marche aléatoire jusqu'au premier trou libre qu'elle trouve. Sur les cycles ($\mathbb{Z}/n\mathbb{Z}$), on caractérise la loi des trous résiduels dans le cas où on tire uniformément une configuration avec des nombres de balles et de trous fixés. On peut alors étendre la définition du modèle à un graphe infini, $\mathbb{Z}$, et on explicite également la loi des trous résiduels dans ce cas.

Square-tiled surfaces are quadrangulations with prescribed monodromy. They come in families parametrized by the genus and the vertex degree profile. Their asymptotic enumeration for each family is important in the study of geometry and dynamics of rational billiards / flat surfaces (via Masur-Veech volumes), and has been performed using an algebraic approach (intersection theory). I will present an alternative, purely combinatorial approach to this problem in the case of a particular family. This approach gives a refined count of square-tiled surfaces according to their number of maximal horizontal cylinders. The key ingredient is the Chapuy-Féray-Fusy bijection between unicellular maps and decorated plane trees.