Journées MathSTIC 2019

10h00 – 10h45 Grégory Miermont

The breadth-first construction of scaling limits of graphs with finite excess

Random graphs with finite excess appear naturally in at least two different settings: random graphs in the critical window (aka critical percolation on regular and other classes of graphs), and unicellular maps of fixed genus. In the first situation, the scaling limit of such random graphs was obtained by Addario-Berry, Broutin and Goldschmidt based on a depth-first exploration of the graph and on the coding of the resulting forest by random walks. This idea originated in Aldous' work on the critical random graph, using instead a breadth-first search approach that seem less adapted to taking graph scaling limits. We show hat this can be done nevertheless, resulting in some new identities for quantities like the radius and the two-point function of the scaling limit. We also obtain a similar ``breadth-first'' construction of the scaling limit of unicellular maps of fixed genus. This is based on joint work with Sanchayan Sen.

10h50 – 11h35 Minmin Wang

Prunings, cut trees and the reconstruction problem

We consider prunings of two families of continuum random trees: the Lévy trees and the inhomogeneous continuum random trees. The so-called cut trees encode the genealogies of the fragmentations that come with the pruning. The reconstruction problem asks how much information about the initial tree is retained in its cut tree and how to recover it from the cut tree. We propose a new approach to the reconstruction problem, which has been treated previously for the Brownian CRT and for the stable trees. Our approach does not rely upon self-similarity and can apply to both Lévy trees and inhomogeneous continuum random trees.
Joint work with Nicolas Broutin and Hui He.

14h00 – 14h45 Anne-Laure Basdevant

Plus longue sous suite croissante avec contraintes

Étant donné un nuage de points poissonien, Hammersley étudia dans les années 70 le nombre maximal de points du nuage par lequel un chemin croissant peut passer. Ceci permettait alors d'obtenir la longueur asymptotique de la plus longue sous-suite croissante dans une grande permutation aléatoire.
Dans cet exposé, nous généraliserons le problème d'Hammersley en rajoutant des contraintes sur le chemin et nous exposerons des couplages qui permettent de se ramener au problème originel.
Travail en collaboration avec Lucas Gerin

14h50 – 15h35 Jacopo Borga

Phase transition for almost square permutations

A record in a permutation is an entry which is either bigger or smaller than the entries either before or after it (there are four types of records). Entries which are not records are called internal points. We explore scaling limits (called permuton limits) of uniform permutations in the classes Sq(n,k) of almost square permutations of size n+k with exactly k internal points.
We first investigate the case when k=0, this is the class of square permutations, i.e. permutations where every point is a record. The starting point for our result is a sampling procedure for asymptotically uniform square permutations. Building on that, we characterize the global behavior by showing that square permutations have a permuton limit which can be described by a random rectangle. We also explore the fluctuations of this random rectangle, which we can describe through coupled Brownian motions.
We then characterize the permuton limit of almost square permutations with k internal points, both when k is fixed and when k tends to infinity along a negligible sequence with respect to the size of the permutation. Here the limit is again a random rectangle but of a different nature: we will show during the seminar that a phase transition on the shape of the limiting rectangles arises for different values of k.
Joint work with E.Slivken and E. Duchi.

16h20 – 17h05 Valentin Féray

Random permutation factorizations

We study random minimal factorizations of the n-cycle into transpositions, which are factorizations of the full cycle (1,...,n) as a product of n-1 transpositions. It is known since Denes (1959) that they are counted by the sequence n^n-2 and bijections with Cayley trees and parking functions have been found. Moreover, these factorizations are naturally encoded (in two different ways) by sequences of non-crossing set of chords of the unit disk.
We establish limit theorems for these sets of chords. The limiting objects are constructed from Levy’s excursion processes and interpolate between the circle and Aldous’ Brownian triangulation. One key step of the proof is to connect our model with conditioned bitype Galton-Watson trees with offspring distribution varying with $n$, and to find the limit of the contour function of those trees. If time allows, we will also describe the limit of the trajectory of a fixed element in this factorization (in some sense, this is a local limit result in space).
This is a joint work with Igor Kortchemski.

10h00 – 10h45 Robin Stephenson

The scaling limit of a critical random directed graph

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 + λ n^-4/3 for λ ∈ R. We show that, within this critical window, the strongly connected components of G(n,p), rescaled by n^-1/3, converge in distribution to a sequence (C₁,C₂,...) of finite strongly connected directed multigraphs with edge lengths which are either 3-regular or loops. The convergence occurs the sense of an L¹ 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. We show that the limiting sequence (C₁,C₂,...) contains only finitely many components which are not loops.

10h50 – 11h35 Marie Théret

Cardinality of a minimal cutset in first passage percolation

We consider the model of first passage percolation on Z^d in dimension d≥2 : we associate with the edges of the graph a family of i.i.d. non negative random variables. We interpret the random variable associated with an edge as its capacity, i.e., the maximal amount of water or information that can cross the edge per second. This leads to a natural definition of maximal flow through a bounded domain of the graph from a collection of sources to a collection of sinks. This maximal flow is equal to the minimal capacity of a cutset, i.e., a set of edges such that if we remove it from the graph we disconnect completely the sources from the sinks. In this talk, we will focus on one of the properties of this minimal cutset : it's cardinality. This is a joint work with Barbara Dembin (LPSM, Université de Paris).

14h – 14h45 Sergey Dovgal

The subcritical phases of random structures

We will discuss the emerging substructures in graphs with degree constraints, digraphs, acyclic digraphs, and 2-CNF below the point of their respective phase transitions. While long time ago, probabilistic method allowed to establish the location of the transition points, with some very rough properties, more and more refined results gradually become available. With analytic combinatorics as a main tool, we will see what exactly is happening when the structure approaches its boiling point. Based on joint works with Élie de Panafieu and Vlady Ravelomanana.

14h50 – 15h35 Andrea Sportiello

The tangent method for the determination of Arctic Curves: the simplest rigorous application

In the paper Arctic curves of the six-vertex model on generic domains: the Tangent Method [J. Stat. Phys. 164 (2016), arXiv:1605.01388], of Filippo Colomo and myself, we pose the basis for a method aimed at the determination of the ``arctic curve'' of large random combinatorial structures, i.e. the boundary between regions with zero and non-zero local entropy, in the scaling limit.
In this paper many things are claimed, and few are proven. In particular, it is not made clear that variants of it can be made fully rigorous in certain circumstances. In this seminar we present the simplest such instance: we rederive the arctic circle phenomenon for ``domino tilings of the aztec diamond'', first discovered by Jockusch, Propp and Shor [arXiv:math/9801068, but in fact from 1995].

16h20 – 17h05 Vincent Beffara

TBA

9h30 – 10h15 Jean-Baptiste Gouéré

Non percolation dans des graphes géométriques orientés de degré sortant égal à 1

Considérons un processus de Poisson ponctuel dans le plan. À l'instant initial, un segment issu de chaque point de ce processus croît à une vitesse aléatoire dans une direction aléatoire. La croissance de ce segment s'arrête dès qu'il en touche un autre. La réunion des segments percole-t-elle ? Quel est le lien avec le titre de l'exposé ? Travail en collaboration avec David Coupier et David Dereudre.

10h20 – 11h05 Dariusz Buraczewski

Large deviations for random walk in random environment

In this talks we will discuss recent results concerning large deviations of one-dimensional nearest neighbour random walk in site-random environment. Our main contribution is an extension of large deviation results to precise (rather than logarithmic) asymptotic. We will explain how this result is related to large deviations of branching process in random environment and stochastic recurrence equations

11h10 – 11h55 Alexander Iksanov

Functional limit theorems for divergent perpetuities and Galton-Watson processes with very active immigration

I am going to discuss weak convergence in the Skorokhod space of Galton-Watson processes with immigration (GWI), properly normalized, under the assumption that the tail of the immigration distribution has a logarithmic decay. It will be explained that the limits are extremal shot noise processes. Interestingly, both the behavior in mean and the survival probability (especially in the subcritical case) of the underlying Galton-Watson processes without immigration affect the asymptotics in question.
The sequence of the conditional expectations of GWI given the immigration forms a very particular instance of a (divergent) perpetuity. In view of this I shall also present functional limit theorems in the Skorokhod space for general divergent perpetuities and suprema of perturbed random walks which are closely related objects.