Program

Mini-courses

Probabilistic cellular automata (PCA) are a class of random discrete dynamical sytems. They can be seen both as a generalization of deterministic cellular automata, and as the synchronous counterparts of finite-range interacting particle systems: time is discrete and at each time step, all the cells are updated independently in a random fashion, according to a distribution depending only on the states of a finite number of their neighbours. I will present some general tools to study the evolution of PCA, and show by several examples that they appear in various contexts in combinatorics.

We give an example of the sort of question we will look at. Let T be the set of all graphs which contain a triangle as a subgraph, i.e. all graphs G which contain three vertices u,v,w such that uv,uw and vw are all edges. Let the random graph G(n,p) be the graph with vertex set [n] = {1,2,...,n} in which each possible edge is present with probability p, independently of the others.

We are interested in how the probability that G(n,p) contains a triangle changes for different values of p. Write u(n,p) for the probability that the random graph G(n,p) has a triangle. Clearly, for any n, u(n,0)=0 and for n at least three, u(n,1)=1. One can also show that for p < p', u(n,p)<u(n,p'). For edge probability p=p(n), we investigate the behaviour of u(n,p(n)) as n tends to infinity. We will find that for p(n) and p'(n) `not too far apart' that u(n,p(n)) tends to zero while u(n,p'(n)) tends to one: a sort of a phase transition in the behaviour. These ideas will be made precise in this course as we investigate how fast such phase transitions can occur. Material covered to include some theory of Boolean functions and the Margulis-Russo formula.

The quantitative properties of dynamics in polygon billiard are strongly related to the geometry and dynamics of moduli spaces of flat surfaces (that can be seen as a larger space of deformation of the polygonal billiard table). After giving some insight on this relation, I will explain in particular why some counting problems in these spaces are particularly relevant for the study of billiard dynamics. I will then focus on the problem of counting square-tiled surfaces with fixed combinatorial data, and show that it is closely related to the enumeration of (metric) maps with fixed combinatorics. I will then explain the main conjectures about the enumeration of square-tiled surfaces of large genus, in terms of maps.

Long talks

Sturmian words are a fundamental family of words, due to their low complexity without being periodic. In this talk we introduce a probabilistic study of the recurrence function of these words, and more particularly of substitutive Sturmian words, built with letter substitutions. The recurrence functioncan be viewed as a waiting time to discover all the factors of length n of a Sturmian word. In this talk we introduce Sturmian words, the recurrence function, and the associated models and results.

There exist several combinatorial models of lambda calculus terms. Since these objects, independently of the assumed representation, exhibit a rather unusual structure, studying each of the models is interesting on its own. But what makes the whole research even more intriguing are surprising discrepancies in behavior of counting sequences and properties of typical terms. This talk aims at presenting an overview of known results with its main focus on statistical (or typical) properties of lambda terms. These results are usually proven by means of analytic combinatorics, however, in our quest for further answers, it might be about time to go beyond the limits of this powerful tool.

Pattern-avoiding permutations were defined in the sixties, and their study developed from the nineties, mostly with an enumerative point of view. These past few years, pattern-avoiding permutations have also been studied from a probabilistic point of view. This research line focuses on describing a typical permutation of large size in a pattern-avoiding family.

This talk presents some recent results obtained about the scaling limits of certain permutation classes, described in terms of permutons (which can be seen as permutations of infinite size). An essential tool is the substitution decomposition of permutations, which allows to represent them as trees.

We will review the story arc of the latest developments in combinatorics of walks, or how one can go from moving around a city to Schramm-Loewner Evolution to quantum mechanics while getting 2 field medals and a Wolff prize along the way. Plenty of new breakthroughs will be presented, from a 10 orders of magnitudes improvement brought about by number theory over probability theory to mysterious fractal-like equations at the heart of many-body quantum systems.

Short talks

  • On the limit of minimum weight spanning trees (Johanna Strömberg)

A well-known result of Alan Frieze states that the expected weight of a minimum weight spanning tree of a complete graph with random edge weights tends to $\zeta(2)$, provided the edge weights are sufficiently well-behaved. In this talk, I will give a simpler proof of the result in two ways: based on Prim's and Kruskal's algorithms for finding minimum weight spanning trees.

  • Discrete correlation of order 2 of generalized Rudin-Shapiro sequences on alphabets of arbitrary size (Pierre-Adrien Tahay), Slides

Pseudorandom sequences are deterministic sequences on finite alphabets with similar properties to those of random sequences. In 1997 and 1998, Mauduit and Sárközy published two papers on the topic with various results including pseudorandomness of the Legendre symbol, correlations of Champernowne, Thue-Morse and Rudin-Shapiro sequences over two letters. Several papers followed their research. In 2009, Grant, Shallit and Stoll constructed a large family of pseudorandom sequences, called generalized Rudin-Shapiro sequences, over alphabets whose size is a squarefree integer. In this talk, I will first present their results and the methods (such as those of exponential sums techniques), and will then give generalizations recently obtained in my thesis work which allow to cover alphabets of arbitrary size. The major point to obtain these generalizations is the notion of "difference matrices".

  • The scaling limit of a critical random directed graph (Robin Stephenson), Slides

We consider the random directed graph G(n,p) with vertex set {1,2,...,n} in which each of the n(n-1) possible directed edges is present independently with probability p. We are interested in the strongly connected components of this directed graph. A phase transition for the emergence of a giant strongly connected component is known to occur at p = 1/n, with critical window p = 1/n + lambda n^{-4/3} for lambda in R. We show that, within this critical window, the strongly connected components of G(n,p) , ranked in decreasing order of size and rescaled by n^{-1/3}, converge in distribution to a sequence (C_1,C_2,...) of finite strongly connected directed multigraphs with edge lengths which are either 3-regular or loops. The convergence occurs the sense of an L1-sequence metric for which two directed multigraphs are close if there are compatible isomorphisms between their vertex and edge sets which roughly preserve the edge-lengths. Our proofs rely on a depth-first exploration of the graph which enables us to relate the strongly connected components to a particular spanning forest of the undirected Erdős–Rényi random graph G(n,p), whose scaling limit is well understood. This is joint work with Christina Goldschmidt.

  • Dynamic classification of filtration (Paul Lanthier), Slides

The study of filtration is a profusely studied theory whose one branch is classification. One of the pionners of the classification of filtrations is A. Vershik whose works have been extended by S. Laurent. We are interested by filtrations which are called "natural filtrations" meaning they are generated by a stochastic process that will be in our case in negative time. Vershik and Laurent's works are applicable for some probabilistic spaces. The innovative aspect of this work is to extend the classification of filtration in negative time defined on probabilistic spaces to ones defined on dynamical systems, by adding a transformation.

  • Exact enumeration of weighted Eulerian orientation using Jacobi theta functions (Andrew Elvey Price), Slides

I will describe our solution to the problem of enumerating planar 4-valent Eulerian orientations with a weight on each vertex of a certain type. Our solution to this problem is closely based on work of Kostov in mathematical physics literature, where this is known as the six vertex model on a random lattice. I will then show bijectively that the generating function of weighted 4-valent Eulerian orientations is equal to the generating function of general Eulerian partial orientations, with a weight on each undirected edge. This yields an alternative solution to the problem of enumerating Eulerian orientations, which was posed by Bonichon, Bousquet-Mélou, Dorbec and Pennarun, then solved by E.P. and Bousquet-Mélou, following numerical work by E.P. and Guttmann. This is joint work with Mireille Bousquet-Mélou and Paul Zinn-Justin.

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under the Grant Agreement No. 759702.

  • Some asymptotic properties of high genus maps (Baptiste Louf), Slides

Combinatorial maps are, roughly speaking, graphs embedded on surfaces. They have a lot of nice properties, and can be studied from various points of view (bijective, algebraic, analytic, …). The focus of this talk will be the geometric properties of large random maps. Let n be the « size » of the map (for instance, the number of edges), and take a uniform map of size n. What does it look like for very large n ?

If the genus of the map (the number of « holes » of the surface) is fixed, it has been well studied in the last ~20 years, and there is a long list of results for several observables. But if the genus goes to infinity linearly in the size (g~cn), then it’s a totally different setting where the maps seem to present a « hyperbolic behaviour » in some sense. I will present some recent results about this model (namely the local limit, and the diameter).

I will shamelessly skip all the proofs and try to give some geometric intuition instead. This is based on joint work with T. Budzinski on the one hand, and G. Chapuy-C. Marzouk on the other hand.

  • Tiling translation surfaces with Wang tiles (Khaydar Nurligareev), Slides

Wang tiles are squares with colored edges which must be placed edge-to-edge; colors on contiguous edges must match, rotations and reflections of the tiles are forbidden. Pairing the edges of given n Wang tiles at random, we obtain a translation surface. What properties are typical for this surface? For the easiest case (all edges have the same color) we will convince that the surface is connected with probability 1 as n approaches infinity and we will discuss its typical characteristics such as the genus, the number of singularities, the diameter, etc.

  • On kernel regression estimation for irregularly spaced spatial data (Lucas Reding), Slides

In this talk, we present a new central limit theorem for the well-known Nadaraya-Watson regression estimator in the context of strongly mixing and weakly dependent random fields in the sense of Rosenblatt (1956) and Wu (2005) respectively. Our main motivation is to provide mild conditions on the mixing coefficients and bandwidth parameters for the estimator to be asymptotically normal.