0 -1 -2 -3 -4 1 2 3 4 5 1 2 3 4 5 J'ai souvent noué des relations amicales avec des collègues (qui se reconnaitront), et je les remercie pour tous les moments agréables passés et les découvertes faites ensemble. Je remercie aussi mes amis hors du travail, en particulier ceux de longue date avec qui je n'ai pas coupé le contact, même si celui-ci est parfois devenu ténu. J'ai une pensée particulière pour l'équipe de la colonie Mat'les vacances, à laquelle j'ai eu la chance d'être intégré à trois reprises. Et, bien entendu, je ne peux pas penser aux 10 ans qui se sont écoulés sans immédiatement avoir à l'esprit ma famille qui s'est métamorphosée pendant cette période. Merci avant tout à Mathilde pour tout ce chemin accompli et beaucoup de moments merveilleux. Merci à Oscar, Agathe et Iris d'être venus chambouler notre quotidien et de le rendre si intense. Merci à ma famille au sens large et à celle de Mathilde, d'une part pour leur présence quand on a besoin d'eux, à Zurich ou à Nancy (et même à Paris, Lyon, Londres, Marseille et Sienne lors de conférences et de visites de recherche), et d'autre part de parsemer notre route de retrouvailles festives. 4

C'est une habitude et je n'y dérogerais pas, je tiens à commencer cette page de remerciements par mes trois rapporteurs. Merci Philippe, Jean-François et Svante pour le temps que vous avez passé à lire mon manuscrit, et pour vos commentaires chaleureux. La recherche est un métier où on a parfois peu de retour sur son travail, et c'est extrêmement encourageant de lire l'appréciation de la part de personnalités scientifiques que j'estime beaucoup. Merci aussi de votre flexibilité dans le calendrier ; je n'ose pas écrire dans ce document public le nombre de mois écoulés entre la date prévisionnelle de fin de rédactionun peu ambitieuse -que j'avais initialement annoncée, et la date où je vous ai effectivement envoyé ma copie. Je remercie aussi Jérémie, un autre Philippe (qui a suivi les différentes étapes du parcours du combattant du candidat à l'HDR), Brigitte, Régine et Gilles d'avoir accepté de participer à mon jury ; c'est un honneur de présenter mes travaux devant vous, comme c'est un honneur de faire partie de la communauté française de combinatoire et de probabilités discrètes, dont vous représentez diverses facettes.

Je tiens aussi à remercier l'ensemble de mes co-auteurs. La majorité des travaux présentés dans ce manuscrit (ainsi que ceux que je n'ai pas pu présenter) ont été le fruit de collaborations scientifiques. Merci donc à Adrien, Maciej, Piotr, Pierre-Loïc, Katya, Alain, Victor, Ian, Guillaume, Éric, deux Jean-Christophe, Jean-Yves, Ashkan, Amarpreet, Per, Frédérique, Mathilde, Lucas, Adeline, Mickaël, Igor, Jehanne, Jacopo, Benedikt, deux Michael, Baptiste et Paul dans un ordre plus ou moins chronologique. Ce document serait évidemment moins riche sans vous, mais plus important encore, le travail de chercheur, tel que je l'ai vécu ces dix dernières années, n'aurait pas été aussi enrichissant. Je remercie également les étudiants que j'ai eu la chance d'encadrer et de co-encadrer jusqu'ici -en thèse, Omar, Dario, Helen, Raúl et Jacopo -, d'avoir parfois écouté de longues digressions expliquant pourquoi je voulais leur faire reformuler une simple phrase.

La richesse et l'intérêt du travail de chercheur doit aussi beaucoup aux interactions régulières avec les collègues de son propre institut et de sa communauté, même si cela ne se traduit pas au final par un papier co-signé -le contexte particulier des derniers 18 mois n'a que trop mis cela en évidence. Merci donc à tous les collègues de Bordeaux, de Zurich et de Nancy, et à ceux rencontrés en conférences, qui m'ont rendu ces lieux si chaleureux. Merci aussi aux équipes administratives, qui m'ont toujours permis de faire mon travail dans les meilleures conditions possibles.

CHAPTER 1

Introduc on

The analysis of large random combinatorial structures is an active field of research at the interface between probability theory and combinatorics, sometimes referred to as discrete probability theory. Arguably, its most developed facet is the analysis of random graphs, as testified by the many books on the subject [JŁR00, Kol99, Spe01, Bol01, Pen03a, Mar04, Dur10, FK16, vdH17, Cha17, CAR17]. Yet, many other types of combinatorial objects have attracted the attention of the community, in particular trees, permutations, simplicial complexes, Young diagrams, . . . We start by giving a few general motivations for the study of random combinatorial structures.

Statistics

In many statistical problems, data is collected under the form of a combinatorial object o obs of size n (or a sample of such objects): graphs of interactions, permutations of the ranks in a competition compared to initial ranks, . . . With this data in hand, we want to perform some statistical test, in particular to test the hypothesis that the data is a sample from a given distribution µ th (e.g. the uniform distribution on objects of size n). To perform such a test, one chooses a functional f on the corresponding set of combinatorial objects and one compares f (o obs ) to the distribution of f (o) where o has distribution µ th . In practice, we often use a large n approximation for the distribution of f (o). An illustration of this is given in [Muk16, Section 3]: the author analyses the draft lottery data used to determine the order of enrolment of civils in the US army in the '70s and rejects the hypothesis that this data was generated as a uniform random permutation.

From a theoretical point of view, this assumes that we are able to find a limiting distribution for a well-normalized version of f (o), and many tools have been developed for such problems.

Analysis of algorithm A basic question in complexity analysis is the following: given a program taking some combinatorial structures as input, we want to find, for each n, the maximal amount of operations performed by the program on an object of size n (worst case analysis). This problem does not involve any random combinatorial structures, but there are two interesting variants that do. The first one is the average case analysis.

Here we fix a probability distribution on objects of size n and we want to compute the mean number of operations performed by the program on a random object of size n.

The second variant regards randomized algorithms. In this case, the randomness lies in the execution of the program itself.

For both of these variants, some complexity questions boil down to the analysis of functionals on random combinatorial structures; examples can be found in the book [START_REF] Ph | An introduction to the analysis of algorithm[END_REF]. There is nowadays a large community working on this type of problems, as testified in particular by the annual AofA (Analysis of Algorithms) meetings.

Statistical mechanics

The principle of statistical mechanics is to modelize a macroscopic system by taking at random a microscopic configuration among all those corresponding to the system. In some cases, these microscopic configurations are combinatorial objects, e.g. matchings in dimer models, integer partitions in TASEP (totally asymmetric exclusion models), alternating sign matrices in 6-vertex models, . . . The probability distribution used is most of the time either uniform or exponentially biased according to some energy function. The goal is to analyze some macroscopic quantity of the system, i.e. some functional f , when the size of the system/of the combinatorial object tends to infinity. This gives three different general motivations to study large random combinatorial objects. Building on that, discrete probability theory has become a field of research in itself with an interest in developing general methods for problems not necessarily guided by such applications. My work lies at this theoretical level.

We now discuss a selection of concepts in the theory of random combinatorial structures. This selection is clearly biased towards my own work. The goal is to put the main Chapters (2 to 4) of this habilitation thesis in context.

General methods for finding limi ng laws

In this section, C is a family of combinatorial objects and f a function of interest on C . For each n, we let o n be a random object of size n in C . As motivated above, a central question about random combinatorial structures is to find a limiting distribution for X n := f (o n ), possibly after normalization. Beyond basic counting arguments, various methods have been developed for this. We cite three of them: Analytic methods We consider the bivariate generating series, either ordinary or exponential, defined as C (z, t ) := o∈C z |o| t f (o) , or C (z, t ) :

= o∈C z |o| |o| ! t f (o) ,
where |o| is the size of the object o. In good cases, using some recursive structure of the class C and the functional f , one can compute or write some equations for the generating series C (z, t ). A limit law for f (o n ), where o n is a random object of size n, can then be derived by doing some suitable asymptotic analysis of C (z, t ). Some results of this habilitation thesis, in particular Theorem 4.2 on random permutations, have been obtained through such techniques.

Moment method Another approach considers the moments E[ f (o n ) r ] of our random variable X n = f (o n ). A classical result in probability theory states that if the moments of a sequence X n of random variables converge to that of a limiting distribution µ and if the limiting distribution µ is determined by its moments, then X n converges in distribution to µ. This is usually refered to as the moment method. It is particularly useful in discrete probability theory: indeed when f (o n ) counts some substructures of o n (possibly with weights), then it writes as a sum of indicator functions (or weight functions), and one can expand f (o n ) r to compute the expectation.

I have been using the moment method in several of my works, e.g. for Theorem 2.10 on random Young diagrams. The theory of dependency graphs, to which I contributed (see Section 1.2 and Chapter 3), also relies on the moment method.

Stein's method Another method to prove convergence in distribution is the so-called Stein's method. The development and applications of Stein's method has been an active field of research since its introduction by Stein in the early '70s; see [START_REF] Ross | Fundamentals of steins method[END_REF] for a survey.

Roughly, the principle is the following. First, one finds a functional equation characterizing the limiting distribution. For example, it can be shown that a realvalued random variable Z follows a standard Gaussian distribution if and only if

E[g (Z )] = E[Z g (Z )
] for all compactly supported continuous function g . Note that this step does not depend on the model that we are studying, only on the limiting distribution; thus for classical limiting distributions (Poisson or Gaussian laws in particular), such characterizations are now well-known.

The second step is to prove that X n = f (o n ) "satistifes approximately" this functional equation; such an approximate equation implies that X n converges to Z in distribution, and, additionally, provides a control on the error term in this convergence. We refer to Theorem 2.12 for an example of application from our own work, regarding random Young diagrams.

Dependency graphs

Among the various techniques developed to apply the moment method or Stein's method, there is one of particular interest for this thesis: dependency graphs. Roughly, the principle is the following. We are interested in proving the asymptotic normality (i.e. the convergence to a Gaussian distribution after normalization) of a statistics of the form X n = α∈A Y α ; substructure counts typically are of this form, where the Y α are indicator functions. If the Y α were i.i.d., asymptotic normality would follow from the classical central limit theorem (for triangular arrays). We would like to relax the independence hypothesis, assuming only that "some" of the variables Y α are independent. The idea is to encode this information in a graph with vertex set {Y α , α ∈ A}, putting edges between pairs of dependent variables; this is called a dependency graph for the family {Y α , α ∈ A}. If this graph is sufficiently sparse, then we are close to the case of a sum of independent variables, and we might expect asymptotic normality. In this spirit, Janson [START_REF] Janson | Normal convergence by higher semiinvariants with applications to sums of dependent random variables and random graphs[END_REF] has given a concrete criterion for asymptotic normality using dependency graphs; this criterion has found since then various applications (see Section 3.1 below).

In this thesis, we extend Janson's result in two directions. First, in some cases, we give probabilistic estimates complementing asymptotic normality: control on the speed of convergence, moderate deviation estimates, concentration inequalities. Second, we define a notion of weighted dependency graphs, allowing to apply Janson's technique with weakly dependent random variables. This significantly enlarges its range of applications. These results are presented in Chapter 3 of the thesis.

From algebraic combinatorics to discrete probability theory

Connections between algebra and combinatorics are manyfold and form a research field called algebraic combinatorics. Standard objects of interest are for examples group representations, symmetric functions, and so on. Over the years, many concepts from this field have proved useful to solve problems in discrete probability theory.

A famous example of this kind concerns the length LIS(σ n ) of the longest increasing subsequence in a uniform random permutation σ n of size n. The question of finding its asymptotic behaviour was raised by Ulam in [START_REF] Ulam | Monte Carlo calculations in problems of mathematical physics[END_REF]. Hammersley [Ham72] proved, through probabilistic methods, that LIS(σ n )/ n converges to a constant c in probability, but could not determine the value of the constant.

To go further, a more algebraic point of view is useful. The length of the longest increasing subsequence of a permutation is the length of the first row of the so-called Robinson-Schensted shape of the permutations. We recall that Robinson-Schensted bijection maps permutations to pairs of Young tableaux of the same shape and was originally introduced to explain combinatorially an identity coming from representation theory of symmetric groups, see e.g. [START_REF] Sagan | The symmetric group : Representations, Combinatorial Algorithms, and Symmetric functions[END_REF]. It turns out that the Robinson-Schensted shape of a uniform random permutation is a random Young diagram with the so-called Plancherel distribution.

This distribution has an explicit product formula -the hook formula -making its analysis tractable. This approach was used independently by Vershik-Kerov [START_REF] Kerov | Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux[END_REF] and Logan-Shepp [START_REF] Logan | A variational problem for random Young tableaux[END_REF], to find a limit shape for Plancherel distributed Young diagrams, implying that Hammersley's constant c is equal to 2. This first-order convergence result for LIS(σ n ) was later refined to a fluctuation result, using again the connection with Plancherel distribution [START_REF] Baik | On the distribution of the length of the longest increasing subsequence of random permutations[END_REF].

This seminal series of work has been extended in many directions. In particular, Okounkov defined some generalization of (Poissonized) Plancherel measures on Young diagrams, called Schur processes, that can be analyzed using symmetric function theory [START_REF] Okounkov | Correlation function of Schur process with application to local geometry of a random 3-dimensional Young diagram[END_REF]. These were further generalized to Macdonald processes [START_REF] Borodin | Macdonald processes[END_REF]; interestingly, particular cases of these processes are connected to natural statistical physics models: q-TASEP, directed polymers, ...

In this habilitation thesis, we will discuss some deformations of the Plancherel measure arising from representation theory of Hecke algebras on the one side, and from the theory of Jack symmetric functions on the other side. In both cases, we provide a strong limit shape result and a weak fluctuation result (here, "weak" and "strong" should be understood in the topological sense, i.e. weak means that we describe the fluctuations of a natural family of functionals on these diagrams, while a strong result is a convergence result for the diagram itself). We emphasize that the algebraic structure behind each model is central to compute moments of the relevant random variables. These results are the topic of Chapter 2 of the thesis.

Scaling limits and universality

In addition to finding the limit of a functional f (o n ) of a random combinatorial object o n , there has been an increasing interest in the community in finding a limit for the object o n itself. When finding the limit involves to renormalize "distances" in the object in some sense, we speak of scaling limit. The limit shape results for random diagrams mentioned in the previous section are examples of scaling limit results. In another direction, scaling limits for random trees, random graphs and random maps have been an active area of research in the last thirty years; see e.g. [Ald93, Mie13, LG13, HS20].

An advantage of looking at scaling limit results rather than studying a functional is that it makes more apparent what we call universality phenomena. Namely, it turns out that various models, e.g. of trees and maps, share the same scaling limit. For example, large conditioned Galton-Watson trees converge to the so-called Brownian Continuum Random Tree as soon as the offspring distribution is critical with a finite second moment [START_REF] Aldous | The Continuum Random Tree III[END_REF][START_REF] Gall | Random trees and applications[END_REF].

A more recent, long awaited, result of this type involves random planar maps: many natural models (with fixed face degree, or with the so-called Boltzmann distributions) converge under mild conditions to the Brownian map [START_REF] Miermont | The Brownian map is the scaling limit of uniform random plane quadrangulations[END_REF][START_REF] Gall | Uniqueness and universality of the Brownian map[END_REF][START_REF] Marzouk | Scaling limits of random bipartite planar maps with a prescribed degree sequence[END_REF].

In the last chapter of this thesis (Chapter 4), we initiate a parallel line of study on random permutations. A notion of scaling limits for permutations was recently introduced in [HKM + 13]. Independently, a growing interest in analyzing random pattern-avoiding permutations has emerged in the combinatorics community, following initial works of Madras-Liu [START_REF] Madras | Random Pattern-Avoiding Permutations[END_REF] and Miner-Pak [START_REF] Miner | The shape of random pattern-avoiding permutations[END_REF]. However, before our work, scaling limit results for such models of random permutations were quite sparse. We have provided such results for a large family of pattern-avoiding permutation models, revealing some universality phenomenon in the spirit of the above-mentioned literature for trees and maps.

Outline of the thesis and other works of the author

The remaining chapters of this thesis aim at presenting the main contributions of the author in the field of random combinatorial structures. Namely, Chapter 2 gives results on random partitions, Chapter 3 on dependency graphs and Chapter 4 on scaling limits for random pattern-avoiding permutations. To emphasize the author's contributions, results

13

obtained in papers that I co-signed are in blue frames, while earlier results are in green.

To preserve a unity in the presentation and keep this document concise, we could obviously not present all the results obtained by the author after his PhD thesis. To fill this gap at the minimum, let us list here some topics not covered in this manuscript:

• algebraic and geometric perspectives on linear extensions of posets [BF09, BFLR12, FR12, AFNT15, Fér15], hook formulas for weighted counts of linear extensions of trees [START_REF] Féray | A multivariate hook formula for labelled trees[END_REF][START_REF] Féray | An edge-weighted hook formula for labelled trees[END_REF], and asymptotic enumeration of tableaux [START_REF] Dousse | Asymptotics for skew standard Young tableaux via bounds for characters[END_REF];

• the "dual combinatorics" of Jack polynomials [F Ś11, DF14, DF17, AF17];

• enumeration of permutation factorizations [START_REF] Féray | Bijective enumeration of some colored permutations given by the product of two long cycles[END_REF][START_REF] Féray | On products of long cycles: short cycle dependence and separation probabilities[END_REF] (including functions of Jucys-Murphy elements [START_REF] Féray | On complete functions in Jucys-Murphy elements[END_REF][START_REF] Féray | Partial Jucys-Murphy elements and star factorizations[END_REF] and analysis of related map models [START_REF] Chapuy | A simple model of trees for unicellular maps[END_REF]) and, more recently, their probabilistic analysis [FK18, FK19, FLT21];

• the theory of mod-ϕ convergence [FMN16, FMN19, FMN20] and an asymptotic normality result for uniform random elements in Coxeter groups [START_REF] Féray | On the central limit theorem for the two-sided descent statistics in Coxeter groups[END_REF];

• and a formal logic approach to permutations [START_REF] Albert | Two first-order logics of permutations[END_REF].

CHAPTER 2

Algebraic models of random par ons

A partition (or integer partition) is a non-increasing list (λ 1 , • • • , λ ℓ ) of positive integers.
Partitions are classical objects in number theory and enumerative and algebraic combinatorics; in particular, they index various bases of the symmetric function ring and the irreducible representations of symmetric and general linear groups [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF]. Partitions can be represented by geometric objects called Young diagrams. This geometric realization is crucial in asymptotic questions.

The study of random partitions (under various probability distributions) is a rich area, connected to representation theory, statistical physics, random matrix theory and enumerative geometry; we refer the reader to the surveys of Vershik [START_REF] Vershik | Asymptotic combinatorics and algebraic analysis[END_REF] and Okounkov [START_REF] Okounkov | The uses of random partitions[END_REF] for a presentation of these links.

In the following, we focus on models of random partitions arising from representation theory of the symmetric groups and deformations or analogues. In Section 2.1, we analyze the standard Plancherel measure of the symmetric group, focusing on Kerov's central limit theorem for Young diagrams. We then discuss two variations of the latter, related to Hecke algebras and Jack symmetric functions (Sections 2.2 and 2.3); this is based on works in collaboration with P.-L. Méliot and M. Dołęga, respectively [START_REF] Féray | Asymptotics of q-Plancherel measures[END_REF][START_REF] Dołęga | Gaussian fluctuations of Young diagrams and structure constants of Jack characters[END_REF]. Irreducible representations of the symmetric group S n are indexed by partitions, or equivalently Young diagrams, of size n. For an accessible introduction to the topic, see [START_REF] Sagan | The symmetric group : Representations, Combinatorial Algorithms, and Symmetric functions[END_REF]. We denote by dim(λ) the dimension of the irreducible representation indexed by λ. It is well-known that this is also the number of standard tableaux of shape λ, but we shall not use this combinatorial description here.

Plancherel measure and polynomial func ons on

Definition 2.1

The Plancherel measure for S n (or Plancherel measure for short) is the probability measure P Pl on the set of partitions of n such that for any partition λ of n, we have

P Pl (λ) = 1 n! (dim(λ)) 2 . (2.1)
The fact that (2.1) indeed defines a probability measure is an elementary result of representation theory of finite groups (Plancherel measures can be defined for all finite groups, not only for symmetric groups).

We now review (in a biased way) the literature on random Plancherel-distributed Young diagrams. The Plancherel measure has its origins in representation theory, but the special case of symmetric groups was popularized by its link with the so-called Ulam -this new approach also provides an independent proof of the limit shape result.

We also mention the work of Hora [START_REF] Hora | Central limit theorem for the adjacency operators on the infinite symmetric group[END_REF], who computed independently limiting moments of normalized character values, when the representation is indexed by a Plancherel random Young diagram; see Section 2.1.2.2 below.

In this section, we present the basic ideas of Kerov's approach, which has served as basis for our own work on variations of Plancherel measures. Most results are taken from [START_REF] Ivanov | Kerov's central limit theorem for the Plancherel measure on Young diagrams[END_REF],

the presentation is however rather different.

Limit results for character values

An algebraic family of observables

Kerov's approach starts with the following observation: the algebraic definition of P Pl , via dimension of irreducible representations of S n , gives us a natural family of well-behaved observables (i.e. random variables). These observables are the normalized irreducible character values of the symmetric group.

Let us be more specific. For a partition λ of size n, we denote ρ λ the irreducible representation indexed by λ; by definition of the notion of group representation, ρ λ maps permutations σ in S n to invertible endomorphisms ρ λ (σ) of some vector space V λ . Then the character χ λ (σ) is defined as the trace of the endomorphism ρ λ (σ). As said above, we let dim(λ) be the dimension of the underlying vector space V λ . Since group representations are by definition group morphisms, conjugate elements of S n are mapped to conjugate endomorphisms which have the same trace. In other terms, χ λ (σ) only depends on the conjugacy class of σ, which is determined by its cycle type1 .

The character is usually seen as a function on S n (the partition λ being fixed), but it will be convenient to reverse the point of view here and define, for a fixed permutation σ,

χσ (λ) = χ λ (σ) dim(λ) . (2.2)
As discussed above the function χσ only depends on the cycle-type µ of σ, so that we use the notation χµ := χσ . Finding nice/suitable expression for χµ (as a function of λ) is sometimes referred to as the dual approach to representation theory of the symmetric groups; see [START_REF] Śniady | Combinatorics of asymptotic representation theory[END_REF][START_REF] Féray | Approche duale des représentations du groupe symétrique[END_REF].

Fix a partition µ of n. If λ is taken at random, e.g. with the Plancherel measure, then χµ = χµ (λ) is a random variable. We consider, for a start, its expectation: from Eqs. (2.1) and (2.2), we get

E Pl [ χµ ] := λ n P Pl (λ) χµ (λ) = 1 n! λ n dim(λ)χ λ (σ) = 1 n! χ reg (σ). (2.3)
Here, the sums in the intermediate expressions run over partitions of n, σ is an arbitrary permutation of cycle-type µ and χ reg is the character of the regular representation 2 ρ reg of S n . In the case µ = (1 n ), the function χ(1 n ) is identically equal to 1, so that its expectation is trivially 1. For other partitions µ, the corresponding permutation σ is not the identity and ρ reg (σ) permutes the basis elements of the regular representation, letting no basis element fixed; hence its trace χ reg is equal to 0. To sum up, we get the following lemma.

Lemma 2.2

For any partition µ of n different from (1 n ), we have E Pl [ χµ ] = 0.

Higher moments

We now discuss joint moments of the variables ( χµ ) µ n , i.e. we fix n and arbitrary partitions µ (1) , . . . , µ (m) of n and we want to compute E Pl χµ (1) • • • χµ (m) . Using Lemma 2.2 and the identity

E Pl χ(1 n ) = 1, this expectation is the coefficient of χ(1 n ) in the expansion of χµ (1) • • • χµ (m)
on the basis3 ( χτ ) τ n . Using representation theory, we will see that this coefficient has a combinatorial meaning.

In the following, we denote by σ µ an arbitrary permutation in S n of cycle-type µ and by C µ the set of all permutations S n of cycle-type µ. By abuse of notation, C µ will also represent the formal sum of the permutations that it contains. This is an element of the group algebra C[S n ], and more precisely of its center Z (C[S n ]).

In general, with an element x in Z (C[S n ]), we can associate a function λ → tr[ρ λ (x)]/ dim(λ) on the set Y n of Young diagrams of size n. Basic representation theory arguments show that this is an algebra isomorphism4 from Z (C[S n ]) to the space F (Y n , C) of complex valued functions on Y n (endowed with the point-wise product). Using the conjugacy-invariance of characters, we have

|C µ | χµ (λ) = |C µ | tr ρ λ (σ µ ) dim(λ) = 1 dim(λ) tr ρ λ C µ ,
i.e. C µ is mapped to |C µ | χµ by the above algebra isomorphism.

Consequently, the problem of expanding χµ χν over the basis ( χτ ) τ n is reduced to the problem of expanding C µ C ν over the basis (C τ ) τ n . The latter is a combinatorial problem:

the coefficient of C τ in C µ C ν is the number of ways in which any fixed permutation of type τ can be written as a product of a permutation of type µ and a permutation of type ν.

More generally, the coefficient of χτ in

|C µ (1) |•••|C µ (m) | |C τ | χµ (1) • • • χµ (m)
is the number of ways in which a fixed permutation of type τ can be written as a product of permutations σ 1 , . . . , σ m of cycle type µ (1) , . . . , µ (m) , respectively. Taking the expectation, and using Lemma 2.2, we get:

For partitions µ (1) , . . . , µ (m) of n, the quantity

|C µ (1) | • • • |C µ (m) | E Pl χµ (1) • • • χµ (m)
is the number of factorizations σ 1 • • • σ m of the identity as a product of permutations σ 1 , . . . , σ m of cycle type µ (1) , . . . , µ (m) , respectively.

Asympto c normality of character values

There is no closed general formula5 to count the factorizations in the statement of Proposition 2.3, but some asymptotics will be enough for us. We now fix some integer k ≥ 2 and continue the discussion in the special case where

µ (1) = • • • = µ (m) = (k, 1 n-k )
with n large. In other terms, we are looking at the moments of the sequence of variables

χ[n] (k) := χ(k,1 n-k ) (for n ≤ k).
We use the standard "falling factorial" notation (n

) k = n(n -1) • • • (n -k +1).
Using Proposition 2.3 and the easy formula

|C (k,1 n-k ) | = (n) k /k, we have that (n) k k m E Pl χ[n] (k) m is the number of m-tuples (σ 1 , . . . , σ m ) of k-cycles such that σ 1 • • • σ m = id n ; below, we call
such m-tuples (σ 1 , . . . , σ m ) valid m-tuples. When m is even, there is a simple way to construct valid m-tuples (but not all of them!).

• First choose a matching of the set {1, . . . , m}, i.e. a collection of pairs {i 1 , j 1 }, . . . {i m/2 , j m/2 } whose disjoint union is {1, . . . , m}; we use the convention i t < j t in each pair, and matchings differing only by the order of the blocks are considered equal.

There are (m -1)!! such matchings6 .

• Next, we choose k-cycles σ i 1 , • • • , σ i m/2 with disjoint supports. There are (n) km/2 /k m/2 choices at this step.

• Finally, we set σ j t = σ -1 i t

(no choices at this step).

The construction ensures that the product Exhibiting these valid m-tuples is rather easy, but we recall that these are not all valid mtuples. However, one can prove (see [Hor98, Section 3.1]) that there are at most O (n (km-1)/2 ) valid m-tuples which are not of the form above. In particular, for m odd, there are at most O (n (km-1)/2 ) valid m-tuples in total. We finally get Furthermore, a finer analysis shows that, for any K ≥ 2, the variables

σ 1 • • • σ m is
(n) k k m E Pl χ[n] (k) m = δ m even (m -1)!! (n) km/2 / k m/2 + O n (km-1)/2
(n k/2 tr[ρ λ ((1, • • • , k))]/( k dim(λ)
)) 2≤k≤K converge jointly to independent Gaussian random variables.

One can also study moments of normalized characters tr[ρ λ (σ)]/ dim(λ), when σ is any fixed permutation of S k (we treated above only the case of cycles). The combinatorics is more subtle and in general, the limits no longer correspond to the moments of Gaussian variables, but to that of polynomials in Gaussian variables; see Hora's paper [START_REF] Hora | Central limit theorem for the adjacency operators on the infinite symmetric group[END_REF]. This prevents from deducing convergence in distribution from moment convergence, since some polynomials in Gaussian variables are not determined by their moments (see [START_REF] Slud | The moment problem for polynomial forms in normal random variables[END_REF], where explicit criteria under which such polynomials are or are not determined by their moments are given). We will see a way around this problem in the next section.

Polynomial func ons on Young diagrams I

Given a partition µ = (µ 1 , • • • , µ ℓ ) of size k and an integer n, we consider the following element of the center of symmetric group algebra C[S n ]:

Cl µ;n = (a 1 , • • • , a µ 1 ) (a µ 1 +1 , . . . , a µ 2 ) • • • (a µ 1 +...+µ ℓ-1 +1 , • • • , a k ),
where the sum runs over k-tuples (a 1 ,

(λ) =    |λ|(|λ| -1) • • • (|λ| -|µ| + 1) χµ∪(1 n-k ) (λ) 0 if |µ| > |λ|.
(2.5) Moreover, Eq. (2.4) implies that

Ch µ Cl ν = τ g τ µ,ν Ch τ , (2.6)
as functions on all Young diagrams (here, the independence of g τ µ,ν from n is key). More precisely we have the following result, see [IO02, Proposition 4.5], which is based on [START_REF] Ivanov | The algebra of conjugacy classes in symmetric groups, and partial permutations[END_REF].

Proposition 2.5

The linear span Span(Ch

µ ; µ partition) in F Y , C is closed under multiplication. Moreover, Ch µ Ch ν -Ch µ∪ν lies in Span(Ch π ; |π| < |µ| + |ν|).
The subalgebra of F Y , C spanned by (Ch µ ) µ partition is called the algebra of polynomial functions on Young diagrams; we denote it by A char . Using the second part of the proposition and an easy triangularity argument, we can show that (Ch (k) ) k≥1 is an algebraic basis of

A char .
We now come back to Plancherel distributed Young diagrams. A function F on all Young diagrams defines in this context a sequence of random variables X n = F (λ n ), where λ n is a Plancherel distributed diagram of size n. Theorem 2.4 (and the comment below) implies the joint convergence (after normalization) of Ch (k) , for k ≥ 2, towards independent Gaussian random variables. In principle, this allows to find the limit behaviour of any polynomial combination of (Ch (k) ) k≥1 , i.e. of any element F of A char (recall that Ch (1) (λ) = |λ|, so this is a trivial deterministic quantity). In practice, it requires to find the expansion of F as a polynomial in (Ch (k) ) k≥1 , or at least to find the asymptotically dominant terms, which can be difficult.

Nevertheless, this strategy can be used to find the limit behaviour of Ch µ for any µ: see [IO02, Theorem 6.5], which gives convergence of Ch µ after renormalization in distribution and in moments, while the pure moment approach in the previous section only gives moment convergence. We will also use the same strategy with other functionals in A char in the next section.

Limit results for Young diagrams

From an algebraic point of view, the functions χσ are very natural observable of the diagram, so one can be perfectly satisfied by the description of their fluctuations. However, from a more combinatorial perspective, this is unsatisfying: we do not have information about the geometry of a large random Plancherel Young diagram. This is the topic of this section.

FIGURE 2.2

The Young diagram (7, 4, 3, 3, 2) drawn with English, French and Russian conventions.

0 -1 -2 -3 -4 1 2 3 4 5 1 2 3 4 5 FIGURE 2.3
The outer border of a Young diagram drawn with Russian convention, is the graph of a real-valued function on the real line.

Con nual Young diagrams

To state a limit result for Young diagrams, we first need to embed these discrete objects into a continuous space. To this end, it is better to use the Russian convention for drawing Young diagrams. The way we have drawn Young diagrams so far (e.g. on Fig.

Polynomial func ons on Young diagrams II

One way to analyze (sequences of ) continual Young diagram is to look at their moments:

for k ≥ 2, Kerov introduced the functional p k (ω) = k(k-1) 2 R (ω(x) -|x|)x k-2 d x.
look at the limiting behaviour of p k (ω n ) (for a fixed k ≥ 2).

It is not hard to see that, as functions on Young diagrams, the functions ( p k ) k≥2 are algebraically independent. They generate an algebra, which we will denote by A geom here. We have the following remarkable result.

Proposition 2.6

We have A char = A geom .

We will not give a full proof of this proposition (the curious reader can look at Propositions 3.3 and 3.4 in [START_REF] Ivanov | Kerov's central limit theorem for the Plancherel measure on Young diagrams[END_REF]), but we explain informally where it comes from. The key element is a formula to compute characters and relate them to the "geometry" of the diagram. For this, Ivanov and Olshanski prove the following formula, originally due to Wassermann [START_REF] Wassermann | Automorphic actions of compact groups on operator algebras[END_REF]: for any diagram λ,

Ch (k) (λ) = [t k+1 ] - 1 k k j =1 1 -( j -1 2 )t exp ∞ j =1 p j (λ)t j j 1 -(1 -kt ) -j , (2.7) where [t k+1 ]F is the coefficient of t k+1 in the series F and p j (λ) = i ≥1 (λ i -i + 1/2) j -(-i + 1/2) j (the sum is finite since λ i = 0 for i large enough) 9 .
The functions p j (λ) are different from the p k (λ) introduced above, but both encode in some sense the shape of the diagram. One can prove by combinatorial arguments and generating series manipulation that they generate the same subalgebra of functions on

Young diagrams A geom . The above formula implies directly that Ch (k) is in A geom so that

A char ⊆ A geom .
A careful analysis of the highest term in (2.7) (for an appropriate gradation) shows that

(2.7) can be inverted (though not explicitly) and p j can be expressed in terms of the characters Ch (k) . This concludes the proof that A char = A geom .

Law of large numbers for polynomial func ons and for the rescaled Young diagrams

We note that the above argument is constructive; it gives an expression of Ch (k) in terms of some generator p j of the algebra A geom . For small values of j , we can invert it and get expressions of p j in terms of Ch (k) . The formulas relating p j to ph , which we did not detail above, are also effective. A subtle analysis of these formulas yields the asymptotically dominant term of ph for all h, when expressed in terms of Ch (k) . Since we know the asymptotic behaviour of the functions (Ch (k) ; k ≥ 2) (Theorem 2.4), we can infer those of ph . The first result us a first-order convergence result for ph (λ n ), where λ n is a Planchereldistributed random Young diagram of size n. Namely, we have the following convergence in probability as n tends to +∞:

n -h/2 ph (λ n ) -→    2m m if h = 2m is even; 0 otherwise. ( 2
Ω(x) =    2 π x arcsin( x 2 ) + 4 -x 2 if |x| ≤ 2; |x| if |x| ≥ 2.
(2.9)

A simple computation, via integration by part, yields

ph (Ω) =    2m m if h = 2m is even; 0 otherwise.
(2.10)

In other terms, the moments of Ω match the limiting moments10 of λn . Using the regularity of λn and Ω (both are 1-Lipschitz funcitons) and a small additional combinatorial argument (showing that λn is with high probability supported on a fixed compact interval), we can deduce from the moment convergence ph ( λn ) → ph (Ω) the uniform convergence of the function λn . Namely, the following result is Theorem 5.5 in [START_REF] Ivanov | Kerov's central limit theorem for the Plancherel measure on Young diagrams[END_REF].

Theorem 2.7: Law of large numbers for Plancherel measure Let λ n be a random Young diagram of size n, distributed with Plancherel measure.

Then the outer border of the rescaled Young diagram λn tends to Ω in probability in the space of continuous functions from R to R endowed with the supremum norm.

Central limit theorem for polynomial func ons

We now turn to the central limit theorem. Rather than giving the joint fluctuations of ( ph ; h ≥ 2), we perform a triangular change of basis so that the resulting functions are asymptotically independent. Namely, let us consider Chebyshev polynomials u k (x) of the second kind11 defined by This theorem can be informally interpreted as a Gaussian limit theorem for the function λn (x)-|x| in a space of generalized functions (after centering and normalization); see [START_REF] Ivanov | Kerov's central limit theorem for the Plancherel measure on Young diagrams[END_REF]Section 9]. In this sense, it can be seen as a second-order asymptotic result, refining the law of large numbers given in Theorem 2.7.

u k (x) = k/2 j =0 (-1) j k -j j x k-2 j , or equivalently, u k (2 cos(x)) = sin (k + 1)x sin(x) . Then we set qh (λ) = R 1 2 (ω(x) -|x|)u h (x)d x. ( 2

Hecke algebras and the q-Plancherel measure

This section reports on the article [START_REF] Féray | Asymptotics of q-Plancherel measures[END_REF], written in collaboration with P.-L. Méliot. The main results are a law of large number and a central limit theorem for polynomial functions on random Young diagrams distributed with the so-called q-Plancherel measure. We first introduce this measure, present our results and then discuss briefly some elements of proof, emphasizing differences with the usual Plancherel setting.

Background on the q-Plancherel measure

The q-Plancherel measure is a natural q-analog of the Plancherel measure, introduced by Kerov in [START_REF] Kerov | q-analogue of the hook walk algorithm and random Young tableaux[END_REF]. The most direct way to define it is an explicit formula for the probabilities of individual diagrams. Namely, we set

D λ (q) = q b(λ) {n} q ! □∈λ {h(□)} q , where b(λ) = i ≥1 (i -1)λ i is a standard quantity in symmetric function theory, h(□)
is the hook-length of the box □, {k} q = 1 + q + • • • + q k-1 the standard q-integer and {n} q ! = {1} q {2} q • • • {n} q is the q-factorial. Then, for each q > 0, we define a probability measure 12 M n,q on the set of Young diagrams of size n as follows:

M n,q (λ) = D λ (q) dim λ {n} q !
for any λ n. For q = 1, we recover the usual Plancherel measure on Young diagrams. Due to some symmetry between the cases q > 1 and q < 1, in the sequel, we assume q < 1.

Remarkably, this measure can also be constructed by a random walk on the Young graph (i.e. the graph with vertices indexed by all partitions, and directed arrows representing the addition of a single box). This was proved in the original article of Kerov [Ker92] using a qdeformation of the hook walk algorithm of Greene, Nijenhuis, and Wilf [START_REF] Greene | A probabilistic proof of a formula for the number of young tableaux of a given shape[END_REF]. Moreover, as in the usual q = 1 setting, the q-Plancherel measure for general q is also connected to random permutations through Robinson-Schensted (RS) algorithm. To this end, we consider a random permutation σ of size n, such that for any τ, the probability of having τ is

P[σ = τ] = q maj(τ) /{n} q !,
where maj(τ) is the sum of the positions of the descents of τ, called major index 13 of τ. Then the shape λ of the pair of tableaux associated by the RS algorithm to σ is a random partition distributed with q-Plancherel measure [START_REF] Strahov | A differential model for the deformation of the Plancherel growth process[END_REF].

Fig. 2.5 (taken from [START_REF] Féray | Asymptotics of q-Plancherel measures[END_REF]), shows Young diagrams λ of size up to 4, together with the quantities D λ (q) (called generic degrees), the q-Plancherel weights M n,q (λ) and the transition probabilities in the random walk construction of the q-Plancherel measure. Additionally, Fig. 2.6 (also taken from [START_REF] Féray | Asymptotics of q-Plancherel measures[END_REF]) shows a large random Young diagram distributed with q-Plancherel measure for q = 1/2.

There is yet another way to see the q-Plancherel measure: via representation theory.

For this, we need to introduce the Hecke algebra, which is a well-studied deformation of the symmetric group algebra; see e.g. [START_REF] Mathas | Iwahori-Hecke Algebras and Schur Algebras of the Symmetric Group[END_REF][START_REF] Geck | Characters of Finite Coxeter Groups and Iwahori-Hecke Algebras[END_REF] for introductions to this topic. It can be defined through generators and relations as follows: H n,q is the free associative algebra with generators T 1 , . . . , T n-1 quotiented by the braid relations:

T i T i +1 T i = T i +1 T i T i +1 (for all i ≤ n -2);
the commutation relations:

T i T j = T j T i (for all i , j ≤ n -1 s.t. |i -j | > 1);
and the quadratic relations: (T iq)(T i + 1) = 0 (for all i ≤ n -1).

When q = 1, the T i can be identified with the transposition s i = (i i +1) of the symmet-

12 See [START_REF] Kerov | q-analogue of the hook walk algorithm and random Young tableaux[END_REF] for a proof that this is indeed a probability measure. 13 The major index is a classical permutation statistics in the enumerative combinatorics literature. In particular, it is well-known that it is a Mahonian statistics, meaning that τ∈S n q maj(τ) = {n} q !. Hence, the formula in the main text indeed defines a probability measure.

26

D = 1 ; M1,q = 1 1 q+1 q q+1 D = 1 ; M2,q = 1/(q + 1) M2,q = q/(q + 1)

D = q q 2 q 2 +q+1 q+1 q 2 +q+1 q 2 +q q 2 +q+1 1 q 2 +q+1
M3,q = (2q)/(q 2 + q + 1) D = q 2 + q q 3 +q q 4 +2q 3 +2q 2 +2q+1 D = q 3 M3,q = q 3 /(q 3 + 2q 2 + 2q + 1) q 3 q 3 +q 2 +q+1 D = q 6 M4,q = q 6 /(q 6 + 3q 5 + 5q 4 +6q 3 + 5q 2 + 3q + 1)

M3,q = 1/(q 3 + 2q 2 + 2q + 1)

D = 1 D = q 4 + q 2
q 2 +q+1 q 3 +q 2 +q+1 q 4 +q 3 +q 2 q 4 +2q 3 +2q 2 +2q+1 D = q 3 + q 2 + q M4,q = (3q)/(q 4 + 2q 3 + 2q 2 + 2q + 1) D = q 5 + q 4 + q 3 M4,q = (3q 3 )/(q 4 + 2q 3 + 2q 2 + 2q + 1)

1 q 3 +q 2 +q+1 D = 1 M4,q = 1/(q 6 + 3q 5 + 5q 4 +6q 3 + 5q 2 + 3q + 1)
M4,q = (2q 2 )/(q 4 + 3q 3 + 4q 2 + 3q + 1) q 3 +q 2 +q q 3 +q 2 +q+1 q 2 +q+1 q 4 +2q 3 +2q 2 +2q+1 Figure 3. Generic degrees, q-Plancherel measures and q-transition probabilities on diagrams of size n ≤ 4.

Definition -Proposition 1. The q-Plancherel process is the markovian partition-valued process (λ n ) n∈N defined by:

λ 0 = ∅ ; p q (λ, Λ) = q b(Λ)-b(λ) ∈λ {h( )}q ∈Λ {h( )}q if λ Λ in the Young graph, 0 otherwise.
Its marginal distribution of the n-th partition of the q-Plancherel process is called the q-Plancherel measure. This probability measure M n,q on the set Y n of Young diagrams of size n can be alternatively defined by:

∀λ n, M n,q ({λ}) = M n,q (λ) = D λ (q) dim λ {n!} q ,
where dim λ is the dimension of the irreducible representation of S n indexed by λ, and D λ (q) is its generic degree as defined in [GP00, Chapter 8]:

D λ (q) = q b(λ) {n!} q ∈λ {h( )} q .
The equivalence between the two definitions (as marginal distribution of a markovian process or via a direct formula for the probability to pick each diagram) is explained in [Str08, Section 3].

In the next two paragraphs, we explain why this q-analog is natural in the context of Hecke algebras and general linear groups in finite characteristic. FIGURE 2.5 Generic degrees, q-Plancherel measures and q-transition probabilities on diagrams of size n ≤ 4. ric group and H n,1 is isomorphic to the symmetric group algebra. It can be shown that for generic q, the algebra H n,q is semi-simple14 and has irreducible representations V λ,q indexed by partitions of n. Moreover the dimension of V λ,q is always equal to dim(λ), independently from q. We call q-character and denote by χ λ,q the character of V λ,q .

It is well-known that the braid and commutation relations allow to define unambiguously an element T σ of H n,q for any permutation σ in S n . These elements form a basis (T σ ) σ∈S n of H n,q . Thus, we can consider the regular trace τ q of the Iwahori-Hecke algebra, which is a linear map H n,q → C mapping any (T σ ) σ =id to 0 and T id to 1. This is an analogue of the trace of the regular representation of S n . When q is a power of a prime, one can give a representation-theoretical interpretation of τ q [FM12, Section 2.3], but for generic q, one just thinks at it as a linear map. We then have the expansion, analogue of eq. (2.3),

τ q = λ n D λ (q) {n!} q χ λ,q = λ n M n,q (λ) χ λ,q dim(λ) .
Consequently, the dual normalized q-character defined as χq σ (λ) :=

χ λ,q (T σ ) dim(λ) satisfies E M n,q [ χq σ ] = 0 (2.12)
for any σ = id. This property, extending Lemma 2.2, characterizes the q-Plancherel measure and will be the basis of our investigations.

FIGURE 2.6

A random Young diagram of size 200, taken with q-Plancherel measure (q = 1/2).

q-polynomial func ons

In this section, we present a q-version of the Ch-basis of the algebra A char using qcharacters of the Iwahori-Hecke algebras. To this end, for a partition ρ of n, we define

σ ρ = (1, 2, . . . , ρ 1 ) (ρ 1 + 1, ρ 1 + 2, . . . , ρ 1 + ρ 2 ) • • • (ρ 1 + • • • + ρ r -1 + 1, . . . , ρ 1 + • • • + ρ r ),
which is a specific permutation of type ρ. We then set, for any partition µ,

Ch µ,q (λ) =    |λ|(|λ| -1) • • • (|λ| -|µ| + 1) χq σ µ1 |λ|-|ρ| (λ) if |µ| ≤ |λ|; 0 else.
Unlike in the symmetric group case, the character value would change if one replaces σ µ1 |λ|-|µ| by another permutation on type µ1 |λ|-|µ| , but this does not create difficulties.

It turns out that these normalized q-characters can be expressed in terms of the usual Ch (i.e. corresponding to q = 1) and vice-versa. More precisely, the following was proved in [FM12, Section 3.6], based on a result of Ram [START_REF] Ram | A Frobenius formula for the characters of the Hecke algebra[END_REF]. We denote A := A char = A geom the algebra of polynomial functions on Young diagrams introduced above in Sections 2.1.2.4 and 2.1.3.2. In the following, we use some standard notation of symmetric function theory (see e.g. [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF]), namely, for a partition ρ, ℓ(ρ) is its length, z ρ a standard combinatorial factor, m ρ , p ρ and h ρ are respectively the monomial, power-sum and complete homogeneous basis of the symmetric function ring, and f g is the Hall scalar product between functions f and g .

Proposition 2.9

The family (Ch µ,q ), indexed by partitions µ of all sizes, is a C(q)-basis of the algebra A(q) := A ⊗ C C(q). Moreover, the transition matrices between the Ch µ,q and the Ch µ are triangular, given as follows: for any partition µ of k, one has

(q -1) ℓ(µ) Ch µ,q (λ) = ρ k i (q ρ i -1) z ρ p ρ h µ Ch ρ (λ);
(2.13)

Ch µ (λ) i (q µ i -1) = ρ k (q -1) ℓ(ρ) m ρ p µ Ch ρ,q (λ).
(2.14)

Our results

We start with an informal description of the strategy that we used to study the q-Plancherel measure. Using eqs. (2.12) and (2.14), we can compute the expectation of the random variable Ch µ for all µ:

E[Ch µ ] = (1 -q) |µ| i (1 -q µ i ) n(n -1) . . . (n -|µ| + 1).
Higher moments can then be computed (at least asymptotically) using the combinatorial description of products of Ch µ mentioned in Section 2.1.2.4. This will give us the asymptotic behaviour of Ch µ for any µ. In a second step, we consider some functional describing the geometry of the diagram, which lies in the algebra A(q), and expand them in the basis (Ch µ ).

Though this strategy is similar to the case q = 1, the framework is qualitatively different for other values of q:

• Ch µ has an expectation of order n |µ| and is concentrated around its expectation, while for q = 1, it is centered with fluctuations of order n |µ|/2 (when µ has no parts equal to 1).

• the diagrams have long rows and columns so that the encoding as continual Young diagrams and the renormalization by n are not relevant any more.

Consequently, the functionals ph used in Section 2.1.3.2 do not encode well the geometry of the diagrams any more. We use instead the so-called the power sums of Frobenius coordinates. These are defined as follows: for a diagram λ, we let d be the size of its Durfee square, i.e. the largest integer such that λ d ≥ d . Then, writing λ for the conjugate partition of λ, we

set PF k (λ) = d i =1 (λ i -i + 1/2) k -(λ i -i + 1/2) k .
We now state first-and second-order convergence results for PF k , proved in [START_REF] Féray | Asymptotics of q-Plancherel measures[END_REF].

Theorem 2.10: Asymptotics of q-Plancherel measures

For each n ≥ 1, let λ n be a q-Plancherel-distributed random Young diagram. Then, as n tends to +∞ we have convergence in probability of the renormalized power sums PF k (λ):

∀k ≥ 1, PF k (λ n ) n k -→ (1 -q) k
1q k . Moreover, if we denote the renormalized centered power sum by

W n,q,ℓ (λ) = n PF ℓ (λ n ) -E[PF ℓ ] n ℓ ,
then, for any k ≥ 1, the random vector (W n,q,1 ,W n,q,2 , . . . ,W n,q,k ) converges in law towards a Gaussian vector of covariance matrix

cov(W q,ℓ ,W q,m ) = ℓ m (1 -q) ℓ+m 1 1 -q ℓ+m-1,1 - 1 1 -q ℓ,m .
The method also yields a central limit theorem for q-characters giving a q-analogue of Theorem 2.4, see [START_REF] Méliot | Gaussian concentration of the q-characters of the Hecke algebras of type A[END_REF]. The first-order convergence in Theorem 2.10 implies a convergence result for the row-lengths of the diagram: namely, for any fixed i ≥ 1, the quantity λ i /n tends in probability to (1-q) q i -1 [FM12, Theorem 1]. The simulation in Fig. 2.6, where each of the first rows is around half the previous one, illustrates well this limit theorem. Unfortunately, we cannot directly infer a central limit theorem for the row-lengths from the one for

On extremal characters of S ∞ and the Thoma simplex

The q-Plancherel measure is actually a special case of a larger family of measures, linked to representation theory of S ∞ = n≥1 S n , or more precisely to the classification of its (extremal) characters. It has been shown by Thoma that these characters are indexed by the following simplex, now called the Thoma simplex:

∆ ∞ = (α i ) i ≥1 , (β i ) i ≥1 , γ ∈ [0, 1] N N {0} : γ + i ≥1 (α i + β i ) = 1 .
Characters are functions on S ∞ and induce by restriction to S n , some central functions on S n . The latter can be decomposed as a nonegative sum of irreducible S n -characters, inducing a probability distribution on Young diagrams of size n.

We skip the details, the point being that with each element of ∆ ∞ is associated a sequence (P n ) n≥1 of probability measures on Young diagrams of size n. The measures obtained this way include examples discussed so far. The Plancherel measure corresponds to γ = 1, α i = β i = 0, while the q-Plancherel measure for q < 1 is associated with

α i = (1-q) q i -1 and γ = β i = 0.
With this point of view, the law of large numbers in Theorem 2.10 was already known [KV81, KOV04]. The central limit theorem is however new, and the method presented here can be extended to other points of the Thoma simplex, see [START_REF] Méliot | A central limit theorem for the characters of the infinite symmetric group and of the infinite Hecke algebra[END_REF][START_REF] Bufetov | A central limit theorem for extremal characters of the infinite symmetric group[END_REF].

A deforma on linked with Jack symmetric func ons

In this section, we present a law of large numbers and a central limit theorem for random partitions distributed according to a second family of one-parameter deformations of the Plancherel measure. This one-parameter deformation is defined using the so-called Jack symmetric functions. This is based on the paper [START_REF] Dołęga | Gaussian fluctuations of Young diagrams and structure constants of Jack characters[END_REF], written in collaboration with M. Dołęga.

Background and defini on

Let us start by giving some motivated definition. We have seen that the Plancherel measure is related to the representation theory of the symmetric groups S n . On the other hand, a remarkable well-known result of Frobenius connects irreducible character values of S n to the ring of symmetric functions. Namely, if p µ and s λ denote respectively the power sum and Schur symmetric functions, then one has Eq. (2.15) can be deformed, replacing Schur functions by the more general Jack symmetric functions:

p µ = λ n χ λ µ s λ . ( 2
p µ = λ n ϑ λ,(α) µ J (α) λ .
(2.16) Specializing α to 1 gives ϑ λ,(1) µ = dim(λ) n! χ λ µ . In particular, for µ = (1 n ), we have ϑ λ,(1)

(1 n ) = dim(λ) 2 n!
, which is the Plancherel probability of the partition λ. For general α, one can prove that the formula P (α) n (λ) = ϑ λ,(α) (1 n ) still defines a probability measure on Y n (i.e. these are nonnegative numbers that sum up to 1). This is a natural deformation of the Plancherel measure, which we call Jack-Plancherel measure of parameter α. A simulation is given on Fig. 2 For a further motivation, we need to make a small detour through random matrix theory.

The following discussion is meant to be informal, more details can be found, e.g., in the introduction of [START_REF] Guionnet | Rigidity and edge universality of discrete βensembles[END_REF]. Of fundamental interest in random matrix theory are the eigenvalues

x 1 > • • • > x N of
an N × N Hermitian random matrix with independent complex Gaussian entries over the main diagonal. The distribution of {x 1 , . . . , x N } is called the Gaussian unitary ensemble or GUE for short. Considering instead a symmetric real random matrix, we get the Gaussian orthogonal ensemble or GOE for short. It has been observed that there is a natural continuous deformation interpolating between these two distributions, which is called Gaussian β ensembles or GβE: for β = 2, it specializes to the GUE; for β = 1 to the GOE. These particle systems (the x i are sometimes thought of as particles on the real line) are now wellunderstood: see [START_REF] Valkó | Continuum limits of random matrices and the brownian carousel[END_REF][START_REF] Ramirez | Beta ensembles, stochastic airy spectrum, and a diffusion[END_REF] for the description of the large N bulk and edge fluctuations of the GβE 16 . These GβE models are continuous particle systems, in the sense that the x i are continuous random variables. A natural question is to find analogue results for discrete particle systems, i.e. where the x i live in a discrete set, e.g. are integers. Partitions can be seen as discrete particle systems by setting x i = λ i +N -i . It turns out that the Plancherel measure provides a good discrete analogue of the GUE, in the sense that its algebraic structure makes it tractable and that its asymptotic behaviour resembles that of the GUE (see, e.g., [START_REF] Okounkov | The uses of random partitions[END_REF]). More generally, Jack-Plancherel measure is meant to be a discrete analogue of the GβE (for β = 2/α).

We will provide results in this direction, showing some similarity of Jack-Plancherel random partitions with the GβE ensembles.

Some nice observables: Jack characters

The normalized characters Ch µ used to analyze the usual Plancherel case have a natural α-deformation. Namely, we consider the expansion of Jack symmetric functions on the power sum basis

J (α) λ = ρ: |ρ|=|λ| θ (α) ρ (λ) p ρ .
(2.17)

For α = 1, one has J (1) λ = |λ|! s λ dim(λ)
and thus, θ (1) ρ (λ) = |λ|! χρ (λ). We now look for a normalization analogue to the definition of Ch µ in (2.5). Recall that for a partition µ, m i (µ) is the number of parts equal to i in µ, and z µ is the combinatorial factor i ≥1 i m i (µ) (m i (µ))!; we define

Ch (α) µ (λ) :=    α -|µ|-ℓ(µ) 2 |λ|-|µ|+m 1 (µ) m 1 (µ) z µ θ (α) µ,1 |λ|-|µ| (λ) if |λ| ≥ |µ|; 0 if |λ| < |µ|.
From now on, we refer to the functions Ch (α) µ as Jack characters, even though they have no representation-theoretical interpretation for general α. One can check easily that for α = 1, we recover the function Ch µ defined in (2.5), i.e. we have Ch (1) µ = Ch µ . Moreover, Jack characters have a trivial expectation with respect to Jack-Plancherel measure, generalizing 16 For a random particle system x 1 > • • • > x N , studying the large N "edge fluctuations" consists in finding a distribution limit for a renormalized version of the vector (x 1 , • • • , x k ) for a fixed k (and of (x N , • • • , x N -k+1 ) if this does not follow by symmetry); in words, we are looking at the first (and last) few particles, sometimes called the extreme ones. For "bulk fluctuations", we look at a limit for sets of the form {x i b(N )-a(N ); i ≤ N }∩[-K , K ] (for any fixed K > 0) where a(N ) is chosen to be of the same order of magnitude as x 1 , in the interval (x N , x 1 ) but far from its extremities and b(N ) is chosen such that the number of particles in this interval remain stochastically bounded. In words, we are looking at a fixed number of particles in a small interval in the interior of the particle system. In both cases, these are local statistical information on the system, usually hard to obtain.

E P (α) n (Ch (α) µ ) = 0. (2.18)
This equation follows easily from a classical orthogonality property of Jack symmetric functions; we refer to [Mat10, Section 8] for details.

At this stage, we might wonder whether Jack characters span a subalgebra of the space of functions of Young diagrams, as usual characters. Remarkably, it the case and this relies on the notion of α-shifted symmetric functions.

Definition 2.11

An α-shifted symmetric function F is a sequence (F N ) N ≥1 satisfying the following properties.

• (shifted symmetry) For each

N ≥ 1, F N is a polynomial in N variables x 1 , • • • , x N with coefficients in Q(α) that is symmetric in x 1 -1/α, x 2 -2/α, . . . , x N -N /α.
• (stability) for each N ≥ 1,

F N +1 (x 1 , . . . , x N , 0) = F N (x 1 , . . . , x N ). • (degree bound) sup N ≥1 deg(F N ) < ∞.
A function F on all Young diagrams can be seen as the sequence (F N ) N ≥1 of its restrictions (λ 1 , ..., λ N ) → F (λ 1 , ..., λ N ) to Young diagrams of length at most N (setting λ i = 0 for i > ℓ(λ)). Using this identification, in [Las08, Proposition 2], M. Lassalle proved that the functions Ch (α) µ are shifted symmetric functions; moreover, they form a Q(α)-linear basis of the ring of α-shifted symmetric functions. This implies in particular that there are coefficients g π, (α) µ,ν in Q(α) such that

Ch (α) µ • Ch (α) ν = π partition of any size g (α) µ,ν;π Ch (α) π . (2.19)
These coefficients, called structure constants of Jack characters, play a key role in our work.

REMARK For α = 1, that Ch µ is a 1-shifted symmetric function is a direct consequence of eq. (2.7). I am not aware of an analogue of eq. (2.7) for general α. The only known way to compute Ch (α) µ is by induction on k = |µ|, solving a linear system of exponentially growing size at each step; see [START_REF] Lassalle | Jack polynomials and free cumulants[END_REF]Section 9]. An analogue of eq. (2.7) would give a simpler way to compute Ch (α) µ and would certainly be useful.

REMARK

We recall that Jack symmetric functions are a degeneration of the celebrated Macdonald symmetric functions, depending on two parameters q and t . A natural question is whether the discussion above can be extended to this two-parameter setting. There is a natural notion of q, t -shifted symmetric function; see [START_REF] Okounkov | Shifted) Macdonald polynomials: q-integral representation and combinatorial formula[END_REF]. I am however not aware of a way to normalize the coefficients of the power-sum expansion of Macdonald symmetric functions in such a way that they define q, t shifted symmetric functions. This is a major obstacle in trying to generalize results of this section to the Macdonald setting.

Our results

Our first result is a central limit theorem for Jack characters under Jack-Plancherel measure, giving a natural analogue of Theorem 2.4. The original reference is [DF16, Theorem

1.2].
Theorem 2.12: Asymptotic normality of Jack characters Choose a sequence (Z k ) k=2,3,... of independent standard Gaussian random variables.

Let (λ (n) ) n≥1 be a sequence of random Young diagrams of size n distributed according to Jack-Plancherel measure of parameter α. Define

W k = αk θ (α) (k,1 n-k ) (αn) k/2 = Ch (α) (k) n k/2 k .
Then, as n → ∞, we have: Ω defined in (2.9). This convergence holds in probability in the space of continuous functions from R to R endowed with the supremum norm.

W k (λ (n) ) k=2,3,... d -→ (Z k ) k=2,
For the central limit theorem, we use the functionals qh ∈ A geom introduced in Eq. (2.11).

Theorem 2.14: Central limit theorems for Jack Plancherel measure Let λ n be a Jack-Plancherel distributed Young diagram of size n. We also denote by

Z 1 , Z 2 , • • • independent standard Gaussian random variables.
Then we have the following convergence in distribution (in the sense of finite-dimensional laws)

n qh A α ( λn ) -qh Ω h≥1 → Z h h + 1 - α -1 -α k + 1 1[k odd] h≥1 .
In the law of large number, the limit is indepedent of α. The central limit theorem is more interesting, because of the appearance of a deterministic shift in the fluctuations, which disappears for α = 1. This came first as a surprise for us, but we learned afterwards that such a term also appears when studying fluctuations of linear statistics of Gaussian β ensembles, see [DE06, Theorem 1.2]. This strengthens the analogy between Jack-Plancherel random partitions and Gaussian β ensembles.

Proof method: polynomiality in α and Stein's method

We discuss here the proof method of Theorem 2.12; the way Theorems 2.13 and 2.14 are deduced from it is then essentially similar to the α = 1 case (except that expressions of Ch (α) in terms of the p h or qh are less explicit than for α = 1). The goal is not to give a full account of the proof, but to enlighten the differences with the α = 1 case and some new ingredients that we introduced.

The basic idea for proving Kerov's central limit theorem for characters (i.e. the α = 1 case) was to analyze the moments of Ch (k) by expanding products Ch µ Ch ν on the Ch π basis.

The structure constants in this expansion have a combinatorial interpretation, thanks to the representation theory behind the scene, and one can determine asymptotically dominant terms.

In the general α case, we still have an expansion of Ch (α) µ Ch (α) ν on the Ch (α) π basis (see eq. (2.19) above). However, the structure constants g (α) µ,ν;π no longer have a combinatorial interpretation and we have to find a way around. By carefully analyzing Lassalle's algorithm to compute Ch (α) µ recursively, we could prove the following result. Let

n 1 (µ) = |µ| + ℓ(µ), n 2 (µ) = |µ| -ℓ(µ), n 3 (µ) = |µ| -ℓ(µ) + m 1 (µ).
Then we have:

Theorem 2.15: Polynomiality of structure constants of Jack characters

Fix three partitions µ, ν and π. The structure constant g (α) µ,ν;π is a polynomial in γ = α -1 -α with rational coefficients and of degree at most

min i =1,2,3 n i (µ) + n i (ν) -n i (π).
By definition, the structure constants g (α) µ,ν;π are rational functions in α; in particuler, the polynomiality alone in the above statement (without the degree bound) is already nontrivial. Nonetheless, the bound on the degree is important in that it allows to compute some of these structure constants by polynomial interpolation from the cases α ∈ {1/2, 1, 2} (for which representation-theoretical tools are available). It turns out that this is sufficient to determine the asymptotics of the lower moments (up to order 4) of Ch (α) (k) . Of course, knowing the asymptotics of moments up to order 4 is not enough to prove convergence to a Gaussian distribution. We therefore used an extra ingredient, called Stein's method (see Section 1.1 for a brief description of Stein's method). Stein's method had already been used in the context of Jack-Plancherel measure by Fulman [START_REF] Fulman | Stein's method, Jack measure, and the Metropolis algorithm[END_REF], who proved a central limit theorem for Ch (α) (2) . Our contribution was to extend it to the vector of all Ch (α) (k) (using a multivariate version of Stein's method, due to Reinert and Röllin [START_REF] Reinert | Multivariate normal approximation with Stein's method of exchangeable pairs under a general linearity condition[END_REF]); our polynomiality result for structure constants is crucial to control the various error terms appearing in the theorem of Reinert and Röllin. We note that as a byproduct of the proof, we get not only the convergence to a Gaussian vector as stated in Theorem 2.12 above, but also a control on the speed of this convergence; see [DF16, Theorem 1.3].

REMARK Our polynomiality result for structure constants of Jack characters is interesting independently of the probabilistic application presented here: in the appendices of [START_REF] Dołęga | Gaussian fluctuations of Young diagrams and structure constants of Jack characters[END_REF],

we give other applications of this result. Most notably, we used it to prove polynomiality results in two conjectures of Goulden and Jackson relating Jack polynomials and combinatorial maps on unoriented surfaces (see [START_REF] Goulden | Connection coefficients, matchings, maps and combinatorial conjectures for Jack symmetric functions[END_REF] for the original statement of the conjectures and [DF16, Section B.2] and [DF17] for our polynomiality results).

Some subsequent works

We briefly mention some later works, related to the paper [START_REF] Dołęga | Gaussian fluctuations of Young diagrams and structure constants of Jack characters[END_REF] presented here. In [START_REF] Guionnet | Rigidity and edge universality of discrete βensembles[END_REF], Guionnet and Huang found the edge fluctuations of Jack-Plancherel random Young diagrams. They coincide with that of Gaussian β ensembles, answering a question raised in our paper. In another direction, several other models of random partitions related to Jack symmetric functions have been introduced and studied (some of them generalize Jack-Plancherel measure, others are a bit different in that they involve partitions of fixed length but varying size). We refer to [BGG17, Hua21, D Ś19, Mol20] for central limit theorems for such models.

CHAPTER 3 (Weighted) dependency graphs

As explained in the introduction, a basic question in discrete probability theory is the following. Let o n be a random combinatorial object of size n and f a function of interest on the corresponding set of objects. The question is to understand the asymptotic behaviour of

X n = f (o n ).
When X n counts some small substructures and when the model has some kind of independence, we expect X n to be asymptotically normal, meaning that Xn :=

X n -E[X n ] Var(X n )
converges in distribution to a standard Gaussian variable Z . Proving this asymptotic normality might be difficult, and the goal of this chapter is to discuss general tools for such problems, namely the theory of dependency graphs and a weighted variant.

In Section 3.1, we present the standard theory of dependency graphs, as developed by Janson. Section 3.2 reports on an improvement of the cumulant bound in this theory, given in [START_REF] Féray | Mod-φ convergence: Normality zones and precise deviations[END_REF], which yields estimates on the speed of convergence and moderate deviations results for X n . Section 3.3 gives the main contribution of the author in this chapter. It presents a weighted extension of the theory of dependency graphs, extending widely its range of applications; original references are [START_REF] Féray | Weighted dependency graphs[END_REF][START_REF] Dousse | Weighted dependency graphs and the ising model. Annales de lInstitut Henri Poincaré D[END_REF][START_REF] Féray | Central limit theorems for patterns in multiset permutations and set partitions[END_REF].

The theory of dependency graphs

Defini on and a normality criterion

We consider a family of random variables {Y α , α ∈ A} defined on the same probability space. A dependency graph for this family is an encoding of the dependency relations between the variables Y α in a graph structure. We take here the definition given by Janson [START_REF] Janson | Normal convergence by higher semiinvariants with applications to sums of dependent random variables and random graphs[END_REF]; we refer also to papers of Malyshev [Mal80] and Petrovskaya/Leontovich [START_REF] Petrovskaya | The central limit theorem for a sequence of random variables with a slowly growing number of dependences[END_REF] for earlier appearances of the notion with slightly different names.

Definition 3.1

A graph L is a dependency graph for the family {Y α , α ∈ A} if the two following conditions are satisfied: 1) the vertex set of L is A.

2) for any subsets of vertices A 1 and A 2 , if there is no edge connecting A 1 to A 2 in L, then {Y α , α ∈ A 1 } and {Y α , α ∈ A 2 } are independent.

Informally, one might think that vertices α and β are connected by an edge if the corresponding Y α and Y β are correlated.

Example 3.2

Consider the Erdős-Rényi random graph model G(n, p n ). By definition, a random

graph G in this model has vertex set [n] := {1, . . . , n} and it has an edge between i and j with probability p n , all these events being independent from each other. Let A be the set of 3-element subsets of [n] and for α = {i , j , k} ∈ A, let Y α be the indicator function of the event "the graph G contains the triangle with vertices i , j and k".

Let L be the graph with vertex set A such that there is an edge between α and β if and only if |α ∩ β| = 2 (that is, if the corresponding triangles share an edge in G). Then L is a dependency graph for the family {Y α , α ∈ A}.

Note also that the complete graph on A is a dependency graph for any family of variables indexed by A. In particular, given a family of variables, it may admit several dependency graphs. The fewer edges a dependency graph has, the more information it encodes and, thus, the more interesting it is. It would be tempting to consider the dependency graph with fewest edges, but such a graph is not always uniquely defined [FMN16, Example 9.1.4].

Dependency graphs are a toolbox to prove central limit theorems for sums of partially dependent variables. The following theorem is due to Janson [Jan88, Theorem 2] (see also an earlier paper of Petrovskaya and Leontovich [START_REF] Petrovskaya | The central limit theorem for a sequence of random variables with a slowly growing number of dependences[END_REF] for the case s = 3).

Theorem 3.3: Janson's normality criterion

For each n, we let {Y n,i , 1 ≤ i ≤ N n } be a family of N n random variables such that a.s., one has sup i ≤N n |Y n,i | < M n for some M n > 0. Let L n be a dependency graph for this family and D n -1 be the maximal degree of L n . Finally, we set X n = N n i =1 Y n,i and σ 2 n = Var(X n ). Assume that there exists an integer s such that

N n D n 1/s D n σ n M n → 0 as n → ∞. (3.1)
Then X n is asymptotically normal.

We will discuss the proof of this normality criterion in the next section. Informally, the condition (3.1) says that D n is small, i.e. that the dependency graph L n is rather sparse (so that we are close to the situation of a sum of independent random variables). This condition is usually easy to check on examples (except sometimes for determining the order of magnitude of the variance). We illustrate this criterion by continuing the example of triangles in Erdős-Rényi random graph model G(n, p n ).

Example 3.4

We use the same model and notation as in Example 3.2. Assume to simplify that p n is bounded away from 1. One has N n n 3 , D n n and M n = 1. An easy computation -see, e.g., [JŁR00, Lemma 3.5] -gives σ 2 n max(n 3 p 3 n , n 4 p 5 n ). Thus the hypothesis (3.1) in Janson's theorem is fulfilled if p n n -1/3+ε for some ε > 0. When this holds, Theorem 3.3 implies that, after rescaling, the number X n of triangles in G(n, p n ) is asymptotically normal.

The latter is in fact true under the less restrictive hypothesis p n n -1 , as proved by

Ruci ński [START_REF] Ruci | When are small subgraphs of a random graph normally distributed?[END_REF]. The asymptotic normality in the full range can be proved through dependency graphs, using a refined normality criterion due to Mikhailov [START_REF] Mikhailov | On a Theorem of Janson[END_REF]; see also [JŁR00, Chapter 6] for a complete account of asymptotic normality of the number of triangles and of more general subgraph counts in Erdős-Rényi random graphs. This is only one example among many others. Dependency graphs have been used to prove asymptotic normality in various other domains. Let us give a non-exhaustive list of bibliographic pointers.

• Before Janson's paper, Petrovskaya and Leontovich had studied mathematical models of cell populations using a notion similar to that of dependency graphs [START_REF] Petrovskaya | The central limit theorem for a sequence of random variables with a slowly growing number of dependences[END_REF].

• After Janson's work on random graphs (completed by papers of Baldi-Rinott [BR89],

Rinott [START_REF] Rinott | On normal approximation rates for certain sums of dependent random variables[END_REF] and Mikhailov [START_REF] Mikhailov | On a Theorem of Janson[END_REF]), the theory has found a field of application in geometric probability, where asymptotic normality has been proven for various statistics on random point configurations: the length of the nearest-neighbour graph, of the Delaunay triangulation and of the Voronoi diagram of these random points [START_REF] Avram | On central limit theorems in geometrical probability[END_REF][START_REF] Penrose | Normal approximation in geometric probability[END_REF], or the area of their convex hull [START_REF] Bárány | Central limit theorems for Gaussian polytopes[END_REF]; see also [START_REF] Penrose | Random geometric graphs, volume 5 of Oxford Studies in Probability[END_REF] for applications to geometric random graphs.

• More recently, dependency graphs have been used to prove asymptotic normality of pattern counts in random permutations [START_REF] Bóna | On three different notions of monotone subsequences[END_REF][START_REF] Hitczenko | Asymptotic normality of statistics on permutation tableaux[END_REF][START_REF] Hofer | A central limit theorem for vincular permutation patterns[END_REF].

Behind the normality criterion: joint cumulants

We give here the main lines of the proof of Theorem 3.3. The proof uses the notion of joint cumulants (sometimes called also mixed cumulant), which we now recall.

Let X 1 , . . . , X r be real-valued random variables on the same probability space with finite small exponential moments 1 , i.e. we assume that E exp(εX j ) < +∞ for some ε > 0 and all j ≤ r . We define their joint cumulant as

κ(X 1 , . . . , X r ) = [t 1 . . . t r ] log E exp(t 1 X 1 + • • • + t r X r ) . (3.2)
As usual, [t 1 . . . t r ]F stands for the coefficient of t 1 . . . t r in the series expansion of F in nonnegative powers of t 1 , . . . , t r . The finite small exponential moment assumption ensures that

exp(t 1 X 1 +• • •+ t r X r ) is analytic around t 1 = • • • = t r = 0. If all random variables X 1 , • • • , X r are
equal to the same variable X , we denote κ r (X ) = κ(X , . . . , X ) and this is the usual cumulant of a single random variable.

The main properties of joint cumulants for our purpose are the following (see, e.g.

[JŁR00, Chapter 6] for items 1-2 and [Jan88, Theorem 1] for item 3).

Proposition 3.5 1) (X 1 , . . . , X r ) → κ(X 1 , . . . , X r ) is a symmetric multilinear functional.

2) If the set of variables {X 1 , . . . , X r } can be split into two mutually independent sets of variables (e.g. {X 1 , X 2 } is indepedent from {X 3 , . . . , X r }), then the joint cumulant κ(X 1 , . . . , X r ) vanishes;

3) Let Z n be a sequence of real-valued random variables with E[Z n ] = 0 and Var[Z n ] = 1 for all n ≥ 1. Assume that there exists an integer s ≥ 3 such that κ r (Z n ) tends to 0 for all r ≥ s. Then Z n converges in distribution to a standard Gaussian variable.

The proof of Theorem 3.3 now goes as follows. First, we write

κ r (X n ) = κ(X n , . . . , X n ) = 1≤i 1 ,...,i r ≤N n κ Y n,i 1 , . . . , Y n,i r .
The idea is that, because of property 2 above, many summands in the right-hand side do vanish. Namely, κ Y n,i 1 , . . . , Y n,i r = 0 unless the subgraph induced by the dependency graph L on the vertex set {i 1 , . . . , i r } is connected. One can prove that the number of nonzero terms is at most C r N n D r -1 n , and each nonzero term is easily bounded by C r M r n (here and in what follows, C r are universal constants, depending only on r , which may change from line to line). This yields the following lemma.

Lemma 3.6

Under the assumptions of Theorem 3.3, we have

|κ r (X n )| ≤ C r M r n N n D r -1 n .
Deducing Theorem 3.3 from here is immediate. We consider the normalized version

X n := X n -EX n σ n of X n ; its cumulants are given by κ r ( X n ) = σ -r n κ r (X n ) for r ≥ 2.
An easy computation starting from Lemma 3.6 and Eq. (3.1) shows that κ r ( X n ) tends to 0 for r ≥ s. This implies the asymptotic normality of X n by Proposition 3.5, item 3).

Improving the cumulant bound

Background: cumulants, speed of convergence and moderate devia ons

We have seen in the previous section that a sequence of random variables Z n converges to a standard Gaussian variable N (0, 1) if, for any fixed r larger than a threshold s, its cumulant κ r (Z n ) of order r tends to 0.

It turns out that, if s = 3 and if one can control the rate of decay of κ r (Z n ) uniformly on r ≥ 3, one can establish stronger estimates than asymptotic normality: namely one gets an upper bound on the speed of convergence of Z n to N (0, 1) (with respect to Kolmogorov distance2 d Kol ) and deviation probability estimates for Z n (at intermediate scales between asymptotic normality and large deviations; these are sometimes called moderate deviation estimates). This kind of results, together with applications, can be found in the work by the probabilist Statuleviius and his students Rudzkis and Saulis; see the book [START_REF] Saulis | Limit theorems for large deviations[END_REF] or the recent survey [START_REF] Döring | The method of cumulants for the normal approximation[END_REF]. We have in particular the following proposition [SS91a, Corollary 2.1 and Lemma 2.3].

Proposition 3.7

Assume that Z n is a sequence of variables with expectation 0 and variance 1 whose cumulants are bounded as follows: there exists C > 0, γ ≥ 0 and a sequence ∆ n tending to +∞ such that, for all r and n, we have

|κ r (Z n )| ≤ C (r !) 1+γ ∆ r -2 n .
Then Z n tends to a Gaussian random varaible

Z at speed d Kol (Z n , Z ) = O (∆ -1/(1+2γ) n ).
Moreover, for any nonnegative sequence x n min(∆ 1/(2γ+1) n

, ∆ 1/2 n ), one has the upper and lower tail estimates

P[Z n ≥ x n ] P[Z ≥ x n ] = exp 1 6 x 3 n κ 3 (Z n ) 1 + o(1) ; (3.3) P[Z n ≤ -x n ] P[Z ≤ -x n ] = exp -1 6 x 3 n κ 3 (Z n ) 1 + o(1) . (3.4)
Some comments are useful.

The proposition tells us that the estimates

P[Z n ≥ x n ] ∼ P[Z ≥
x n ] is valid not only for bounded sequences x n (as asserted by asymptotic normality), but also in the full range 1), so that the right-hand side of (3.3) is 1 + o(1). In the case γ < 1, when

x n = o(∆ 1/3 n ) if γ ≤ 1 or x n = o(∆ 1/(2γ+1) n ) otherwise. Indeed, for x n = o(∆ 1/3 n ), the bound κ 3 (Z n ) = O(∆ -1 n ) implies x 3 n κ 3 (Z n ) = o(
∆ 1/3 n < x n ∆ n 1/(2γ+1) ,
the proposition gives us the correction factor needed to go from the Gaussian estimate

P[Z ≥ x n ] to an estimate for P[Z n ≥ x n ].
Let us finally mention that [SS91a, Lemma 2.3] gives in fact more precise estimates, valid for wider ranges of x n . We limit ourselves to the version above to avoid too technical statements.

REMARK For γ = 0, which is the case we will use below, Proposition 3.7 can also be seen as a special case of general estimates for random variables converging in the mod-ϕ sense (i.e. with some precise control on the renormalized characteristic function); see [START_REF] Féray | Mod-φ convergence: Normality zones and precise deviations[END_REF][START_REF] Féray | Mod-φ convergence, II: Estimates of the speed of convergence[END_REF]. We will not discuss further mod-ϕ convergence in this thesis.

A be er bound for cumulants in the framework of dependency graphs

The important feature in Proposition 3.7 is that the parameter γ, i.e. the dependence of the cumulant bounds with respect to the order r , is crucial to obtain a sharp bound on the speed of convergence and a large window for deviation estimates. It is therefore natural to wonder how the constant C r in Lemma 3.6 depends on r . Döring and Eichelsbacher [START_REF] Döring | Moderate Deviations via Cumulants[END_REF],

analyzing Janson's proof, show that one can take C r = (r !) 3 (2e) r , so that Proposition 3.7 can be applied with γ = 2 in many settings with dependency graphs (the factor (2e) r plays no role since it can be absorbed in D r -2 n , changing only D n by a multiplicative constant.) In a joint work with P.-L. Méliot and A. Nikhegbali, we were able to improve this bound [FMN16, Theorem 9.7].

Lemma 3.8

Lemma 3.6 holds with C r = 2 r -1 r r -2 .

To obtain this bound, as before, we start with the expansion

κ r (X n ) = κ(X n , . . . , X n ) = 1≤i 1 ,...,i r ≤N n κ Y n,i 1 , . . . , Y n,i r .
(3.5)

The idea was then to have a bound for each summand in the RHS taking into account the dependencies among the variables Y n,i 1 , . . . , Y n,i r (instead of using the same upper bounds for all nonzero terms, as done before). We found the following general bound which could be of independent interest; see [FMN16, Section 9.4].

Lemma 3.9

Let Y 1 , . . . , Y r be bounded random variables (|Y i | ≤ M a.s.) with a dependency graph

H . Then we have |κ(Y 1 , . . . , Y r )| ≤ M r 2 r -1 ST(H ),
where ST(H ) is the number of spanning trees of H .

We do not discuss the proof of Lemma 3.9 here, but we briefly sketch the proof of Lemma 3.8, assuming Lemma 3.9. Going back to (3.5), if {Y n,i , i ≤ N n } has a dependency graph L, then the subfamily {Y n,i 1 , . . . , Y n,i r } has dependency graph L[i 1 , . . . , i r ], which is the graph induced by L on {i 1 , . . . , i r }. Therefore we get

κ r (X n ) ≤ M r 2 r -1 1≤i 1 ,...,i r ≤N n ST L[i 1 , . . . , i r ] .
The right-hand side can be bounded from above via a double counting argument, using the following observation: for a given tree T on vertex set {1, . . . , r }, there are at most N n D r -1 n lists (i 1 , . . . , i r ) such that T is a spanning tree of L[i 1 , . . . , i r ]. This proves Lemma 3.8.

Applica on to subgraph counts in G(n, p)

Our improved bound for cumulants (Lemma 3.8), combined with Proposition 3.7, yields the following estimates in the dependency graph framework:

• a control of the speed of convergence;

• precise moderate deviation estimates.

Speed of convergence estimates in this context had already been obtained around 1990 using Stein's method ; see in particular the work of Baldi and Rinott [START_REF] Baldi | On normal approximations of distributions in terms of dependency graphs[END_REF][START_REF] Rinott | On normal approximation rates for certain sums of dependent random variables[END_REF]. Their method is more powerful than the cumulant approach, in particular in that it allows to deal with variables Y α having only a few finite moments.

Precise moderate deviation estimates are however out of reach with Stein's method3 and such estimates are, as far as I am aware of, new in the context of dependency graphs.

P T n ≥ n 3 p 3 + n 2 v 6 = 9p 5 (1 -p) π v 2 exp - v 2 36 p 5 (1 -p) + (7 -8p) 324 p 8 (1 -p) 2 v 3 n (1 + o(1)).
Let us decipher this formula. Keeping only the first term in the exponential, we get the tail of the Gaussian limit law for T n . For v n 1/3 , the second term in the exponential is o(1) so that the Gaussian tail gives a correct asymptotic equivalent for the tail probability of the triangle count. For n 1/3 ≲ v n 1/2 , we need a correction factor of the form exp(C v 3 /n), which is explicitly given by our formula.

Similar bounds can be obtained for number of copies of other graphs than triangles, see [FMN16, Theorem 10.1]. We also refer to [START_REF] Goldschmidt | Moderate deviations of subgraph counts in the erdős-rényi random graphs g (n, m) and g (n, p)[END_REF] for a later approach via martingales of moderate deviation estimates for subgraph counts in G(n, p) (and in the related model G(n, M ) with a fixed number of edges).

Concentra on inequali es

Upper bounds on cumulants can also be used to get concentration inequalities, i.e. upper bounds for the probability that a random variable is far away from its expectation.

In [FMN20, Propositions 6 and 7], we prove the two following bounds, which are both elementary consequences of Chernoff inequality.

Lemma 3.10

Let (X n ) n≥1 be a sequence of random variables such that |X n | ≤ N n M n a.s. and

κ r (X n ) ≤ N n (2D n ) r -1 r r -2 M r
n for any r ≥ 1 (for some parameters M n , N n , D n ). Then, for any positive sequence x n > 0, we have

P |X n -E[X n ]| ≥ x n ≤ 2 exp - x 2 n 9 D n N n M 2 n , (3.6) P |X n -E[X n ]| ≥ x n ≤ 2 exp   - x 2 n 2 Var(X n ) + 2e D n N n M 2 n x n N n M n    .
(3.7)

From Lemma 3.8, we know that the hypothesis above is satisfied when we have dependency graphs as in Janson's normality criterion (Theorem 3.3).

Concentration inequalities for sums of variables with an underlying dependency graph had previously been given by Janson in [START_REF] Janson | Large deviations for sums of partly dependent random variables[END_REF]. His basic idea is to split the sum

X n = N n i =1 Y n,i into subsums X I = i ∈I Y n,i
, where I is an independent set of the dependency graph L n . The number of X I needed to decompose X n is precisely the chromatic number of L n . Each X I is a sum of independent random variables, to which we can apply Hoeffding's inequality. We finally get a concentration inequality for X n involving the chromatic number.

The argument can be further refined to involve the fractional chromatic number instead: this gives in general a better bound than (3.6), which involves the maximal degree of L n .

There is nevertheless (at least) one setting in which the approach through cumulants is usable while the decomposition using independent sets is not. This involves the measures on partitions induced by the extremal characters of S ∞ which we already mentioned in Section 2.2.4. In this setting, permutations σ in some symmetric group S k can be seen as random variables in a noncommutative probability space and have a natural dependency graph structure (for some good extension of the notion of dependency graph to noncummutative probability spaces). However, the partial sums X I of permutations over independent sets I of the dependency graph do not make sense as usual random variables; thus, one cannot use Hoeffding's inequality as in Janson's approach. Our approach through cumulants however goes through and we get concentration inequalities for some polynomial functions of Young diagrams under these measures; see [FMN20, Theorem 12].

Weighted dependency graphs

As we have seen, dependency graphs form a powerful and handy toolbox for proving asymptotic normality results in models with underlying independent random variables. A drawback is the non-robustness of the method: if variables are weakly correlated instead of being completely independent, the method fails.

There are many natural models in the literature, where such weak dependencies appear: among others,

• random graphs with a fixed number M of edges (known as the Erdős-Rényi G(n, M )

ε ε 2 ε 3 ε 1 ε 1 ε 2 FIGURE 3.1
Example of a weighted graph with a spanning tree of maximal weight. Bold red edges are the edges of a specific maximum weight spanning tree, the other edges of the graph are dashed for more readability.

model);

• states of an ergodic Markov chain;

• substructures in uniform random matchings, multiset-permutations or setpartitions;

• statistical physics models such as the symmetric simple exclusion process (SSEP) or the Ising model.

In order to prove asymptotic normality in such models, we have introduced an extension of the notion of dependency graphs, called weighted dependency graphs; see [START_REF] Féray | Weighted dependency graphs[END_REF] and the later papers [START_REF] Dousse | Weighted dependency graphs and the ising model. Annales de lInstitut Henri Poincaré D[END_REF][START_REF] Féray | Central limit theorems for patterns in multiset permutations and set partitions[END_REF].

Defini on and normality criterion

To state the definition of a weighted dependency graph, we need to introduce some notation. In the following we use the term weighted graphs for graphs with weights in (0, 1] on their edges; for convenience, we sometimes see non-edges as edges of weight 0. The weighted degree of a vertex is the sum of the weights of its incident edges. A spanning tree in a graph is a subset of the edge-set connecting all vertices and without cycle. A spanning tree in a weighted graph has a weight, simply defined as the product of the weights of its edges. This allows to define, for a weighted graph K , a quantity M (K ) as the maximal weight of a spanning tree of K . For example, if K is the weighted graph of Figure 3.1 for some ε ∈ (0, 1), then M (K ) = ε 4 and a spanning tree of maximal weight is given by the red edges.

By convention, if K is disconnected, M (K ) = 0.
We now define the notion of weighted dependency graphs of a family of variables {Y α , α ∈ A} through bounds on their joint cumulants (see Section 3.1.2 for background on joint cumulants).

Definition 3.11: Weighted dependency graphs

Fix C = (C r ) r ≥1 . A weighted graph L with vertex set A is a C -weighted dependency graph for the family {Y α , α ∈ A} if, for any α 1 , . . . , α r in A, one has

κ(Y α 1 , • • • , Y α r ) ≤ C r M L[α 1 , • • • , α r ] ,
where

L[α 1 , • • • , α r ]
is the weighted subgraph of L induced on the vertices α 1 , . . . , α r .

In the above definition, we need to consider also lists α 1 , . . . , α r with repetition. In this case, we take as many copies of each vertex as its multiplicity in the list α 1 , . . . , α r and we connect copies of the same vertex by edges of weight 1. Some (informal) comments are needed.

• The definition depends on a sequence of numbers C = (C r ) r ≥1 . They should be thought of as constants in the following sense. In applications to prove asymptotic normality, we will consider sequences of weighted dependency graphs depending on n, and require that, for any given r ≥ 1, the quantity C r does not depend on n.

• The lower the weights in L are, the lower the joint cumulants of the variables should be. Recalling that joint cumulants of independent random variables vanish, we see that the weights in L quantify in some sense the dependency between random variables.

• Why is the functional M a good choice here, and not another quantity depending in a monotone fashion on the edge weights? I have no satisfactory explanation for that.

In particular, making a parallel with Lemma 3.9 is tempting, but I do not have a deep understanding of why spanning trees appear in both places.

• For usual dependency graphs, the fact that a well-chosen graph is a dependency graph in some model is usually immediate to check (see, e.g., Example 3.2). This is no longer true for weighted dependency graphs since one has to prove a number of inequalities for joint cumulants, namely one for each list (α 1 , . . . , α r ) of elements of A (or in fact for each multiset of elements of A since joint cumulants are symmetric functionals). The paper [START_REF] Féray | Weighted dependency graphs[END_REF] gives some general properties helping in proving that a given weighted graph is a weighted dependency graph; one of them is the stability property described in Section 3.3.2 below.

• Finally, let us mention that this is in fact a simplified version of the definition, which covers only some cases of applications. The most general version also involves a function Ψ, giving some weights to multisets of vertices ; we will not discuss it here and refer the reader to [START_REF] Féray | Weighted dependency graphs[END_REF] for details.

With this definition in hand, one has a natural extension of Janson's normality criterion (see [Fér18, Theorem 4.11 and Remark 4.12] fir the original reference). We do not discuss the proof of this criterion here.

Theorem 3.12: An extension of Janson's normality criterion

For each n, let {Y n,i , 1 ≤ i ≤ N n } be a family of N n random variables; such that there exists M > 0 with |Y n,i | < M a.s. for all n, i ≥ 0. For each n, we let L n be a C -weighted dependency graph for this family for some C = (C r ) r ≥1 independent of n. We call D n -1 the maximal weighted degree of L n . Finally, we set X n =

N n i =1 Y n,i and σ 2 n = Var(X n ). Assume that there exists an integer s such that

N n D n 1/s D n σ n → 0 as n → ∞. (3.8)
Then, X n is asymptotically normal.

event "G contains the edge e".

Lemma 3.14: Weighted dependency graph for edges in G(n, M )

Let Kn be the complete graph on A n with weight 1/M n on each edge. Then Kn is a C -weighted dependency graph for the family {Y e , e ∈ A n }, where C = (C r ) r ≥1 is a sequence that does not depend on n.

We skip the proof of this lemma which is rather technical. It is based on the facts that the joint moments of the random variables (Y e ) e∈A n are explicit and that joint cumulants can be expressed as linear combinations of joint moments.

We now consider indicator functions of triangle containments. Set B n = [n] 3 . For any {i , j , k} in B n , we define a random variable Z i , j ,k such that Z i , j ,k = 1 if the triangle {i , j , k} belongs to the random graph G, and 0 otherwise. Note that Z i , j ,k = Y {i , j } Y {i ,k} Y { j ,k} . Therefore Lemma 3.14 and Proposition 3.13 yield the following proposition. • otherwise, the edge {I , J } gets weight 1/M n .

Then L n is a C -weighted dependency graph for the family {Z i , j ,k , {i , j , k} ∈ B n }, where C = (C r ) r ≥1 is a sequence that does not depend on n.

With this proposition in hand, let us check if the asymptotic normality criterion is satisfied. It is easily seen that the graph L n is regular with weighted degree 3(n -3) + n-3 3 /M n . The latter is of order Θ(n) when M n n 2 . Moreover, the variance of the number of triangles in G(n, M n ) is known to be of order n 3 ; see [START_REF] Janson | A functional limit theorem for random graphs with applications to subgraph count statistics[END_REF]. Therefore for s = 5, one has

N n D n 1/s D n σ n n 2/5 n -1/2 → 0.
We conclude that the number of triangles in G(n, M n ) is asymptotically normal. This result had been previously obtained by Janson [START_REF] Janson | Orthogonal decompositions and functional limit theorems for random graph statistics[END_REF] through martingales techniques (again for a larger range of M n and all subgraph count statistics).

Another example: pa erns in set-par ons

Let us present a second example of application of the normality criterion through weighted dependency graphs, for which I am not aware of an alternative approach to prove the same result.

We are interested here in uniform random set-partitions π of [n]. We see set-partitions as sets of arcs, where there is an arc between any two consecutive elements in the same part. This geometric representation induces a natural notion of substructure, or pattern, in setpartitions. The following definition (illustrated on Figure 3.2) was suggested under a more

An arc pattern of length ℓ is a subset A ⊆ {(i , j ) ∈ [ℓ] × [ℓ] : i < j } such that for distinct
elements (i 1 , j 1 ) and (i 2 , j 2 ) in A , we have i 1 = i 2 and j 1 = j 2 . We say that the pattern A occurs in a set partition π in positions x 1 < x 2 < . . . < x ℓ if for every (i , j ) ∈ A there is an arc from x i to x j in π.

Arc patterns of length ℓ are exactly the arc representations of set-partitions of ℓ, but in the sequel, it is more natural to think of them as sets of arcs. We are interested in the random variable Occ A n := Occ A (π), which gives the number of occurrences of a fixed arc pattern A in a uniform random set partition π of [n]. We have the following result, proved in [START_REF] Féray | Central limit theorems for patterns in multiset permutations and set partitions[END_REF].

Theorem 3.17: Asymptotic normality of pattern occurences in set-partitions

The number of occurrences Occ A n of any fixed arc pattern A in a uniform random set partition of [n] is asymptotically normal as n → ∞. This is a wide generalization of a theorem of Chern, Diaconis, Kane and Rhoades [START_REF] Chern | Central limit theorems for some set partition statistics[END_REF], stating that the number of crossings is asymptotically normal. Their method is based on the fact that, conditioned on minimal and maximal values of blocks, the number of crossings is a sum of independent random variables. It does not seem to be generalizable to other patterns.

As advertized, our proof is based on weighted dependency graphs. To this end, we call 1[ i j ] the indicator variable of the arc {i , j } (1 ≤ i < j ≤ n). The variables 1[ i j ] are correlated even if they do not share an extremity. Intuitively, this happens for two reasons: 1) knowing that i and j are in the same part tends to reduce the total number of parts of π and thus increases the probability that some other integers, say k and ℓ, are in the same part.

2) the event 1[ i j ] = 1 means that i and j are in the same part, but also that all intermediate points are in other parts; hence it carries information on these intermediate points.

These correlations are however weak when the size of the set-partition becomes large. This is quantified with weighted dependency graph in the following statement. We warn the reader that we use here a more general version of weighted dependency graphs involving a weight function Ψ on multiset of vertices. We apologize for using it without having defined it in this manuscript. Unlike in other examples, the sequence C depends on n, but we control this dependency: the normality criterion is easily adapted to this setting.

Proposition 3.18: Weighted dependency graph for arcs in set-partitions

The complete graph with weights The proof of Proposition 3.18 is involved and we do not even sketch it here. The stability property of weighted dependency graphs presented in Section 3.3.2 then yields without extra effort a dependency graph for indicator functions of the occurrences of the pattern A in given sets of positions. We can then prove Theorem 3.17 as an application of the extended normality criterion (Theorem 3.12; or more precisely its version for (C , Ψ)-weighted dependency graphs), after a delicate analysis of the variance. Details can be found in [START_REF] Féray | Central limit theorems for patterns in multiset permutations and set partitions[END_REF].

w 1[ i j ], 1[ i j ] =    1 if i = i or j = j ; 1/n otherwise.

Improving the cumulant bound?

Looking at Proposition 3.7, it is natural to wonder if one can get sharp bounds on cumulants in the context of weighted dependency graphs. This is indeed possible, but we need a more restricted version of weighted depedency graphs, which was defined in [START_REF] Féray | Mod-φ convergence, II: Estimates of the speed of convergence[END_REF].

Definition 3.19: Uniform weighted dependency graph

Fix C > 0. A weighted graph L is a C -uniform weighted dependency graph for the family {Y α , α ∈ A} if, for any list (α 1 , . . . , α r ) of elements of A, one has

κ Y α 1 , . . . , Y α r ≤ C r T ∈ST( L[α 1 ,...,α r ]) w(T ).
With this notion, one has the following bound for cumulants.

Lemma 3.20

Let {Y α , α ∈ A} be a finite family of random variables with a C -uniform weighted dependency graph L. We denote by N the number of vertices of L, and by D -1 its maximal weighted degree. Then, for r ≥ 1,

κ r α∈A Y α ≤ N r r -2 D r -1 C r .

Pa erns and permuta on classes

We now define patterns of permutations. This has become in the last 30 years a standard notion in enumerative combinatorics, see [START_REF] Vatter | Permutation Classes[END_REF] for a survey.

For any positive integer n, the set of permutations of [n] := {1, 2, . . . , n} is denoted by S n . We write permutations of S n in one-line notation as σ = σ(1)σ(2) . . . σ(n). For a permutation σ in S n , the size n of σ is denoted by |σ|.

Take σ ∈ S n , and I ⊂ [n] of cardinality k; we consider the subsequence (σ(i )) i ∈I and look for the permutation π of size k whose entries are in the same relative order as the entries of (σ(i )) i ∈I . Then π is the pattern of σ in position I and denoted pat I (σ). For example for σ = 65831247 and I = {2, 5, 7} we have pat {2,5,7} (65831247) = 312 since the values in the subsequence σ(2)σ( 5)σ(7) = 514 are in the same relative order as in the permutation 312 (the largest first, the smallest one in the middle, and the intermediate value at the end).

If π = pat I (σ) for some I ⊂ [n], then we say that π is contained in σ, and that the subsequence (σ(i )) i ∈I is an occurrence of π in σ. When a pattern π has no occurrence in σ, we say that σ avoids π. The pattern containment relation defines a partial order on S = ∪ n S n : we write π ≼ σ if π is a pattern of σ.

A permutation class, C , is a subset of S which is downward closed under ≼. Namely, for every σ ∈ C , and every π ≼ σ, it holds that π ∈ C . It is known that permutation classes may equivalently be defined as subsets of S characterized by the avoidance of a (finite or infinite) family B of patterns. If we require in addition that B is an antichain (i.e. consists of elements incomparable for ≼), then B is uniquely determined by C . This set B is called the basis of C , and we write C = Av(B ).

The general question we are interested in is the description of the asymptotic properties of a uniform random permutation of large size in a given class C . Though permutation classes are most often studied with an enumerative perspective, the probabilistic literature on the subject has developed quickly in the past few years with a variety of approaches, see for example [MP14, HRS17, Jan19, MP16, Bor20b].

Subs tu on opera on and an enumera ve result

The enumeration of permutations avoiding given patterns is a difficult problem in general 1 , for which many different approaches have been developed. This makes the subject fascinating, but also suggests that it is rather hopeless to obtain general precise results on uniform random permutations in any class C . Therefore the best we can do is to consider a large family of classes C with a common structure. In this spirit, we focus here on permutation classes containing only finitely many simple permutations.

We recall the necessary definitions, originally introduced in [START_REF] Albert | Simple permutations and pattern restricted permutations[END_REF]. Throughout this chapter, we identify permutations with their diagrams: the diagram of σ is a square grid with dots at coordinates (i , σ(i )) (for i in {1, . . . , |σ|}). For θ a permutation of size d , the substitution θ[π (1) , . . . , π (d ) ] is obtained by inflating each point (i , θ(i )) of θ by a square containing the diagram of π (i ) , see Fig. A simple permutation is a permutation of size at least 2 that can not be obtained as substitutions of smaller permutations. Equivalently a permutation is simple if it does not contain a nontrivial set of consecutive values in consecutive positions. In algebraic terms, the simple permutations are the generators of the set of all permutations with respect to the substitution operation (which gives to the set of permutations an operad structure).

In [START_REF] Albert | Simple permutations and pattern restricted permutations[END_REF], the following theorem was proved:

Theorem 4.1

Every class C containing only finitely many simple permutations has a finite basis and an algebraic generating function.

We call such classes finitely generated classes and study here uniform random permutations in such classes.

Permutons

Now that the models we are interested in are well-defined, we need to be more precise on the kind of asymptotic results we are looking for. As suggested earlier, we will be interested in scaling limits in the sense of permutons. The latter notion first appeared under a different name in a paper of Presutti and Stromquist [START_REF] Presutti | Packing rates of measures and a conjecture for the packing density of 2413[END_REF] in the context of packing problems. Later in [HKM + 13], it was rediscovered as a limit object for permutation sequences;

see also [BBF + 20, Section 2] for an introduction to permutons close to the point of view used here.

Formally, a permuton is a probability measure µ on the unit square [0, 1] 2 with uniform marginals. The latter means that if we project µ on the vertical (resp. horizontal) axis, we get the uniform measure on [0, 1]. Permutons generalize permutations in the following sense: with a permutation σ ∈ S n , we associate the permuton µ σ with density FIGURE 4.2 Seeing a permutation as a measure on the unit square, called permuton. Each gray square on the right-hand side has total mass 1/n = 1/5 (i.e. density n = 5 w.r.t to the 2-dimensional Lebesgue measure), so that the total mass is 1.

µ σ (d xd y) = n1 σ( xn )= yn d xd y,
where t is the nearest integer above t . Note that it amounts to replacing every point (i , σ(i )) in the diagram of σ (rescaled to fit in the unit square) by a square of the form

[(i -1)/n, i /n] × [(σ(i ) -1)/n, σ(i )/n],
with a mass 1/n uniformly distributed on it. An example is given on Fig. 4.2.

The space M of permutons is equipped with the topology of weak convergence of measures, which turns it into a compact metric space. This allows to define convergent sequences of permutations: we say that (σ n ) n converges to a permuton µ when (µ σ n ) → µ weakly. This is a natural notion of scaling limits for permutations. Interestingly, permuton convergence is also equivalent to the convergence of pattern occurrences, see [HKM + 13] and [BBF + 20, Theorem 2.5]. In this sense, permuton convergence is a natural analogue of the notion of dense graph convergence (also known as graphon convergence), which has been an active research topic in graph combinatorics in the last 15 years, see e.g., Lovasz' book [START_REF] Lovász | Large networks and graph limits[END_REF].

In this thesis, we will use the framework of permutons to describe limits of (random) permutation sequences. By abuse of language, we will say that a permutation class C converges to a (possibly random) permuton µ if a uniform random permutation σ n of size n in C converges in distribution to µ. We mention that permutons have also been studied with other purposes: packing problems [START_REF] Presutti | Packing rates of measures and a conjecture for the packing density of 2413[END_REF], large deviation theory [START_REF] Kenyon | Permutations with fixed pattern densities[END_REF], quasirandomness [KP13, CKN + 20], . . .

Main result: a dichomotomy for scaling limits of finitely generated classes

We now state informally the main result of the paper [BBF + 19b] (and of this section of the thesis); note that the technical condition and the limiting objects in the theorem will be discussed in Sections 4.4.1 to 4.4.3 below. We denote by ∆ 3 the simplex • either σ n converges to the so-called Brownian separable permuton of parameter p ∈ (0, 1);

{(x 1 , x 2 , x 3 , x 4 ) ∈ [0; 1] 4 ; x 1 + x 2 + x 3 + x 4 = 1}.
• or σ n converges to the X -permuton of parameter (p left

+ , p right + , p left -, p right - ) ∈ ∆ 3 .
In both cases, the parameter(s) are computable, given the finite basis of C .

The hypothesis "C contains finitely many simple permutations" (and the technical condition) are restrictive but the theorem still applies to a large family of classes. In comparison, most results in the literature concern a single class [HRS17,BS20,Bor20a], or in the best cases a simply-indexed family of classes [BDS19, HRS20]; our result is much more general. An exception is Bevan's limit shape result on monotone grid classes [Bev15, Chapter 6], which also applies to a large family of classes.

It is remarkable that the limiting permutons in Theorem 4.2 fall into two simple families;

this can be seen as an instance of a universality phenomenon, as discussed in the introduction. We now describe the limiting objects together with examples. We have plotted large uniform random permutations taken from those classes2 on Fig. 4.4.

The X -permuton

The convergence to X -permutons (with respectively 0,1 and 2 coordinates equal to 0 in the parameter p) is clearly visible on the pictures.

The Brownian separable permuton

The Brownian separable permuton is more delicate to define than the X -permuton (but also more interesting!). We start with a Brownian excursion3 e : [0, 1] → R + , and we assign to local minima4 of e independent random signs (S i ) i ≥1 with P(S i = ⊕) = p = 1 -P(S i = ).

From this "signed Brownian excursion" (e, (S i ) i ≥1 ), we first construct an "infinite permutation" σ ∞ , which is a Lebesgue preserving function from = 3214576 FIGURE 4.6 A signed tree and the associated separable permutation. We have circled some leaves and the corresponding elements in the permutation to illustrate the definition. We see that leaves 2 and 3 have the same parent carrying a sign and that the corresponding elements form an inversion. On the other hand the closest common ancestor of leaves 2 and 7 (resp. 3 and 7) is the root of the tree which carries a ⊕ sign and the corresponding elements in the permutation are in increasing order.

In other words, there is an inversion between x and y if and only if the local minimum of e on the interval [x, y] carries a sign. See This definition might seem mysterious but this is in fact a natural extension of the encoding of the so-called separable permutations by their seraparation trees. A separation tree is a plane tree with ⊕ or signs on its internal vertices. We associate a permutation to it as follows. First, we label the leaves from left to right. Then we require that there is an inversion at positions (i , j ) in the permutation if and only if the closest common ancestors of the i -th and the j -th leaves in the tree carries a sign; see Fig 4 .6. Separable permutations are the permutations that can be obtained through this process.

Brownian excursions are known to represent limits of natural models of random trees; see the seminal work of Aldous in the early nineties [START_REF] Aldous | The Continuum Random Tree III[END_REF]. In this context, leaves of the infinite tree correspond to (a measure 1 subset of) the interval [0, 1] and the closest common ancestor between two leaves is matched with the minimum of the excursion on the corresponding interval. Eq. (4.1) is therefore the natural extension of the discrete construction above to the infinite setting.

It is a simple exercise to show that there is (up to equality on a set of measure 1) a unique In this setting, a combinatorial specification is a finite system of equations of the kind:

C i = P i (Z , C 0 , . . . , C d ), 0 ≤ i ≤ d , (4.2)
where the C i are sets of permutations included in C , with C 0 = C , where Z is a set with only one permutation of size 1 and where the P i are polynomials. The operations + and × in the polynomials P i act on sets of permutations in the sense of (unlabelled) combinatorial classes (see, e.g., [START_REF] Flajolet | Analytic Combinatorics[END_REF]): + represents a disjoint union and × a direct product. A list of permutations in a direct product is then seen as a single permutation in a way which depends on the equation; it can be a direct sum ⊕ or a skew sum , or a substitution (π 1 , . . . , π d ) → α[π 1 , . . . , π d ] for some α. We assume that the system of equations uniquely determines the class C i (assuming that there is no element of size 0).

It is well-known that such a specification yields a polynomial system of equation for the generating series of the C i , implying that they are algebraic (and even N-algebraic). Such a system can be used to analyze the behavior of the generating series at their singularity (and hence to find the asymptotic enumeration of the class). Such an hypothesis would be too restrictive for the application to permutation classes.

We make a weaker hypothesis and assume only that the dependency graph restricted to those C i with a minimal radius of convergence (which we call critical families) is strongly connected. This is the technical hypothesis in Theorem 4.2.

Facing such a hypothesis, several questions occur:

1) Is such a condition really necessary or just needed in the proof? In other words, are there some finitely generated classes whose limit is neither an X -permuton, nor a Brownian separable one? 2) Is the condition often verified?

3) Given a specific class, how can we check whether the condition is verified or not?

Let me discuss briefly these questions:

1) There are indeed finitely generated classes with other limits than X or Brownian separable permutons. An example is given on Figure 4.8. In this example, one can prove that the limiting permuton is a juxtaposition of two X -permutons of random relative sizes [BBF + 19b, Proposition 7.8]. In [BBF + 19b], we exhibited another example, where the limit is the diagonal permuton with probability 1/2 and the antidiagonal permuton with probability 1/2 [BBF + 19b, Proposition 7.5]. Though both the diagonal permuton and the antidiagonal ones are special cases of X -permutons (and of Brownian separable permutons), this mixture is not.

We note that Theorem 4.2 is nevertheless useful to describe the limit of these classes.

Indeed, we can apply it to appropriate subfamilies to find the limit of uniform permutations in those subfamilies, and then use some equations of the specification (4.2) to infer the limit of the class we started from. We refer to [BBF + 19b, Section 7] for details.

2) Thanks to the software Specifier developed by M. Maazoun, which computes automatically combinatorial specifications of finitely generated classes, we have tried to apply Theorem 4.2 to a number of examples. In many cases, the strongly connectedness assumption was directly verified ; in other cases, it was applicable to a family with obviously the same limit (e.g. the class C from which we remove a single permutation of each size). This seems to indicate that Theorem 4.2 has indeed a large range of applications. But unfortunately, we have no mathematical statement on the proportion of finitely generated classes, to which this theorem applies.

3) Let us now discuss how to check the technical condition. There is no automatic way to determine which families C i in the specification (4.2) are critical. Nevertheless, strongly connected components of the dependency graph can be computed easily and, in a given strongly connected component, either all classes are critical, or none of them are. We then need ad-hoc arguments to distinguish between these two cases.

Once critical families have been identified, seeing whether the dependency graph restricted to those families is strongly connected or not is straight-forward. In case it is, we also provide a simple condition to determine whether the limit is an X -permuton or a Brownian separable one. The X -permuton occurs when the system restricted to critical families is linear. At the contrary, when there are quadratic or higher degree terms in this restricted system, then the limit is a Brownian separable permuton

The proof approach via analy c combinatorics

We describe in a nutshell the strategy used in [BBF + 19b] to prove Theorem 4.2.

We want to prove the convergence of uniform random permutations in some class C in the topology of permutons. As mentioned in Section 4.3, a general result [BBF + 20, Theorem We analyze the resulting specifications with tools of analytic combinatorics. Indeed as said above, combinatorial specifications yield systems of equations for the associated generating series. When the equations are analytic on a sufficiently large domain and when the dependency graph of the system is strongly connected, two different kinds of behavior might happen:

• either the system is linear, and the series have all polar singularities at their radius of convergence [START_REF] Banderier | Formulae and asymptotics for coefficients of algebraic functions[END_REF];

• or the system is called branching, and the series have all square-root singularities (this is known as Drmota-Lalley-Woods theorem in the literature [START_REF] Flajolet | Analytic Combinatorics[END_REF][START_REF] Drmota | Random trees: an interplay between combinatorics and probability[END_REF]).

We apply these theorems to the critical series in our (refined) specifications, considering the non-critical series as parameters. Once we know the singular behavior of the series, the transfer theorem of analytic combinatorics [START_REF] Flajolet | Analytic Combinatorics[END_REF] gives us the asymptotic number of elements in C and C π for all π. We deduce from this the probability that k marked elements in a uniform permutation in C induce a given pattern π. Comparing these probabilities to those in the candidate limiting permutons proves the desired convergence.

Connec on with random trees

There is another way to think at (and in some cases to prove) our convergence results for random permutations in finitely generated classes. The substitution operation on permutations described in Section 4.2 allows to encode bijectively permutations through some plane rooted trees called substitution trees 8 . These trees have leaves corresponding to the elements of the permutations, and internal nodes decorated by simple permutations. They FIGURE 4.9 A permutation and its associated substitution tree.

FIGURE 4.10 Substitution trees of random permutations in finitely generated classes. Left: in the case of convergence to an X -permuton. Right: in the case of convergence to a Brownian separable permuton. We observe that the tree on the left hand side is more "elongated".

encode the construction of the permutation by successive substitutions into simple permutations. An example is given in Fig. 4.9 (the precise definition is not needed for this discussion).

Through this encoding our random permutations in classes yield random trees. The dichotomy of Theorem 4.2 seems also to hold at the level of random trees. Let σ n be a uniform random permutation in a finitely generated class C . We believe that we have the following convergences of the undecorated substitution trees (seen as measured metric spaces):

• If σ n converges to a Brownian separable permuton, then the associated substitution tree converges after normlization to Aldous' Brownian CRT (CRT stands for Continuum Random Tree); see [START_REF] Aldous | The Continuum Random Tree III[END_REF] for a definition of this now classical object.

• On the other hand, if σ n converges to an X -permuton, then the associated substitution tree converges after normalization to the line segment [0, 1].

We refer to Fig. 4.10 for simulations supporting this belief.

Thanks to the specification (4.2), one can construct the substitution tree of a uniform random permutation in C as a multitype Galton-Watson tree conditioned to have n leaves (the colors in Fig. 4.10 correspond to the different types in this Galton-Watson representa-tion of the substitution trees; the sizes differentiate critical and subcritical types). Convergence results to Aldous' Brownian CRT for multitype Galton-Watson trees are available in the literature [START_REF] Miermont | Invariance principles for spatial multitype galtonwatson trees[END_REF][START_REF] Haas | Scaling limits of multi-type Markov branching trees[END_REF], but only in the irreducible case (corresponding to the dependency graph of the specification being strongly connected). To prove the first item above, we would therefore need to adapt such results to our weaker connectedness hypothesis on the graph of the specification. Regarding the second item, we are not aware of convergence results of multitype Galton-Watson trees to the line segment, but this might be easier than the convergence to the Brownian CRT.

Knowing the limit of the undecorated substitution tree is only a first step in proving permuton convergence, since the permutation depends not only on the shape of this tree, but also on the decorations of the internal nodes. More precisely, one needs to understand the law of the decorations of common ancestors of random leaves of the tree. This determines in particular the parameters of the Brownian separable or X -permuton appearing in Theorem 4.2. This would certainly needs some extra work, but is probably not out of reach with existing methods in the random tree literature.

We have not followed this strategy of proof in the general setting of Theorem 4.2. However, we have developed it in the specific case of substitution-closed classes. In this case, we found a combinatorial construction to reduce the study of the multitype Galton-Watson tree to that of a monotype one, on which much more is known. This has allowed us to reprove permuton limit results for uniform random permutations in substitution-closed classes (with a slight improvement on the range of applications of the result). With this strategy, we have also found new local limit results9 for such random permutations. This is the content of the article [START_REF] Borga | A decorated tree approach to random permutations in substitution-closed classes[END_REF], written in collaboration with J. Borga, M. Bouvel and B.

Stufler. We will not give further details here.

Some "concrete" corollaries

Scaling limits of combinatorial objects are rather abstract results, and one may ask whether one can deduce from them some more "concrete" corollaries, like the convergence of some real-valued statistics. We will discuss this question for a sequence σ n of random permutations converging to the Brownian separable permuton (which is the most interesting case in Theorem 4.2).

We have already mentioned that the convergence in terms of permutons is equivalent to the convergence of pattern densities. Fix p ∈ (0, 1). There exists a family of random variables (Λ τ (p); τ ∈ k≥1 S k ) with the following property. If a sequence of random permutation σ n converges to the Brownian separable permuton µ Br p , then, jointly for all τ, the random variable occ(τ, σ n ) tends to Λ τ (p). Unfortunately, we are not able to compute neither the density nor the generating functions of Λ τ (p). Moments of Λ 12 (1/2) can be computed either through a combinatorial description [BBF + 18, Section 9.1] or via an involved inductive formula (unpublished); with either approach, finding a general compact formula seems out of reach. The expression is arguably involved, but it is explicit and yields easily numerical approximation. Hence, the convergence to the Brownian separable permuton gives us a good control on the average repartition of points in the permutation diagram.

The last statistics I want to discuss is the length of the longest increasing subsequence LIS(σ) of a permutation σ. The asymptotic behavior of LIS(s n ), where s n is a uniform random permutation in the whole symmetric group S n , is a famous problem in discrete probability theory, already discussed in Section 1.3 of this thesis. Longest increasing subsequences in random permutations in classes are a much newer research topic: see [START_REF] Mansour | The longest increasing subsequence in involutions avoiding 3412 and another pattern[END_REF] and references therein. In the recent preprint [BBD + 21], we show the following result.

Proposition 4.4

For each n ≥ 1, let σ n be a sequence of random permutations tending to the Brownian separable permuton µ Br p for p ∈ [0, 1). Then LIS(σ n ) n converges to 0 in probability.

To obtain this result, we consider the inversion graphs G n of the random permutations σ n . We show that G n converges to W p , a graph analogue of µ Br p introduced in [BBF + 19a], which we call Brownian cographon. Also LIS(σ n ) corresponds to the size of the largest independent set, called independence number, of G n .

It turns out that a notion of independence number α of graphons has been introduced in [START_REF] Hladkỳ | Independent sets, cliques, and colorings in graphons[END_REF], where it is proved that it is lower-semicontinuous. Proposition 4.4 then reduces to the fact that, a.s., the Brownian cographon has independence number 0. The latter is proved using a self-similarity property of the Brownian excursion, and analyzing a resulting (in)equation in distribution for α(W p ). Details can be found in [BBD + 21].

Other combinatorial objects with subs tu on opera ons

We now take a bit of hindsight on our results on permutation classes and will discuss analogues for other combinatorial objects. A simple summary of our work is that we have taken advantage of the substitution operation on permutations and the associated tree encoding to obtain probabilistic results on uniform random objects in classes.

It turns out that permutations are not the only combinatorial objects on which a substitution operation and/or an associated tree encoding has been defined and studied. Many other examples can be found in the theory of combinatorial operads, see e.g. [START_REF] Chapoton | Operads and algebraic combinatorics of trees[END_REF][START_REF] Giraudo | Nonsymmetric Operads in Combinatorics[END_REF] (an operad is an algebraic structure, whose axioms correspond in some sense to natural associativity properties of substitution operations). For graphs, two kinds of decomposition trees have similar properties to substitution trees of permutations: modular decomposition trees and split decomposition trees [START_REF] Habib | A survey of the algorithmic aspects of modular decomposition[END_REF][START_REF] Charbit | Linear time split decomposition revisited[END_REF]. These decomposition trees can be useful to study uniform random graphs in these families.

We have started this program by looking at cographs, which can be defined through their modular decomposition trees. We proved in [BBF + 19a] that a uniform random cograph tends in the sense of graphons to a Brownian limiting object W p , already mentioned above, which is the graphon counterpart of µ Br p . We also refer to [START_REF] Stufler | Graphon convergence of random cographs[END_REF] for a proof of the same result using random tree theory, in the spirit of Section 4.6. This general idea of using substitution decompositions to prove scaling limit results can be pushed further. It would be for instance interesting to look at other classes of graphs through their modular or split decomposition trees. In the latter case, distance-hereditary graphs form the first natural example, see [START_REF] Chauve | An exact enumeration of distancehereditary graphs[END_REF] for their enumeration through their split decomposition tree. Also, recently, substitution operations on matchings have been defined in order to enumerate matching classes modeling RNA secondary structures [START_REF] Jefferson | The Substitution Decomposition of Matchings and RNA Secondary Structures[END_REF]. This opens the door to a probabilistic analysis of random matchings in such classes.

  Images on the front page: (Left) A Young diagram drawn with the Russian convention (see p. 22) (Right) Diagram of a uniform random separable permutation of size n = 457 (see p. 61);

  As a start, let us recall that it is customary to represent a partition λ = (λ 1 , . . . λ ℓ ) by a Young diagram: it consists in left-aligned rows of boxes with respectively λ 1 , λ 2 . . . and λ ℓ boxes. The size of the partition is the number of boxes in the diagram, i.e. λ 1 + • • • + λ ℓ . For example, the Young diagram on Figure2.1 (left) represents the partition (7, 4, 3, 3, 2). From now on, we speak interchangeably of partitions and Young diagrams.

FIGURE 2 . 1 (

 21 FIGURE 2.1 (Left) The Young diagram of the partition (7, 4, 3, 3, 2). (Right) A Plancherel-distributed random Young diagram of size 500.

  -Hammersley problem [Ula61, Ham72, Rom15]: what is the asymptotic behaviour of the length LIS(σ n ) of the longest increasing subsequence in a random permutation σ n of size n? As a consequence of Robinson-Shensted correspondence, the quantity LIS(σ n ) is distributed as the length λ 1 of the first row of a diagram λ of size n distributed with Plancherel measure. A more recent motivation to study the Plancherel measure is its link to random matrix theory, for example through the appearance of the discrete sine process in the bulk and the Airy ensemble at the edge of the diagrams, see [BOO00, Joh01, Oko05].

Figure 2 .

 2 Figure 2.1 (right) shows a Young diagram of size 500, taken at random with Plancherel measure.On the picture, it seems that the boundary of the diagram approaches a continuous curve. This fact was formalized and proved independently by Vershik-Kerov[START_REF] Vershik | Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux[END_REF] and Logan-Shepp[START_REF] Logan | A variational problem for random Young tableaux[END_REF], providing the equation of this limiting curve. Twenty-five years later, Kerov announced a central limit theorem for Plancherel distributed Young diagrams[START_REF] Kerov | The asymptotics of interlacing sequences and the growth of continual Young diagrams[END_REF]. The complete proof of this central limit theorem was given by Ivanov and Olshanski[START_REF] Ivanov | Kerov's central limit theorem for the Plancherel measure on Young diagrams[END_REF], based on Kerov's unpublished notes. It uses a new approach, based on the concept of polynomial functions on Young diagrams introduced by Kerov and Olshanski in[START_REF] Kerov | Polynomial functions on the set of Young diagrams[END_REF] -this new approach also provides an independent proof of the limit shape result.

  the identity: factors of different pairs commute with each other (since they have disjoint support) while factors of the same pair are inverse one of the other and cancel out. Hence we have constructed (m -1)!!(n) km/2 /k m/2 valid m-tuples (σ 1 , . . . , σ m ).

  Fig. 2.3, taken from [DF Ś10]). We remark that this function is always 1-Lipschitz. We then use standard notions of convergence of functions, in particular uniform convergence, to give a rigorous meaning to the convergence of Young diagrams. More formally, following Kerov, we define a continual Young diagram as a 1-Lipschitz function ω from R to R such that ω(x) ≥ |x| and ω(x) = |x| for |x| large enough. Taking the upper boundary of a Young diagram drawn with Russian convention gives an embedding of classical Young diagrams into the set of continual Young diagrams.

FIGURE 2 . 4

 24 FIGURE 2.4 The continual Young diagram Ω (red curve).

. 8 )

 8 For a Young diagram λ of size n, we denote λ the continual Young diagram obtained by rescaling the 2D picture by 1/ n in both directions. One easily shows that, for any λ n, we have ph ( λ) = n -h/2 ph (λ). With this, (2.8) reads as ph ( λn ) continual Young diagram, drawn on Fig 2.4, given by the equation

  .11) Ivanov and Olshanski (following notes of Kerov) proved the following theorem [IO02, Theorem 7.1]. Theorem 2.8: Central limit theorem for Plancherel measure Let λ n be a Plancherel distributed Young diagram of size n. Then the vector of random variables n qh ( λn )qh (Ω) (for h ≥ 1) converges in distribution to a vector (Z h / h + 1) h≥1 , where Z 1 , Z 2 , • • • are independent standard Gaussian random variables.

  FIGURE 2.7 A diagram of size n = 500 taken at random with Jack-Plancherel distribution of parameter α = 1/3.

  .7. This measure first appeared implicitly in an article of Kerov , who defined a Jack deformation of the Plancherel growth process [Ker00] -more precisely, Kerov constructs Jack-Plancherel distributed Young diagrams via a Markov process similar to that of Fig. 2.5 for q-Plancherel measure. Jack-Plancherel measures (and further generalizations) have then been analyzed in a series of research articles in recent years [Ful04, BO05, Mat08, Ols10, Mat10, DF16, BGG17, GH19, D Ś19, Mol20] and in Okounkov's survey of random partitions [Oko05, Section 3.3].

  3,... , where d -→ means convergence in distribution of the finite-dimensional laws. As in the case α = 1, we also have more geometric convergence results. Instead of renormalizing the Young diagram λ n in both directions by a factor 1/ n, we rescale it by α/n horizontally and by 1/ α n vertically 17 . Following [DF16], the resulting (continual) Young diagram is denoted A α ( λn ). We then have the following results [DF16, Theorems 1.1 and 8.1], generalizing Theorems 2.7 and 2.8. Theorem 2.13: Law of large number for Jack Plancherel measure Let λ n be a random Young diagram of size n, distributed with Jack-Plancherel measure of parameter α. Then the rescaled Young diagram A α ( λn ) tends to the function

  Proposition 3.15: Weighted dependency graph for triangles in G(n, M ) Let L n be the complete graph on B n with the following weights • if I and J are 3-element subsets with | I ∩ J | = 2 (i.e. the corresponding triangle share an edge), then the edge {I , J } gets weight 1;

FIGURE 3 . 2 (

 32 FIGURE 3.2 (Top) The arc pattern A corresponding to {{1, 3, 4}, {2, 5}}. (Bottom) An occurrence of A in a larger set-partition.

  is a (C , Ψ)-weighted dependency graph for the family 1[ i j ], i < j , for some C = (C r ) r ≥1 depending on n with C r = Õ (1) and some function Ψ on multiset of vertices a . a We use the notation f = Õ (g ), standard in algorithmics, which means f = O (g (log n) d ) for some d .

FIGURE 4 . 1

 41 FIGURE 4.1 Example of substitution of permutations.

FIGURE 4 . 3

 43 FIGURE 4.3 The support of the X -permuton with parameter p = (p left + , p right + , p left -, p right -), denoting a = p left + + p left -and b = p left -+ p right -. Left: The generic case. Right: A degenerate case where b = 0.

)

  ∈ ∆ 3 . We set a = p left + + p left -and b = p left -+ p right -. The X -permuton µ X p with parameter p is the probability measure constructed as follows:• it is supported on the union of the four line segments joining the point (a, b) to the corners of the unit square [0, 1] 2 ;• the weights of these segments are respectively p left + , p right + , p left -, p right -;• for each segment, its weight is uniformly distributed on the segment.

FIGURE 4 . 4

 44 FIGURE 4.4 Large uniform random permutations in the classes C X 1 , C X 2 and C X 3 , respectively.

FIGURE 4 . 5

 45 FIGURE 4.5 A signed Brownian excursion (with only finitely many signs represented) and the graph of the associated infinite permutation σ ∞ . We have circled some points of the Brownian excursion and the corresponding points of the graph of σ ∞ to illustrate the definition. The minimum of the excursion between the circled points carries a sign and, consequently, the corresponding points in the graph of σ ∞ form an inversion. 1 2

  Fig 4.5.

FIGURE 4 . 7

 47 FIGURE 4.7 Large uniform random permutations in the classes C b 1 , C b 2 and C b 3 , respectively.

FIGURE 4 . 8

 48 FIGURE 4.8 A large uniform random permutation in some finitely generated class.

2. 5 ]

 5 relates such convergence to the convergence, for each k ≥ 1, of the pattern induced by k random elements of the permutation. To study the distribution of this random pattern, we enumerate, for each π, the family C π of permutations in C with k marked elements inducing the pattern π. It turns out that the combinatorial specification that we have for C can be refined into a combinatorial specification for C π .

  For a pattern τ in S k and a permutation σ in S n , we define occ(τ, σ)= # I ⊂ [n] : pat I (σ) = τ , occ(τ, σ) = occ(τ, σ) n k, which are respectively the number of occurrences and the density of the pattern τ in σ. Then we have the following result (which is a particular case of [BBF + 20, Theorem 2.5]):

  Since permutons are measures on [0, 1] 2 , a natural statistics is the weight of a given rect-angle R = [a; b] × [c; d ] ⊂ [0, 1] 2 . If σ n converges to the Brownian separable permuton µ Br p , then we have 1 n E # i : i n , σ n (i ) n ∈ R → E µ Br p (R) . (4.3) It turns out that the right-hand side can be made explicit. The following formula has been found by M. Maazoun in [Maa20]: E µ Br p (R) = R α p (x, y)d xd y, where α p (x, y) = min(x,y) max(0,x+y-1) 3p 2 (1p) 2 d a 2π a(xa)(1xy + a)(ya)

Theorem 2.4: Central limit theorems for characters

	This	shows	that	the	moments	of	n k/2 χ[n] (k) / k,	or	equivalently 7	of
	n k/2 tr[ρ λ ((1, . . . , k))]/( k dim(λ)), tends to δ m even (m -1)!!. The latter are well-known
	to be the moments of the standard Gaussian distribution; therefore by the method of mo-
	ments, we get the following theorem, originally found by Kerov [Ker93a] and Hora [Hor98].
	Let λ be a Plancherel-distributed Young diagram of size n. Fix k ≥ 2. The random
	variable n k/2 tr[ρ λ ((1, • • • , k))]/( k dim(λ)) tends in distribution and in moments to a
	standard Gaussian random variable.

  For each n ≥ 1, the element Cl µ;n is mapped to a function on Young diagrams of size n, which we denote Ch µ;n . The whole sequence (Ch µ;n ) n≥1 can be seen as a function Ch µ on the set Y = Y n of Young diagrams of all sizes. Explicitly we have Ch µ

	• • • , a k ) of distinct integers between 1 and n. If k > n,
	the sum is empty, and thus Cl µ;n = 0; otherwise it is a nonzero multiple of C µ∪(1 n-k ) . The
	notation Cl stands for class, since these are multiples of conjugacy class sums. The inter-
	est of this normalization of conjugacy class sums lies in the following property: there exist
	coefficients g τ µ,ν independent of n such that, for all partitions µ and ν and all n, we have
	Cl µ;n Cl ν;n =	τ	g τ µ,ν Cl τ;n ,	(2.4)
	where the sum runs over partitions τ of all sizes. This property is easily seen, splitting the
	double sum defining Cl µ;n Cl ν;n according to the equalities between indices in the first and
	in the second sum. Details can be found, e.g., in [Bia03, Section 3].
	Recall that with an element x in Z (C[S n ]), we can associate a function
	λ → tr[ρ λ (x)]/ dim(λ) on the set Y

n of Young diagrams of size n. Fix a partition µ.

  = 0, i.e. if the class C j appear in the equation defining C i . Besides, a directed graph is strongly connected if there is a directed path going from any vertex to any other vertex in the graph.

	∂P i
	∂C j

To get general results, it is standard to assume that the dependency graph of the system is strongly connected; see e.g. [FS09, Thm VII.6] and [Drm09, Thm 2.33]. For the reader's convenience, we recall the relevant definitions. The dependency graph of the system is the directed graph on {0, . . . , d } with an edge from j to i if

The cycle-type of a permutation σ is the integer partition obtained by taking in decreasing order the length of the cycles of σ.

The (left-)regular representation of a group G has a basis (δ g ) g ∈G and an element h in G acts on the basis by sending δ g on δ hg .

The family ( χτ ) τ n is a basis of the space of functions on Young diagrams of size n.

We note that the map is naturally extended to the whole symmetric group algebra C[S n ] with the same formula (i.e. x in C[S n ] is mapped to the function λ → tr[ρ λ (x)]/ dim(λ)); this extension is however not an algebra morphism anymore.

The most general result of this kind of which the author is aware covers the case where one of the partition is the one-part partition (n); see[START_REF] Poulalhon | Factorizations of large cycles in the symmetric group[END_REF].

We recall the standard double factorial notation (2r -1)!! = 1 • 3 • • • (2r -1).

Here, we see the element (1, . . . , k) of S k as an element of the larger symmetric group S n (fixing all elements larger than k); with this identification, it has cycle-type (k, 1 n-k ) as wanted.

The shift of index (the moment of order k -2 is denoted p k ) is justified by a homogeneity relation when scaling continual diagrams in both directions, on which we will not expand here.

To prove eq. (2.7), Ivanov and Olshanski start from an example in Macdonald's book on symmetric function [Mac95, Chapter I, Section 7, Example 7] and perform simple analytic manipulation. The example in Macdonald book itself comes from an application of the Murnaghan-Nakayama rule (no further representation theory is needed). Thus, this formula is in some sense a special case of Murnaghan-Nakayama rule in disguise.

Naturally, the formula (2.9) for Ω was chosen so that these moments match. To guess the right formula for Ω based on (2.10), one can use the theory of Stieljes transforms; see[START_REF] Wall | Analytic Theory of Continued Fractions[END_REF] for the general theory and[START_REF] Biane | Approximate factorization and concentration for characters of symmetric groups[END_REF] for an application to finding limit shapes of Young diagrams.

This is in fact a slight modification of Chebyshev polynomials. They are related to the usual Chebyshev polynomials U k (x) by U k (x) = u k (2x).

An algebra A is called semi-simple if every representation of A can be decomposed as a direct sum of irreducible representations.

Actually, the terminology Jack polynomials is more common. However, in the theory of symmetric polynomials, it is customary to use polynomials when working with a finite number of variables and functions for infinitely many variables. It is therefore more logical to speak of Jack symmetric functions here.

Such different scaling factors for rows and columns are standard in the theory of Jack symmetric functions, see[START_REF] Kerov | Anisotropic Young diagrams and Jack symmetric functions[END_REF] and the deformations of hooks and contents in [Mac95, Section 6.10].

In fact, one can defined more generally joint cumulants of order r as soon as the variables have finite r -th moment, but let us restrict to the case with finite small exponential moments for simplicity.

The Kolmogorov distance between two probability distributions on R is simply defined as the supremum norm between their cumulative distribution function. It is a standard way to measure speed of convergence in asymptotic normality.

I have tried in collaboration with A. Röllin to use Stein's method to obtain moderate deviation estimates from the existence of an exchangeable pair, but we did not succeed.

as testified by the still open question of enumerating 1324-avoiding permutations, see [BBEPP20] and references therein.

Most simultations have been conducted with the sage module Specifier, developed by my collaborator M. Maazoun.

For the reader not familiar with stochastic processes, we recall that one can think at a Brownian excursion as a Brownian motion on [0, 1] starting at 0 conditioned to stay nonnegative and to come back to 0 at time 1.

It is easy to show that a.s., a Brownian excursion has countably many local minima, explaining the indexing of S i by i ≥ 1; one has to be careful however in how we index local minima, so that the relevant variables, such as the function σ ∞ defined below, are measurable; we will not discuss such details here, and refer the reader to[START_REF] Maazoun | On the brownian separable permuton[END_REF].

We note that arg min [x,y] e is a.s. well-defined, since a.s., all local minima of a Brownian excursion have distinct values.

Substitution trees are a generalization of the separation trees mentioned in Section 4.4.2.

A notion of local limit for permutations was recently suggested by my student J. Borga, co-advised by M.Bouvel, during his PhD thesis[START_REF] Borga | Local convergence for permutations and local limits for uniform ρavoiding permutations with |ρ| = 3[END_REF].

Remerciements

The main difference with Janson's normality criterion (Theorem 3.3) is that we consider weighted degrees and not usual degrees. Since the weights are in [0, 1], weighted degrees are smaller than usual degrees. In particular, weighted degrees can be small even when the underlying graph of L n is the complete graph, i.e. when one cannot find two independent variables in the family {Y n,i , 1 ≤ i ≤ N n }. Consequently, Theorem 3.12 has a larger range of applications than Theorem 3.3.

A stability property

In this section, we present a stability property of weighted dependency graphs. Informally, when we have a weighted dependency graph for a family {Y α , α ∈ A}, we can automatically construct a new one for monomials Y I = α∈I Y α in the original variables Y α . As we will see in the next two sections, this property is useful in applications.

Let us present this formally. For m ≥ 1, we denote by MSet ≤m (A) the set of multisets of size at most m of elements of A. For I ∈ MSet ≤m (A), we let Y I = α∈I Y α . Furthermore, let L is a weighted graph with vertex set A and denote w(i , j ) the weight between i and j ; by convention w(i , j ) = 0 if there is no edge between i and j and w(i , j ) = 1 if i = j . We construct a weighted graph L m with vertex set MSet ≤m (A) as follows: the weight W (I , J ) of the edge between I and J is given by

With this notation, we have the following result.

Proposition 3.13: Stability of weighted dependency graphs

Let {Y α , α ∈ A} be a family of random variables with a C -weighted dependency graph L, and fix a positive integer m.

Then there exists a sequence C = (C r ) r ≥1 depending only on m, r and C such that L m is a C -weighted dependency graph for the family {Y I , I ∈ MSet ≤m (A)}, The proof of this proposition uses a general formula for cumulants of products of random variables, due to Leonov and Shiraev [START_REF] Leonov | On a method of calculation of semi-invariants[END_REF], and some elementary combinatorial observations regarding spanning trees. We refer to [Fér18, Proposition 5.11] for details.

A first example: graphs with a fixed number of edges

We now give an example of application of the extended criterion; this example is an analogue of Example 3.4 with weak dependencies. We consider the triangle count statistics in Erdős-Rényi random graph models G(n, M n ), i.e. when G is taken uniformly at random among all graphs with vertex-set [n] and M n edges. To simplify the discussion, we will assume that M n is of order n 2 , but the method works in more generality; it also works for counting copies of more general subgraphs in G(n, M n ), see [START_REF] Féray | Weighted dependency graphs[END_REF]Section 7].

Let A n be the set of unordered pairs of vertices, i.e. of 2-element subsets of [n]. We start by studying the simple random variables (Y e ) e∈A n , where Y e is the indicator function of the dency graph for the sequence C = (C r r -2 ) r ≥1 , but the converse is not true. Unfortunately, among all the settings in which we have found weighted dependency graphs (SSEP, Ising model, Markov chains, random matchings, permutations, set-partitions, G(n, M )), we have been able to prove only in two situations that the weighted dependency graph is uniform:

for Markov chains and for the high temperature or strong magnetic field Ising model. In the case of low temperature Ising model, there is a weighted dependency graph in the sense of Defintion 3.11, but we can prove that it is not uniform in the sense of Defintion 3.19. In other cases, we do not know whether the weighted dependency graphs which we have found are uniform in the sense of Defintion 3.19 or not. Also, uniform weighted dependency graphs are not stable by product (in the sense of Section 3.3.2), limiting their range of applications.

CHAPTER 4

The Brownian separable permuton Random permutations form a classical topic in discrete probability theory. As explained more generally in the introduction, a standard question is the asymptotic analysis of X n = f (σ n ), where σ n is a uniform random permutation of size n and f a well-chosen statistics. We refer to [START_REF] Goncharov | Some facts from combinatorics[END_REF][START_REF] Wolfowitz | Note on runs of consecutive elements[END_REF] for early works of this kind, on the number of cycles and runs of σ n , respectively. A more general result was obtained by Hoeffding [START_REF] Hoeffding | A combinatorial central limit theorem[END_REF], who gives conditions for the asymptotic normality of statistics of the form f (σ) = k≤n a k,σ(k) , where for each n, we are given a matrix (a k, j ) 1≤k, j ≤n of real numbers. Another well-known example is that of the length of the longest increasing subsequence, see, e.g., [START_REF] Romik | The surprising mathematics of longest increasing subsequences[END_REF] for an overview of the topic. We can also mention more recent works, for instance on pat- restricting it to some interesting subsets of permutations (in particular conjugacy classes [START_REF] Fulman | Central limit theorem for peaks of a random permutation in a fixed conjugacy class of S n[END_REF][START_REF] Kim | Central limit theorem for descents in conjugacy classes of S n[END_REF], or sets of pattern-avoiding permutations [START_REF] Madras | Random Pattern-Avoiding Permutations[END_REF][START_REF] Miner | The shape of random pattern-avoiding permutations[END_REF]). For some of these models (either non-uniform, or uniform on a subset), in addition to studying some statistics, it is interesting to look at the scaling limit of the permutations. An appropriate setting for this is the theory of permutons [HKM + 13], which has received recently an increasing interest.

We report in this chapter on a series of papers [BBF + 18, BBF + 20, BBFS20, BBF + 19b, Now that we have an "infinite permutation" σ ∞ , we shall construct a permuton, i.e. a measure on [0, 1] 2 from it. By analogy with the discrete case (see Fig. 4.2), for each t in [0, 1] we want to put some mass at coordinates (t , σ ∞ (t )). The natural choice is to take the push forward of the Lebesgue measure by the application t → (t , σ ∞ (t )).

This construction gives us a random permuton (the randomness coming from the initial Brownian excursion and the signs on its local minima) whose law depends on the parameter p in [0, 1]. We denote it µ Br p and call it (biased) Brownian separable permuton.

We now discuss examples of permutation classes C converging to µ Br p . The most studied class in this category is the class of separable permutations 6 , considered in the article [BBF + 18]; by symmetry, we have p = 1/2 in this case. More generally 7 , classes with finitely many permutations and closed for the substitution operation also converge to µ Br p , for some parameter p depending of the class. Here, the assumption of having finitely many simple can be relaxed to an analytic assumption on the generating series of the simple per- The first one is the class of separable permutations, the second one a substitution-closed class with infinitely many simple permutations (in fact, it is the substitution closure of Av(123), originally considered in [START_REF] Atkinson | Substitution-closed pattern classes[END_REF]; see [BBF + 20] for details on its scaling limit), and the third one has only finitely many simple permutations but is not substitution-closed (see [BBF + 19b] for details). The universality of the limit is visible on the pictures, which all have the same "aspect".

The technical condi on

We now state and discuss the technical condition in Theorem 4.2. For this, we need to go a bit backwards and discuss enumerative aspects of finitely generated classes. In particular, we recall (see Theorem 4.1) that the generating series of such a class C is always algebraic.

In the paper [BBP + 17] (see also [START_REF] Brignall | Simple permutations and algebraic generating functions[END_REF]), this algebraicity result has been strengthened: an algorithm is given to compute a combinatorial specification for any finitely generated permutation class C . 6 Separable permutations are standard objects in enumerative combinatorics and algorithmics (see, e.g., [START_REF] Bose | Pattern matching for permutations[END_REF] and [START_REF] Albert | Equipopularity classes in the separable permutations[END_REF]), but they also appear in real analysis (describing reordering of polynomials going through a common root [START_REF] Ghys | A singular mathematical promenade[END_REF]) and in probability theory (bootstrap percolation [START_REF] Shapiro | Bootstrap percolation, the Schröder numbers, and the n-kings problem[END_REF]). 7 The class of separable permutations is substitution-closed and contains no simple permutations.