Jérémie Bouttier (IPhT/CEA & ENS Lyon)   Autour de la mesure de Plancherel sur les partitions d’entiers (une introduction aux processus de Schur)

Le but de ce cours sera de présenter quelques techniques liées aux processus de Schur, dans le cadre le plus simple de la mesure de Plancherel sur les partitions d’entiers. 
La mesure de Plancherel est une mesure sur l’ensemble des partitions d’un entier n, où une partition donnée apparaît avec une probabilité proportionnelle au carré de son nombre de tableaux de Young standard. Cette mesure apparaît très naturellement en lien avec le fameux problème de Ulam-Hammersley, qui consiste à étudier la longueur d’une plus longue sous-suite croissante d’une permutation uniforme de {1,…,n}. Il est en fait fructueux de travailler avec une version «poissonisée» du problème, où la taille n est tirée selon une loi de Poisson, dont on fera tendre le paramètre vers l’infini afin d’étudier les asymptotiques. 
Dans la première séance, nous verrons que la mesure de Plancherel poissonisée est en fait un processus déterminantal, dont le noyau de corrélation fait intervenir les fonctions de Bessel. Nous utiliserons pour cela le formalisme de l’espace de Fock fermionique. (Toutes les notions nécessaires seront introduites au fur et à mesure, de la manière la plus élémentaire possible.) 
Dans la seconde séance, nous étudierons les différentes asymptotiques du noyau de corrélation, par une application élégante de la méthode du col due à Okounkov et Reshetikhin. Nous verrons en particulier apparaître un phénomène de forme-limite, le noyau sinus discret dans le cas des limites «bulk» et le noyau d’Airy dans la limite «edge». In fine, nous aboutirons à une preuve du théorème de Baik-Deift-Johansson (1998) énonçant que les fluctuations de la longueur d’une plus longue sous-suite croissante d’une permutation uniforme ont asymptotiquement la même distribution que la plus grande valeur propre d’une matrice hermitienne aléatoire.

Julien Clément (Greyc Université de Caen)   Introduction à l’algorithmique du texte

Ce cours introductif vise à décrire quelques notions et structures fondamentales en algorithmique du texte. Il s’articule en trois parties: 
* Recherche de motifs (algorithme de Knuth-Morris-Pratt, automate de Aho-Corasick) 
* Structures d’indexation (arbres de suffixes, tables de suffixes, tri des suffixes en temps linéaire) 
* Transformée de Burrows-Wheeler (applications en indexation et en compression de données). ​

Cécile Mailler (University of Bath) . Les urnes de Pólya; approches probabilistes

Dans ce cours, nous étudierons divers modèles d’urnes de Pólya et les méthodes probabilistes utiles à l’étude de ces modèles. Dans le premier chapitre, nous introduirons la notion de martingale (uniquement en temps discret), et utiliserons cette théorie pour l’étude de deux cas classiques : le cas originel (quand la matrice de remplacement est diagonale), et le modèle « irréductible’’ (quand la matrice de remplecement est irréductible). Dans le second chapitre, nous étudierons des urnes « irréductibles » à tirage multiple pour lesquelles les méthodes classiques de martingales ne s’appliquent pas; nous montrerons comment utiliser l’approximation stochastique pour résoudre ce cas. Dans le troisième chapitre, nous généraliserons le modèle irréductible à un nombre infini de couleurs et découvrirons un lien entre urnes de Pólya et ergodicité markovienne. J’espère pouvoir, au cours de ces trois chapitres, donner une vision d’ensemble de ces trois modèles ainsi que des trois méthodes probabilistes utilisées pour leur étude. 
Le premier chapitre s’inspire principalement des travaux de Eggenberger et Pólya (1923) et de Janson (2004). Les deux autres chapitres s’appuient sur des travaux beaucoup plus récents : Lasmar, M., Selmi (2018) et M., Marckert (2017).

​

Anna Ben-Hamou (Sorbonne Université) : Temps de mélange de marches aléatoires sur des graphes aléatoires

Le temps de mélange d’une marche aléatoire sur un graphe connexe fini est intimement lié aux propriétés géométriques du graphe, comme par exemple sa constante isopérimétrique : intuitivement, plus il est difficile pour la marche de passer d’une région du graphe à une autre, plus le mélange est lent. De plus, la présence de goulots d’étranglement a tendance à empêcher le phénomène de cutoff, qui décrit une convergence abrupte à l’équilibre. Dans cet exposé, nous commencerons par donner une introduction aux temps de mélange et présenter les liens entre le temps de mélange et l’isopérimétrie du graphe. Puis nous chercherons à quantifier ces liens de façon plus précise sur des graphes aléatoires présentant une structure en deux communautés. Sur ces graphes, la constante isopérimétrique correspond à peu près à la fraction d’arêtes allant d’une communauté à l’autre, et peut être ajustée comme un paramètre du modèle. Nous verrons qu’il existe un seuil pour cette constante délimitant deux régimes de mélange bien différents.

Nicolas Bonichon (Bordeaux LaBRI) Spanners géométriques : au-delà du pire cas

​Un graphe géométrique est un graphe défini à partir d’un nuage de points (par exemple dans le plan). L’étirement d’un graphe géométrique est le pire rapport entre la distance dans le graphe et la distance Euclidienne, pour toute paire de points du graphe. Un t-spanner est un graphe (ou une famille de graphes) dont l’étirement est borné par t. Dans cet exposé je présenterai quelques résultats relatifs à certains spanners : triangulations de Delaunay, Theta-graphs, routage dans les triangulations de Delaunay. Nous essayerons d’aller au-delà des analyses en pire cas.

Jehanne Dousse (CNRS et Université Lyon I)   Identités de q-séries et de partitions
​
Les q-séries (parfois appelées séries basiques hypergéométriques) sont des séries construites en utilisant les q-factorielles $(a;q)_n := (1-a)(1-aq)…(1-aq^{n-1}).$ On les retrouve dans de nombreux domaines des mathématiques tels que la combinatoire, la théorie des nombres, la théorie des groupes et la physique mathématique. Sous l’influence de Ramanujan, les q-séries ont souvent été étudiées en relation avec les partitions d’entiers. Nous commencerons par une introduction générale aux q-séries et étudierons quelques identités classiques, puis nous verrons comment utiliser des identités de q-séries pour prouver des identités de partitions.

Christina Goldschmidt (University of Oxford) The scaling limit of the minimum spanning tree of the complete graph

Consider the complete graph on n vertices with independent and identically distributed edge-weights having some absolutely continuous distribution. The minimum spanning tree (MST) is simply the spanning subtree of smallest weight. It is straightforward to construct the MST using one of several natural algorithms. Kruskal’s algorithm builds the tree edge by edge starting from the globally lowest-weight edge and then adding other edges one by one in increasing order of weight, as long as they do not create any cycles. At each step of this process, the algorithm has generated a forest, which becomes connected on the final step. In this talk, I will explain how it is possible to exploit a connection between the forest generated by Kruskal’s algorithm and the Erdös-Rényi random graph in order to show that M_n, the MST of the complete graph, possesses a so-called « scaling limit » as n tends to infinity. We think of M_n as a metric space (using the graph distance), rescale edge-lengths by n^{-1/3}, and show that M_n converges in distribution to a random tree-like metric space. No prior knowledge of scaling limits will be assumed! Joint work with Louigi Addario-Berry (McGill), Nicolas Broutin (Sorbonne Université) and Grégory Miermont (ENS Lyon).

Adeline Pierrot (Université Paris Sud)  Formes limites de permutations à motifs 

​On s’intéresse aux ensembles de permutations à motifs exclus, appelés classes de permutations, qui ont été beaucoup étudiés en combinatoire énumérative. Dans ce travail, à la frontière entre combinatoire et probabilités, on s’intéresse à la limite d’échelle d’une grande permutation aléatoire uniforme dans une classe de permutation. On décrit cette limite en terme de permuton, objet pouvant être vu comme une permutation de taille infinie. Un outil clé est la décomposition par substitution des permutations, qui permet de voir les permutations comme des arbres.

Angel and Schramm ont étudié en 2003 la limite locale des triangulations uniformes. La loi limite, appelée UIPT (pour Uniform Infinite planar Triangulation) a depuis été pas mal étudiée et est plutôt bien comprise. Dans cet exposé, je vais expliquer comment on peut obtenir un résultat analogue à celui d’Angel et Schramm mais lorsque les triangulations ne sont plus uniformes mais distribuées selon un modèle d’Ising. Une partie importante de la preuve consiste à étudier une équation sur des séries génératrices à deux variables catalytiques et repose sur la méthode des invariants de Tutte (introduite par Tutte et popularisée par Bernardi et Bousquet-Mélou). L’objet limite est pour le moment très mal compris et soulève un grand nombre de questions ouvertes !

Dan Betea: The finite temperature Plancherel measure and process

The Plancherel measure on partitions, counting standard Young tableaux, has remarkable scaling properties. In the large size limit and upon poissonization, it exhibits (discrete) sine kernel asymptotics in the bulk and Tracy–Widom GUE fluctuations at the edge, both behaviours seen before and considered universal in (continuum) random matrix theory. In this talk we present a generalization first discussed by Borodin, the so-called cylindric or finite temperature Plancherel measure. It comes from counting standard Young tableaux of skew shape in the same way the original measure comes from counting tableaux of non-skew shape. Using the theory of Schur measures and fermions in finite temperature, we analyse the edge of this measure to obtain—for the first time in a discrete system—the finite temperature Tracy–Widom GUE distribution, first obtained by Johansson in (continuum) finite temperature random matrix theory (the so-called Moshe–Neuberger–Shapiro matrix model). The latter distribution provides an interpolation between two classical extreme statistics distributions: the Tracy–Widom GUE distribution of the KPZ universality class and the Gumbel distribution. The result, joint with Jeremie Bouttier, could be viewed as a « finite temperature analogue » of the Baik–Deift–Johansson theorem on the edge scaling of poissonized Plancherel random partitions and the longest increasing subsequence of random permutations. If time permits, we shall discuss the associated stationary stochastic process, as well as recent progress on other variants, associated limit shapes and bulk limits, and possible connections to the representation theory of $S_{\infty}$.

Jérémie Bettinelli: Slit-slide-sew bijections for bipartite and quasibipartite plane maps

​We unify and extend previous bijections on plane quadrangulations to bipartite and quasibipartite plane maps. Starting from a bipartite plane map with a distinguished edge and two distinguished corners (in the same face or in two different faces), we build a new plane map with a distinguished vertex and two distinguished half-edges directed toward the vertex. The faces of the new map have the same degree as those of the original map, except at the locations of the distinguished corners, where each receives an extra degree. The idea behind this bijection is to build a path from the distinguished elements, slit the map along it, and sew back after sliding by one unit, thus mildly modifying the structure of the map at the extremities of the sliding path. This bijection provides a sampling algorithm for uniform maps with prescribed face degrees and allow to recover Tutte’s famous counting formula for bipartite and quasibipartite plane maps. In addition, we explain how to decompose the previous bijection into two more elementary ones, which each transfer a degree from one face of the map to another face. In particular, these transfer bijections are simpler to manipulate than the previous one and this point of view simplifies the proofs.

Henri Derycke: Une notion de récurrence dans le modèle du tas de sable sur le réseau carré

Pour les graphes finis, les configurations récurrentes du modèle du tas de sable sont en bijection avec les arbres couvrants, via un critère algorithmique de Dhar. De plus la distribution du nombre de grains sur ces configurations est, à une constante près, celle de l’activité externe au sens de Tutte. On s’intéresse à des extensions de ces propriétés dans le cas du graphe infini qu’est la grille Z^2 et pour des configurations bipériodiques. On étudie la récurrence en plaçant le puits du critère de Dhar à l’infini dans une direction de pente rationnelle. Les analogues des arbres couvrants sont alors les forêts couvrantes enracinées sur des cycles non-contractiles du tore décrivant la période. On montre bijectivement que la distribution de l’analogue de l’activité externe au sens de Tutte de ces forêts est invariante par rotation de la direction du puits.

Sergey Dovgal: Contradictory circuits of the 2-SAT

We investigate the structure of a random 2-CNF formula near the point of the satisfiability phase transition, where the ratio of the number of clauses and the number of edges approaches to one. The analytic approach together with a new sum-representation decomposition allows to study such statistics as the number of contradictory circuits and variables, and the structure of the spine (introduced by Bollobás et. al. [2001, Random Structures & Algorithms, 18(3), 201-256]): its cardinality and the number of its components.

Dans le modèle de graphe aléatoire d’Erdős–Rényi $G(n,p)$, l’émergence de la composante géante se situe à la fenêtre $p=n^{-1}+O(n^{-4/3})$. Nous considérons une généralisation de $G(n,p)$ sur les hypergraphes k-uniformes, avec une notion de connexité d’ordre supérieur dite j-connexe, avec un paramètre j. Sous cette notion de j-connexité, nous avons déterminé, dans un régime sous-critique, la taille précise des $m$ plus grandes composantes j-connexes, et aussi leur structure. C’est un travail joint avec Oliver Cooley, Nicola Del Giudice et Mihyun Kang.

Sandro Franceschi: Méthode des invariants de Tutte et mouvement brownien réfléchi dans des cônes

Dans les années 1970, William Tutte développa une approche algébrique, basée sur des « invariants », pour résoudre une équation fonctionnelle qui apparait dans le dénombrement de triangulations colorées. La transformée de Laplace de la distribution stationnaire du mouvement brownien réfléchi dans des cônes satisfait une équation similaire. Pour être applicable, cette méthode requiert l’existence de deux fonctions appelées respectivement invariant et fonction de découplage. Tous les modèles ont des invariants mais on démontre que l’existence de fonctions de découplage équivaut à une condition géométrique simple sur les angles de réflexion. Pour les modèles qui ont une fonction de découplage, on obtient une expression explicite sans intégrale de la transformée de Laplace en fonction des invariants. En particulier, on obtient à nouveau une formule pour la transformée de Laplace de plusieurs cas bien connus, comme la skew symétrie, les réflexions orthogonales ou le résultat de Dieker et Moriarty qui caractérise les densités stationnaires qui s’écrivent sous la forme d’une somme d’exponentielles. Cette méthode permet de plus de caractériser la nature algébrique de la transformée de Laplace en fonction des modèles. Cet exposé est issu d’un travail en collaboration avec M. Bousquet-Mélou, A. Elvey Price, C. Hardouin et K. Raschel

Luis Fredes: Bijections for tree-decorated maps and applications to random maps

In this talk, we introduce a new family of maps: the (not necessarily spanning) tree-decorated maps. To study this class of maps, we introduce a bijection which allows us to deduce combinatorial results, recovering as a corollary some results about spanning-tree decorated maps, and to understand local limits. Finally, we discuss the possible metric scaling limit of this map: the shocked map. We give certain properties and give the conjectured continuum construction. This is a work in progress with Avelio Sepúlveda.

We are interested in the question of noise sensitivity in the following sense: how much information do we lose on a property of a finite number of iid Bernoulli(p) variables if we resample a small proportion of them. If the Bernoulli variables are thought to indicate the presence of edges between the n vertices of a random graph, this structure corresponds to an Erdős-Rényi random graph with parameter p. Then it’s natural to focus on graph properties, like planarity for instance. The Erdős–Rényi random graph is known to have a threshold for p around 1/n such that many graph properties, like planarity, are asymptotically trivial below but non trivial close to the threshold. This is a fertile ground for noise sensitivity because, if we only remove the edges deleted by the resampling procedure, there is hope that while bringing the graph in his subcritical state, it will erased all witnesses of the original propety. On the other hand, criticality is also known to be the place where a fascinating phenomena occur : the graph converges in the scaling limit towards a certain continuous, fractal-like, random metric space based on the Brownian motion. This convergence takes place together with the convergence of the reampling, in the form of a dynamical percolation, so our plan is that the noise sensitivity can be deduced from the mixing property of the continuous dynamical percolation. In this talk, we will explain how one can prove this mixing property in the continuous setting.

Lucas Gerin: Plus longue chaîne croissante avec écarts

Le problème d’Hammersley s’énonce de la façon suivante : dans un processus de Poisson dans un rectangle, quelle est la longueur maximale d’une chaîne de points croissante (dans les 2 directions)? Le but de cet exposé est de présenter des résultats asymptotiques pour la variante dans laquelle on impose des écarts entre deux points successifs. (Travail en commun avec Anne-Laure Basdevant)

Vincent Jugé: L’algorithme de tri ShiversSort adaptatif

Je présenterai l’algorithme de tri ShiversSort adaptatif. Cet algorithme de tri, développé récemment, exploite la présence de fragments partiellement ordonnés pour trier plus efficacement des données. Je me pencherai notamment sur les liens entre cet algorithme et l’algorithme TimSort, actuellement utilisé dans les langages Python et Java, et je montrerai que la complexité de cet algorithme, en nombre de comparaisons effectuées, est optimal à un facteur additif linéaire près.

Isaac Konan: Bijective proof and generalization of a Rogers-Ramanujan type identity: Siladic’s partitions theorem.

A rich source of ROGERS-RAMANUJAN type identities is the representation theory of Lie algebras. This has its origins in work of Lepowsky and Wilson, who proved the Rogers-Ramanujan identities by using representations of the affine Lie algebra sl(2, C). Our motivation in this talk is one such identity given by Siladić in his study of representations of the twisted affine Lie algebra A_2^(2). In a recent paper, Dousse introduced a refinement of Siladić’s theorem on partitions, where parts occur in two primary (degree one) and three secondary colors(degree two). Her proof used the method of weighted words and q-difference equations. The purpose is to sketch a bijective proof of Dousse’s theorem and show how it can be generalized from two primary colors to an arbitrary number of primary colors. We will also discuss the possibility of a generalization in higher degree (more than two).

Baptiste Louf: Limites locales de triangulations de grand genre
​
En 2002, Angel et Schramm ont démontré que la limite locale des triangulations planaires aléatoires est l’UIPT, une triangulation infinie du plan. En 2012, Curien a introduit les PSHIT, une famille de triangulations infinies du plan de « nature hyperbolique » qui sont une généralisation naturelle de l’UIPT. Benjamini et Curien ont conjecturé que ces objets étaient la limite locale des triangulations de grand genre (i.e. le genre est linéaire en le nombre de faces). Nous démontrons cette conjecture pour les triangulations de type I (travail en commun avec Thomas Budzinski).

Cyril Marzouk: Scaling limits of random planar maps with a prescribed degree sequence

A finite planar map may be viewed as the topological gluing of finitely many polygons which forms a sphere; in this talk I consider a model of random planar maps where for every $n \ge 1$, we are given $n$ deterministic polygons, that we glue together uniformly at random. Then we study the graph structure of such a random map as the number of polygons tends to infinity. We shall identify the growth of the diameter of such maps, and see that the vertex-set equipped with the suitably rescaled graph distance always admits sub-sequential limits. Furthermore, under very simple assumptions on the size of the polygons, we identify Brownian limits of such maps: the celebrated Brownian map, and more generally Brownian disks, or the Brownian CRT.

In biology, a phylogenetic tree is a tool to represent the evolutionary relationship between species. Unfortunately, the classical Schröder tree model is not adapted to take into account the chronology between the branching nodes. In particular, it does not answer the question: how many different phylogenetic stories lead to the creation of n species and what is the average time to get there? In this paper, we enrich this model in two distinct ways in order to obtain two ranked tree models for phylogenetics, i.e. models coding chronology. For that purpose, we first develop a model of (strongly) increasing Schröder trees, symbolically described in the classical context of increasing labeling trees. Then we introduce a generalization for the labeling with some unusual order constraint in Analytic Combinatorics (namely the weakly increasing trees). Although these models are direct extensions of the Schröder tree model, it appears that they are also in one- to-one correspondence with several classical combinatorial objects. Through the paper, we present these links, exhibit some parameters in typical large trees and conclude the studies with efficient uniform samplers.

Mehdi Naima: Ranked Schröder Trees


In biology, a phylogenetic tree is a tool to represent the evolutionary relationship between species. Unfortunately, the classical Schröder tree model is not adapted to take into account the chronology between the branching nodes. In particular, it does not answer the question: how many different phylogenetic stories lead to the creation of n species and what is the average time to get there? In this paper, we enrich this model in two distinct ways in order to obtain two ranked tree models for phylogenetics, i.e. models coding chronology. For that purpose, we first develop a model of (strongly) increasing Schröder trees, symbolically described in the classical context of increasing labeling trees. Then we introduce a generalization for the labeling with some unusual order constraint in Analytic Combinatorics (namely the weakly increasing trees). Although these models are direct extensions of the Schröder tree model, it appears that they are also in one- to-one correspondence with several classical combinatorial objects. Through the paper, we present these links, exhibit some parameters in typical large trees and conclude the studies with efficient uniform samplers.

Frédéric Paccaut: Sous la pression : les VLMC enfin dans le bon sens

Sous la pression de la communauté, Le modèle VLMC (variable length markov chain) sera enfin présenté en lisant les mots de gauche à droite ! Des résultats d’existence et d’unicité de la mesure stationnaire, ainsi que de convergence vers cette mesure, seront donnés, qui reposent sur des collaborations avec Peggy Cénac (Dijon), Brigitte Chauvin (Versailles), Ricardo Felipe Ferreira (Sao Carlos, Brésil), Sandro Gallo (Sao Carlos, Brésil) et Nicolas Pouyanne (Versailles).

Delphin Sénizergues: Propriétés asymptotiques des arbres récursifs pondérés

On se donne une suite de poids (w_n), qui peut être déterministe ou aléatoire, et on construit un arbre récursivement: à l’étape 1, l’arbre a un seul sommet. A l’étape n+1, on ajoute un sommet et celui-ci choisit un parent au hasard parmi les sommets déjà présents, de telle sorte à ce que le k-ième sommet (dans l’ordre d’arrivée) soit choisi avec probabilité proportionnelle au poids w_k. Ce modèle englobe bien sûr le cas uniforme, très étudié depuis les années 70, lorsque la suite de poids est constante. En fait, on peut aussi montrer que les arbres à attachement préférentiel affine (aussi très étudiés depuis une trentaine d’année) peuvent être décrits par un tel modèle, en utilisant une suite aléatoire de poids appropriée. Cela motive l’étude de propriétés de ces arbres pour des suites de poids assez générale. On montrera des résultats asymptotiques sur certaines statistiques de l’arbre: des degrés des sommets, profil et hauteur, lorsque le nombre de sommets devient grand.