La notion de motif dans une permutation définit une notion naturelle de sous-structure. Les classes de permutations évitant des motifs sont les ensembles fermés par le bas pour cet ordre partiel. Ces classes ont été définies dans les années 70 dans contexte des algorithmes de tri. Depuis, elles sont étudiées dans des contextes allant de la combinatoire aux probabilités en passant par la bio-informatique.
Dans ce cours, on présentera la décomposition par substitutions des permutations qui permet de représenter les permutations comme des arbres. On montrera ensuite une série de résultats sur ces classes de permutations qui peuvent être obtenus en utilisant la décomposition par substitutions. Ceux-ci incluent l'énumération exacte de classes spécifiques, des théorèmes d'énumération plus généraux ou encore les limites d'échelle (en termes de permutons) de certaines classes de permutations.

L'un des nombreux problèmes posés par S. Ulam concerne l'asymptotique du cardinal maximal d'une sous-suite croissante d'une permutation aléatoire uniforme de [1,n]. Ce problème est résolu, du moins au premier ordre, en 1979, indépendamment par Logan et Shepp à l'Ouest et par Kerov et Vershik à l'Est, dans leur étude de la forme limite des tableaux de Young sous la mesure de Plancherel. Il en ressort que la plus longue sous-suite croissante est de cardinal équivalent à 2√n. Des fluctuations en n^{1/6} autour de ce résultat, faisant intervenir la loi de Tracy-Widom, ont été montrées en 1999 par Baik, Deift et Johansson, dans un travail faisant date.

Auparavant, en 1972, à l'occasion du sixième Symposium de Probabilités et Statistiques à Berkeley, Hammersley, dans un exposé sur une liste de sujets qui lui paraissent porteur, propose une approche probabiliste pour attaquer ce problème, mettant en jeu un processus de Poisson homogène sur un carré (qui engendre la permutation uniforme). Cependant, Hammersley ne mène pas à bout cette approche dans son texte. C'est Cator et Groeneboom, en 2007, qui arrivent à l'exploiter pour retrouver l'asymptotique en 2√n. Nous présenterons cette approche dans un contexte un peu simplifié, qui permet de bien en appréhender le principe.

Nous verrons ensuite comment cette même méthode permet de résoudre au premier ordre le problème de percolation de dernier passage appelé "Corner Growth Model" et résolu par H. Rost en 1981 par la théorie des systèmes de particules.

Nous verrons dans la séance d'exercices comment des variantes de ces cas peuvent être traités par cette même méthode.

Le cours ne demande pas de prérequis de probabilités très sophistiqués.

Comment prouver qu’un algorithme est optimal ? Nous nous intéresserons à donner un sens à cette question, et à présenter des techniques classiques pour y répondre. Le cours se concentrera sur des problèmes qui ont des solutions algorithmiques rapides (il ne s’agit donc pas d’un cours de classe de complexités, P, NP, …) et l’on abordera la question pour la complexité pire cas et pour la complexité d’algorithmes probabilistes (randomized). On verra notamment les méthodes par comptage et par adversaire, la technique de Ben-Or et le principe de Yao.

Reconfigurer une solution d'un problème donné, c'est lui appliquer des opérations élémentaires successives sans quitter l'espace des solutions. Un tel besoin apparaît naturellement dans des situations dynamiques où une solution donnée est déjà en place et doit être modifiée, sans qu'une rupture de service puisse être envisagée. C'est également un outil utile pour l'énumération ou le sampling uniforme de solutions. Plusieurs grandes questions sont étudiées : quelles opérations élémentaires garantissent que toute autre solution peut être ainsi atteinte ? À opérations fixées, quelle est la complexité de décider si une autre solution donnée peut être atteinte ? Que dire du nombre d'opérations nécessaires pour cela ?

Dans cet exposé, nous discuterons de divers résultats positifs et négatifs dans le cas particulier de la coloration de graphes.

Dans plusieurs situations comme certains championnats sportifs, jeux vidéos en ligne ou dans l’analyse de réseaux sociaux, les données collectées par les statisticiens concernent des paires d’individus et peuvent donc être représentées par des graphes. Je présenterai quelques modèles basiques de graphes aléatoires utilisés dans ces situations et passerai en revue quelques résultats obtenus récemment dans l’analyse statistique de ceux-ci. Je porterai une attention particulière aux problèmes de prédiction et de matching, qui se posent tout deux à des situations ou le graphe n’est pas complètement observé. Nous verrons ainsi par exemple certains cas ou la structure du graphe permet de caractériser précisément quand ce manque d’information peut être pallié.

Given a finitely generated group with generating set S, we study the cogrowth sequence, which is the number of words of length n over the alphabet S that are equal to one. This has a very natural interpretation in terms of walks on graphs as it is related to the probability of return for walks in a Cayley graph with steps from a step set S. This talk will survey the topic, focusing on connections between the structure of the group, and properties of the cogrowth sequence. We will then show that the cogrowth sequence is not P-recursive when G is an amenable group of superpolynomial growth, answering a question of Garrabant and Pak. In addition, we consider the exponential growth of the cogrowth sequence for certain infinite families of free products of finite groups and free groups with the purpose of proving that a gap theorem holds: if S is a finite symmetric generating set for a group G and if a(n) denotes the number of words of length n over the alphabet S that are equal to 1, then lim sup_n a(n) (1/n) is either less than or equal to 2, or greater than or equal to 2(√2).

Le calcul de Schubert se propose de répondre à des problèmes énumératifs en géométrie du type: si on se donne 4 droites affines ``génériques'' dans $\mathbb{C}^3$, combien de droites intersectent chacune des droites de départ? Le quinzième problème de Hilbert, résolu au cours du vingtième siècle, visait à formuler et répondre à ces questions de manière rigoureuse. Dans cet exposé nous exposerons brièvement ce contexte classique, et en quoi la combinatoire des fonctions de Schur et des tableaux apparaît naturellement. Dans un deuxième temps nous aborderons des problèmes d'intersection plus complexes, pour lesquels les questions combinatoires ne sont pas encore entièrement résolues.

En partant d'un graphe aléatoire d'Erdös-Rényi critique, on s'intéresse à une percolation dynamique sur ce graphe: chaque paire de sommets est munie d'un processus de Poisson et à chaque point de ce processus correspond un rafraîchissement de l'état de la paire dans le graphe. Un tel processus est un processus de fragmentation-coalescence: il fait se connecter différentes composantes connexes et se déconnecter certaines. On verra qu'avec une mise à l'échelle correcte, le processus converge vers un processus de fragmentation et coalescence sur la limite continu du graphe d'Erdös-Rényi. On discutera également du cas d'autres graphes aléatoires dont le comportement critique des grandes composantes est décrit par le coalescent multiplicatif.

La percolation de dernier passage dirigée est, classiquement, un modèle de croissance dans le quart de plan discret. Pour croitre de la case $(i,j)$, il faut que les cases $(i-1,j)$ et $(i,j-1)$ soient présentes dans notre amas de croissance, puis attendre un temps aléatoire $\tau_{(i,j)}$. Ce modèle est notamment intéressant pour modéliser le temps d’assèchement d'un terrain. Dans cet exposé, je présente une généralisation de la percolation de dernier passage dirigée dans le cas où le temps à attendre $\tau_{(i,j)}$ dépend des temps d'arrivée des cases $(i-1,j)$ et $(i,j-1)$ dans l'amas et je présente ce modèle non pas comme un modèle de croissance dans le quart de plan, mais dans un cylindre de taille $L$. Dans le cylindre, il apparait ainsi une ligne de front pour notre amas. L'objet de cet exposé va être d'étudier deux propriétés asymptotiques (en temps) de cette ligne de front: sa vitesse et sa forme. Nous verrons que, dans des cas particuliers dits solubles ou intégrables, cette vitesse et cette forme ont une forme explicite en fonction des paramètres du modèle. Puis, j'expliquerai par quelle magie ces cas sont solubles, alors que les autres ne les sont a priori pas.

Construisons une suite aléatoire et croissante d’arbres par le mécanisme d’attachement préférentiel affine. Partant d’un arbre fini $S$, appelé « graine », nous ajoutons un par un de nouveaux sommets, en les reliant par une arête à un sommet déjà existant. Ce dernier est choisi aléatoirement, avec une probabilité qui est proportionnelle à une fonction affine de son degré. Ainsi, nous définissons une famille (à un paramètre) d’arbres à attachement préférentiel affine $(T_n^S)_{n \geq k}$, dont le bien connu modèle linéaire (Barabasi-Albert) est un cas particulier. Nous étudions le problème de l’influence asymptotique de la « graine » sur la loi de notre suite d’arbres $(T_n^S)_{n \geq k}$. Nous montrons que pour deux graines distinctes $S$ et $S’$, la distance en variation totale entre les lois de $T_n^S$ et $T_{n}^{S’}$ est uniformément minorée en $n$ par une constante strictement positive. Ce travail a été réalisé en commun avec Ioan Manolescu.

Dans la sacramentelle présentation des journées ALEA du début de semaine, il y a toujours un slide qui montre à quel point cette conférence est à l'interface avec de nombreuses disciplines scientifiques : l'algorithmique, les probabilités, la physique statistique, la bio-informatique... Ma collaboration avec la physicienne et combinatoricienne Karen Yeats (Waterloo, Canada) permet de faire figurer dans cette liste un domaine moins représenté : la théorie quantique des champs. Récemment, il a été découvert que les solutions de certaines équations de Dyson-Schwinger (des équations fondamentales du domaine - pas de panique, j'expliquerai cela dans une longue introduction didactique) peuvent se voir comme des séries génératrices d'objets combinatoires : des diagrammes de cordes un peu particuliers. L'analyse de ces objets par le prisme de la combinatoire énumérative nous permet alors d'obtenir des résultats physiques surprenants. Notamment, nos travaux mettent en évidence une dichotomie entre les différentes théories quantiques.

Nous donnons des conditions explicites sur le noyau de transition d'une chaîne de Markov branchante pour que cette chaîne admette une limite d'échelle vers un processus de croissance-fragmentation autosimilaire d'indice négatif. Le résultat inclut également une limite d'échelle pour la généalogie associée vue comme un arbre réel compact.

Lors de cette démonstration, nous présenterons la librairie "usain boltz". Nous rappellerons brièvement les principes de la méthode de Boltzmann puis nous montrerons son implémentation dans usain boltz à travers le langage de grammaire, les différentes implémentation d'oracles et enfin le mécanisme de "builders". Les "builders" permettant de passer de la spécification d'une classe combinatoire à un structures de données Python. Enfin nous présenterons l'utilisation de usain boltz avec Sagemath.

 I will describe our solution to the problem of counting lattice walks by winding angle around the origin on four different lattices including the square lattice and the triangular lattice. The method uses a new decomposition of each lattice, which allows us to write functional equations characterising generating functions of these walks. We then solve these equations in terms of Jacobi theta functions, allowing us to extract information about the (differential) algebraicity and asymptotics of these generating functions. For each of the four lattices, we then use the reflection principle to count walks confined to cones such as the quarter plane and three quarter plane. On the square lattice, most of our results were derived by Timothy Budd in 2017 using a very different method, based on an explicit eigenvalue decomposition of certain matrices counting paths in the lattice.

Un arbre binaire compacté est un graphe acyclique dirigé qui représente un arbre binaire de façon sans redondances, dans le sens que tous les sous-arbres isomorphes sont partagés. Nous montrons que le nombre des arbres binaires compactés de tailles n croît asymptotiquement en $\Theta(n! 4^n e^{3 a_1 n^{1/3}} n^{3/4})$, avec a_1 ≈ -2,338 la plus grande racine de la fonction d'Airy. Ce résultat est obtenu à partir d'une nouvelle récurrence des nombres de ces arbres compactés, et avec une nouvelle méthode qui, inspirée par des estimations empiriques suffissament précises, prouve des bonnes bornes par induction. Avec la même méthode, nous avons obtenu aussi l'énumération asymptotique des automates minimaux qui reconnaissent un langage fini d'un alphabet binaire, qui possède aussi un exponentiel étiré. Par sa simplicité, notre méthode s'applique potentiellement aux autres objets. Il s'agit d'un travail commun avec Andrew Elvey Price et Michael Wallner.

Pour une étude asymptotique d' un grand réseau stochastique, dont l’état des noeuds suit un processus de Markov, si la mesure invariante n’est pas explicite, on s'intéresse à la limite champ moyen d’un modèle symétrique. Elle donne la distribution limite de l’état d’un noeud du réseau. Dans l’étude d’Autolib -ou système de véhicules partagés avec réservation- le processus d’état des noeuds n’est pas Markovien mais a une limite champ moyen simple. Travail commun avec Cédric Bourdais et Hanene Mohamed.

Bukh et Zhou ont conjecturé que pour deux permutations i.i.d, l'espérance de la longueur de la plus longue sous-suite commune est minorée par $\sqrt{n}$. Ce problème peut se ramener à la compréhension de la plus longue sous-suite croissante de permutations aléatoires. On détaillera le cas où la loi de la  permutation est invariante par conjugaison qui peut être traité à l'aide de la compréhension de la structure en cycles de la composée de deux permutations indépendantes.

Nous nous intéressons à une sous-classe des automates de Parikh dont la série génératrice multivariée est holonome. Dans un premier temps, nous étendons les travaux de Philippe Flajolet sur l’intrinsèque ambiguïté des langages algébriques à la classe des automates de Parikh. Nous étudions ensuite les limites de cette méthode, et les problèmes de décision liés à l’intrinsèque ambiguïté des automates de Parikh. Enfin, nous exploitons le caractère holonome des séries génératrices pour en déduire un algorithme résolvant le problème d’inclusion sur la sous-classe considérée. Travail en commun avec Alin Bostan, Arnaud Carayol et Cyril Nicaud.

La notion d’universalité est un concept important dans l’étude des cartes combinatoires : on observe des phénomènes similaires pour différents modèles de cartes. L’exemple le plus célèbre est la convergence d’échelle de nombreux modèles de cartes planaires aléatoires vers la carte brownienne En 2012, Benjamini et Curien ont formulé une conjecture sur la limite locale des triangulations de grand genre, que nous avons démontrée en 2019 avec Thomas Budzinski.. Dans un deuxième travail, nous étendons l’étude des limites locales en grand genre à une vaste classe de cartes (plus précisément les cartes biparties à degrés prescrits). Cet exposé sera une introduction à nos techniques, qui reposent à la fois sur des arguments probabilistes et sur des récurrences énumératives que j'ai obtenues dans un travail indépendant via la hiérarchie de 2-Toda.

Soit $m$ un entier positif fixe et $p_1,\ldots, p_m$ des entiers premiers. Le système de numération à base multiple est un système de représentation dont tous entier positif $n$ a une représentation de la forme \[n=\sum_{\mathbf{a}} d_{\mathbf{a}}p_1^{a_1}\cdots p_m^{a_m}\] avec $d_{\mathbf{a}}\in\{0,1\}$. On peux voir ces représentations comme partitions en éléments de l'ensemble \[\mathcal{S}=\{p_1^{\alpha_1},\ldots,p_m^{\alpha_m}\colon \mathbb{N}\}.\] L'objectif de cet exposé est de considérer ces partitions en laissant varier $m$ par rapport à $n$. Par exemple, nous considérons les partitions de l'entier $n$ en entiers dont la décomposition en facteurs premiers ne comporte que des nombres premiers plus petits que $n^c$ avec $c \in (0,1)$.

Une suite k-automatique est une suite qui peut être calculée par un automate fini de la manière suivante : le n-ième terme de la suite est fonction de l'état atteint par l’automate après lecture de la représentation de l'entier n en base k. Ces suites peuvent également être obtenues à partir du point fixe d'une substitution de longueur k. Je montrerai qu'il existe des familles de suites automatiques qui, malgré leur description très simple, ont les mêmes corrélations d'ordre 2 qu'une suite i.i.d. de symboles choisis uniformément au hasard. Plus précisément, pour tout entier r>0, et pour tout couple (i,j) de symboles, la proportion asymptotique d'entiers n pour lesquels (u_n,u_{n+r})=(i,j) est égale à 1/L^2, où L est le nombre de symboles. La preuve repose sur des ingrédients simples et se généralise à des suites multi-dimensionnelles.

Let $f_n$ be the counting sequence of a labaled combinatorial class and $g_n$ be the number of connected objects of size $n$ in the same class, so that their exponential generating series satisfies $F(z)=\log(G(z))$. We are interested in the asymptotic behavior of the probability $p_n=g_n/f_n$. It~turns out that if $f_n$ is growing sufficiently fast, then $p_n$ converges to $1$ and we can describe the coefficients $h_i$ involved in the asymptotic expansion of $p_n$ explicitly. In some cases, we can indicate other combinatorial objects that these coefficients count. Moreover, the asymptotic expansion of $h_n/f_n$ can also be described.

En informatique, la notion de "non-déterminisme" ne signifie pas "aléatoire", mais désigne un processus de calcul qui, à chaque étape, peut se dupliquer pour explorer plusieurs possibilités en parallèle. Nous proposons une extension de cette notions aux marches à une dimension. Une marche classique à une dimension tire aléatoirement dans un ensemble S un pas (un entier relatif) à chaque étape. Un problème naturel est le calcul de la probabilité que la marche soit une "excursion" après n pas, c'est-à-dire qu'elle revienne à son point de départ (la somme des pas est nulle), tout en étant demeurée dans le demi-plan supérieur (les sommes partielles sont positives). Un pas non-déterministe est un ensemble fini de pas classiques. S devient donc un ensemble d'ensembles de pas classiques. Une marche non-déterministe tire aléatoirement dans S un pas non-déterministe à chaque étape. Une marche classique C est incluse dans notre marche non-déterministe N si à chaque étape, le pas de C est inclus dans le pas de N. Une excursion non-déterministe est une marche dans laquelle au moins une excursion classique est incluse. Il s'agit d'un travail commun avec Lamine Lamali et Michael Wallner, motivé par l'étude des performances des réseaux utilisant des protocoles d'encapsulation et de décapsulation de paquets. Nos preuves utilisent des techniques de séries génératrices développées notamment pour l'étude des marches aléatoires.

Equivalence of statistical ensembles provides a suitable formalism when it comes to analysing systems of many particles. This paradigm can be transposed to the analysis of large combinatorial objects. It has inspired Vershik a probabilistic approach of integer partitions that can be used in order to derive the distribution of various parameters, limit shapes and asymptotic enumeration formulae. It can also be applied in order to produce algorithms for random generation. After reminding some notions of analytic combinatorics and the definition of the Boltzmann distribution, we will discuss how one may apply this approach to various problems. In particular we will consider the well known case of unrestricted partitions. Then we will talk about partitions with different restrictions, including a restriction of the source of the parts, of the length and of the Durfee number.

Dans cet exposé, nous nous interrogeons sur la pertinence de modèles aléatoires uniformes pour analyser des algorithmes qui prennent en entrée des expressions produites par un système d'équations combinatoires. Dans un premier temps, nous introduisons un cadre général pour décrire ce que nous entendons par expressions, et nous nous plaçons dans le cas où il y a un motif absorbant pour un opérateur donné, qui permet de simplifier les expressions tout en préservant leur sémantique. Nous prouvons alors qu'en simplifiant au maximum une expression aléatoire uniforme de taille n, nous obtenons une expression équivalente de taille constante en moyenne. Cela prouve que les expressions aléatoires uniformes manquent d'expressivité, dès qu'il y a un motif absorbant.  Par exemple, (a+b)* est absorbant pour l'union pour les expressions régulières sur {a,b}, donc les expressions régulières aléatoires peuvent être considérablement réduites en utilisant la simplification induite. Travail en commun avec Florent Koechlin et Cyril Nicaud.

This talk is devoted to the study of two arithmetical sources associated with classical partitions, that are both defined through the mediant of two fractions. The Stern-Brocot source is associated with the sequence of all the mediants, while the Sturm source only keeps mediants whose denominator is "not too large". Even though these sources are both of zero Shannon entropy, with very similar Renyi entropies, their probabilistic features yet appear to be quite different. We then study how they influence the behaviour of tries built on words they emit, and we notably focus on the trie depth. The talk deals with Analytic Combinatorics methods, and Dirichlet generating functions, that are usually used and studied in the case of good sources with positive entropy. To the best of our knowledge, the present study is the first one where these powerful methods are applied to a zero-entropy context. As the generating function associated with each source is explicit and related to classical functions in Number Theory, as the zeta function, the double zeta function or the transfer operator associated with the Gauss map, we obtain precise asymptotic estimates for the mean value of the trie depth that prove moreover to be quite different for each source. Then, these sources provide explicit and natural instances which lead to two unusual and different trie behaviours. Authors: Valérie Berthé, Eda Cesaratto, Frédéric Paccaut, Pablo Rotondo, Martin D. Safe and Brigitte Vallée

Les fonctions harmoniques discrètes jouent un rôle important en probabilités et sont fortement reliées à l’énumération de marches aléatoires. La transformation de Doob est un moyen de construire un processus aléatoire conditionné dans un cône à partir d’un processus aléatoire et une fonction harmonique positive s’annulant au bord du cône. Trouver des fonctions harmoniques positives associées à des processus aléatoires est donc un objectif naturel dans l’étude des marches aléatoires confinées. Il y a très peu de moyens de calculer des fonctions harmoniques discrètes. Dans cet exposé nous nous intéressons aux fonctions harmoniques discrètes aux conditions de Dirichlet dans les trois quarts de plan. Tandis que les marches (aléatoires) dans le quart de plan ont été très étudiées, le cas des marches évitant un quadrant n’a été développé que récemment. Nous étendons la méthode du quart de plan — résolution d’une équation fonctionnelle via un problème frontière à l’aide de transformations conformes — aux trois-quart de plan en appliquant la stratégie de découper le domaine en deux cônes symétriques. Nous obtenons une expression explicite simple de la fonction génératrice algébrique des fonctions harmoniques associées aux marches aléatoires évitant un quadrant. 

The {\bfseries inverse folding} problem consists in designing an RNA sequence $w$ that adopts a given target structure $S^{\star}$ as its unique secondary structure of minimum-free energy, with respect to some energy model $E$. More formally, one must have $$\textrm{argmin}_{S'\text{ comp. with }w} E_{S',w} = \{S^\star\}.$$ Additional design objectives include a min $\varepsilon$ value for the {\bfseries Boltzmann probability} $$\mathbb{P}(S \mid w)=\frac{e^{-E_{S,w}/RT}}{\mathcal{Z}_w} \ge \varepsilon,$$ with $R$ the Boltzmann constant, $T$ the temperature and $\mathcal{Z}_w:=\sum_{S'}e^{-E_{S',w}/RT}$ the partition function; or an upper bound $ \varepsilon'$ on the {\bfseries Ensemble defect}, the expected base-pair distance $d({\sf S},S^{\star})$ to $S^{\star}$ of a random, Boltzmann-distributed, structure ${\sf S}$: $$\mathbb{E}(d({\sf S},S^\star)\mid w) = \sum_{S'\text{ comp. with }w}\mathbb{P}(S'\mid w)\times d(S^\star,S) \le \varepsilon'.$$ While apparently diverse, those criteria share a common property: If one cannot be satisfied by any nucleotides assignment for a structure motif $M$, called a {\bfseries local obstruction}, then it cannot be satisfied, for any sequence, by any structure that contains $M$. In this work, we propose a flexible algorithm to establish a list of 100+ local obstructions within realistic energy models. The problem of counting secondary structures that avoid a set $\mathcal{M}$ of local obstructions is then equivalent to enumerating trees avoiding certain motifs. Using {\bfseries grammar modeling} and {\bfseries analytic combinatorics} techniques, we obtain refined asymptotic upper-bounds for the {\bfseries number of designable secondary structures}, for a variety of design objectives, all of which turn out to be {\bfseries exponentially smaller} than previously thought. Furthermore, we introduce a lower bound on the ensemble defect, and compute its distribution under the uniform distribution. We show that the approximated defect follows a normal law of expected value much larger than classic tolerances. This leads to an exponential decay of designable structures, even when the tolerance is too large to induce strict local obstructions.