Previous seminars in Probability and Combinatorics

2021

25 March, 2021

Details: Thomas Budzinski, ENS Lyon - Online, 10:15 - 11:15
Title: Universality for random maps with unconstrained genus

Abstract: We consider the random map model obtained by starting from a finite set of polygons and gluing their sides two by two uniformly at random. Several properties of this model (central limit theorem for the genus, asymptotic Poisson--Dirichlet distribution for vertex degrees) were proved by Gamburd and Chmutov--Pittel using techniques from algebraic combinatorics. I will describe new, probabilistic proofs of these results which can be used to obtain more precise information about the model. In particular, our results support the following conjecture: asymptotically, the law of the graph associated to the map should only depend on the total number of edges, and not on how they are distributed between the faces.
Based on joint work with Nicolas Curien and Bram Petri.

18 March, 2021

Details: Bram Petri, Sorbonne Université - Online, 10:15 - 11:15
Title: Random 3-manifolds with boundary

Abstract: When one glues a finite number of tetraheda together along their faces at random, the probability that the resulting complex is a manifold tends to zero as the number of tetrahedra grows. However, the only points that pose problems are the vertices of this complex. So, if we truncate the tetrahedra at their vertices, we obtain a random manifold with boundary. I will speak about joint work with Jean Raimbault on the geometry and topology of such a random manifold. I will not assume any familiarity with 3-dimensional geometry and topology.

25 February, 2021

Details: Igor Kortchemski, École polytechnique - Online, 10:15 - 11:15
Title: Cauchy-Bienaymé-Galton-Watson

Abstract: We will be interested in the structure of large random Bienaymé-Galton-Watson trees, with critical offspring distribution belonging to the domain of attraction of a Cauchy law. We will identify a so-called condensation phenomenon, where a single vertex with macroscopic degree emerges. This is a joint work with Loïc Richier.

18 February, 2021

Details: Svante Janson, Uppsala University - Online, 10:15 - 11:15
Title: The sum of powers of subtree sizes of conditioned Galton-Watson trees

Abstract: Let $\alpha$ be a fixed number. For any tree $T$, define $$F(T) := \sum |T_v|^\alpha,$$ summing over all fringe trees of $T$. Such sums have been studied by several authors, for several models of random trees. Today I let $T$ be a conditioned Galton-Watson tree, where the critical offspring distribution has finite variance. For real $\alpha$, there are three different phases: $\alpha$ in $(-\infty,0)$, $(0,1/2)$, and $(1/2,\infty)$. We consider also complex $\alpha$, which is useful since it enables us to use properties of analytic functions in some proofs; moreover, it yields new results and problems. We use several methods, including Aldous's convergence to Brownian excursion to obtain convergence in distribution, and singularity analysis of generating functions to obtain moment asymptotics. (Joint work with Jim Fill.)

11 February, 2021

Details: Cecilia Holmgren, Uppsala University - Online, 10:15 - 11:15
Title: Split trees -- A unifying model for many important random trees of logarithmic height

Abstract: Split trees were introduced by Devroye (1998) as a novel approach for unifying many important random trees of logarithmic height. They are interesting not least because of their usefulness as models of sorting algorithms in computer science; for instance  the well-known Quicksort algorithm (introduced by Hoare [1960]) can be depicted as a binary search tree (which is one example of a split tree). In 2012, I introduced renewal theory as a novel approach for studying split trees*. This approach has proved to be highly useful for investigating such trees and has allowed us to show several general results valid for all split trees. In my presentation, I will introduce split trees and illustrate some of our results for this large class of random trees, e.g. on the size, total path length, number of cuttings and number of inversions as well as on the size of the giant component after bond percolation.

* Holmgren C., Novel characteristic of split trees by use of renewal theory. Electronic Journal of Probability 2012.

28 January, 2021

Details: Stephan Wagner, Uppsala University - Online, 10:15 - 11:15
Title: The mean subtree order of trees

Abstract: By a subtree of a tree T, we mean any nonempty induced subgraph that is connected and thus again a tree. The study of the average number of vertices in a subtree, which is called the mean subtree order, goes back to Jamison's work in the 1980s. His first paper on the topic concludes with six open problems. The first of these was resolved in 2010, and over the past decade, further progress was made so that only one of them remains open today. In my talk, I will mainly focus on recent joint work with Stijn Cambie and Hua Wang on the elusive remaining conjecture, which states that for every number of vertices, the tree with greatest mean subtree order must be a caterpillar.

14 January, 2021

Presentation of the master thesis of Bernat Sopena Gilboy
Details: Uppsala University - Online, 10:15 - 11:15
Title: Random planar graphs

Abstract: The counting problem (i.e. given a combinatorial class, how many possible objects of size n are there) is introduced. In the first part an overview of combinatorial classes, generating functions, the symbolic method as well as results on coefficient asymptotics are presented. Examples are given and a general counting problem with a functional equation of the type y = F(x,y)  is solved to provide context for the methods. The rest of the talk is spent on solving the counting problem for simple labelled planar graphs (Giménez & Noy, 2009). To this end we review results obtained on 3-connected planar maps (Mullin & Schellenberg, 1968) and labelled 2-connected planar graphs (Walsh 1982; Bender,  Gao & Wormald 2002).

2020

17 December, 2020

Details: Eleanor Archer, Tel-Aviv University - Online, 10:15 - 11:15
Title: Random walks on decorated Galton-Watson trees

Abstract: Random trees are the building blocks for a range of probabilistic structures, including percolation clusters on the lattice and a range of statistical physics models on random planar maps. In this talk we consider a random walk on a critical "decorated" Galton-Watson tree, by which we mean that we first sample a critical Galton-Watson tree T, replace each vertex of degree n with an independent copy of a graph G(n), and then glue these inserted graphs along the tree structure of T. We will determine the random walk exponents for this decorated tree model in terms of the exponents for the underlying tree and the exponents for the inserted graphs. We will see that the model undergoes several phase transitions depending on how these exponents balance out.

10 December, 2020

Details: Benedikt Stufler, Vienna University of Technology - Online, 10:15 - 11:15
Title: Cutvertices in random planar maps

Abstract: We study the number of cutvertices in a random planar map as the number of edges tends to infinity. Interestingly, the combinatorics behind this seemingly simple problem are quite involved. This is joint work with Marc Noy and Michael Drmota.

03 December, 2020

Details: Vasiliki Velona, Universitat Pompeu Fabra and Universitat Politècnica de Catalunya - Online, 10:15 - 11:15
Title: Broadcasting on random recursive trees

Abstract:
Consider a random recursive tree, whose root vertex has a random bit value assigned. Every other vertex has the same bit value as its parent with probability 1 − q and the opposite value with probability q, where q is in [0, 1]. The broadcasting problem consists in estimating the value of the root bit upon observing the unlabeled tree, together with the bit value associated with every vertex. In a more difficult version of the problem, the unlabeled tree is observed but only the bit values of the leaves are observed. When the underlying tree is a uniform random recursive tree, in both variants of the problem it is possible to characterize the values of q for which the optimal reconstruction method has a probability of error bounded away from 1/2. Moreover, we find that the probability of error is bounded by a constant times q. Two simple reconstruction rules that are considered is the simple majority vote and the bit value of the centroid vertex of the tree. Most results are extended to linear preferential attachment trees as well. The results to be presented in this talk are joint work with Louigi Addario-Berry, Luc Devroye, Gábor Lugosi. 

26 November, 2020

Details: Svante Janson, Uppsala University - Online, 10:15 - 11:15
Title: On general subtrees of a conditioned Galton-Watson tree

Abstract: We show that the number of copies of a given rooted tree in
a conditioned Galton-Watson tree satisfies a law of large numbers under a
minimal moment condition on the offspring distribution. Based on arXiv:2011.04224.

12 November, 2020

Details: Fiona Skerman, Uppsala University - Online, 10:15 - 11:15
Title: Edge-sampling and modularity

Abstract: We analyse when community structure of an underlying graph can be determined from an observed subset of the graph. In a natural model where we suppose edges in an underlying graph G appear independently with some probability in our observed graph G' we describe how high a sampling probability we need to infer the modularity of the underlying graph. Modularity is a function on graphs which is used in algorithms for community detection. For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The (max) modularity q*(G) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q*(G) ≤ 1. In the seminar I will spend time on intuition for the behaviour of modularity, how it can be approximated, links to other graph parameters and to present some conjectures and open problems. Joint work with Colin McDiarmid.

5 November, 2020

Details: Xing Shi Cai, Uppsala University - Online, 17:15 - 18:15
Title: Minimum stationary values of sparse random directed graphs

Abstract: We consider the stationary distribution of the simple random walk on the directed configuration model with bounded degrees. Provided that the minimum out-degree is at least 2, with high probability (whp) there is a unique stationary distribution. We show that the minimum positive stationary value is whp n^−(1+C+o(1)) for some constant C≥0 determined by the degree distribution. In particular, C is the competing combination of two factors: (1) the contribution of atypically "thin" in-neighbourhoods, controlled by subcritical branching processes; and (2) the contribution of atypically "light" trajectories, controlled by large deviation rate functions. Additionally, our proof implies that whp the hitting and the cover time are both n^(1+C+o(1)). Our results complement those of Caputo and Quattropani who showed that if the minimum in-degree is at least 2, stationary values have logarithmic fluctuations around n−1.

29 October, 2020

Details: Sergey Dovgal, University of Bordeaux - Online, 17:15 - 18:15
Title: The birth of the strong components

Abstract: It is known that random directed graphs D(n,p) undergo a phase transition around the point p = 1/n. Moreover, the width n^{-4/3} of the transition window has been known since the works of Luczak and Seierstad. In particular, they have established that as n → ∞ when p = (1 + μn^{-1/3})/n, the asymptotic probability that the strongly connected components of a random directed graph are only cycles and single vertices decreases from 1 to 0 as μ goes from −∞ to ∞. By using techniques from analytic combinatorics, we establish the exact limiting value of this probability as a function of μ and provide more statistical insights into the structure of a random digraph around, below and above its transition point. We obtain the limiting probability that a random digraph is acyclic and the probability that it has one strongly connected complex component with a given difference between the number of edges and vertices (called excess). Our result can be extended to the case of several complex components with given excesses as well in the whole range of sparse digraphs. Our study is based on a general symbolic method which can deal with a great variety of possible digraph families, and a version of the saddle-point method which can be systematically applied to the complex contour integrals appearing from the symbolic method. While the technically easiest model is the model of random multidigraphs, in which multiple edges are allowed, and where edge multiplicities are sampled independently according to a Poisson distribution with a fixed parameter p, we also show how to systematically approach the family of simple digraphs, where multiple edges are forbidden, and where 2-cycles are either allowed or not. Our theoretical predictions are supported by numerical simulations when the number of vertices is finite, and we provide tables of numerical values for the integrals of Airy functions that appear in this study. Joint work with Élie de Panafieu, Dimbinaina Ralaivaosaona, Vonjy Rasendrahasina, and Stephan Wagner.

8 October, 2020

Details: Clément Requilé, Uppsala University, Ångström 4006, 17:15 - 18:15
Title: Random planar graphs

Abstract: A graph is labelled when its vertex set is {1,...,n}, and planar when it admits an embedding on the sphere. A random (labelled) planar graph is a graph chosen uniformly among all planar graphs on n vertices. We would like to study its properties as n goes to infinity. However, the planarity constraint makes it difficult to mimic the classical methods used in the study of the Erdős-Rényi random graph. An alternative is to rely on asymptotic enumeration via generating functions and analytic combinatorics. The starting point is a decomposition of graphs according to their connected components developed by Tutte in the 60's to study planar maps (fixed embeddings of planar graphs), and which can be extended to encode parameters of interest. In this talk I will present several results about some families of planar graphs, in particular in the cubic (3-regular), 4-regular, and bipartite cases. We will discuss the behaviour of various parameters in the random setting and explain how some of them can be encoded via the Ising and Potts models. If time permits, I will also try to highlight some limitations of this method and where can a more probabilistic viewpoint hopefully help.

1 October, 2020

Details: Paul Thévenin, Uppsala University, Ångström 4006, 17:15 - 18:15
Title: Random trees, laminations and factorizations

Abstract: A minimal factorization of the n-cycle is a way of seeing the cycle (1 2 3 ... n) (sending 1 to 2, 2 to 3, ..., n to 1) as a product of (n-1) transpositions. By coding each of these transpositions by a chord in the unit disk, one sees a uniform minimal factorization as a random process of laminations, which are sets of noncrossing chords in the disk. In this talk, I will discuss the convergence of this process, and highlight various connections between this model, a family of random trees and fragmentation processes. If time allows, I will also present some possible generalizations of these results to other models of factorizations.

24 September, 2020

Details: Baptiste LoufUppsala University, Ångström 4006, 17:15 - 18:15
Title: The geometry of high genus maps

Abstract: A map is the result of polygons glued together to form a (compact, connected, oriented) surface. Alternatively, one can think of it as a graph embedded in a surface. Just like graphs, maps are a good model of discrete geometry, and it can be interesting to study their properties, especially when considering random maps whose size goes to infinity. In this talk I will present some results about high genus maps. The genus of a map is the number of handles of the surface it lives on (for instance, a sphere has genus 0 and a torus has genus 1), and high genus maps are defined as (sequences of) uniform random maps whose size and genus go to infinity at the same time. There won’t be any proof or other technical details, but I will present a bunch of open problems and conjectures.

The talks from 2020-04-02 to 2020-05-28 were cancelled due to the Covid-19 pandemic.

28 May, 2020

Details: Alexander Watson, University College London, Ångström 64119, 10:15 - 11:15 am

14 May, 2020

Details: Benjamin Dadoun, University of Bath, Ångström 64119, 10:15 - 11:15 am

7 May, 2020

Details: Gerardo Barrera Vargas, University of Helsinki, Ångström 64119, 10:15 - 11:15 am

16 April, 2020

Details: Quan Shi, Universität Mannheim, Ångström 64119, 10:15 - 11:15 am

2 April, 2020

Details: Robin Stephenson, University of Sheffield, Ångström 64119, 10:15 - 11:15 am

5 March, 2020

Details: Igor PakUniversity of California, UCLA, Ångström 64119, 10:15 - 11:15 am
Title: Sampling Contingency Tables

Abstract: Contingency tables are integer matrices with fixed row and column sums. Sampling them efficiently is a notoriously challenging problem both in both theory and practice, of great interest in both theoretical and the real world statistics. Roughly speaking, random sampling of contingency tables allows one to measure the empirical correlation between discrete random variables, always a good thing to have.

I will first give a brief overview of the existing approaches (Fisher-Yates sampling, sequential sampling, the Diaconis-Gangolli MCMC algorithm and the algebraic statistic tools). I will then describe a new MCMC sampling algorithm based on combinatorial and group theoretic ideas. Many examples will follow which will illustrate the surprising power of our algorithm both in two and higher dimensions. If time permits, I will mention the theory behind our work and some potential generalizations we are thinking about.

Joint work with Sam Dittmer.

27 February, 2020

Details: Stephan Wagner, Uppsala University, Ångström 64119, 10:15 - 11:15 am
Title: On the Collection of Fringe Subtrees in Random Binary Trees

Abstract: A fringe subtree of a rooted tree is a subtree consisting of one of the nodes and all its descendants. In this talk, we are specifically interested in the number of non-isomorphic trees that appear in the collection of all fringe subtrees of a binary tree. This number is analysed under two different random models: uniformly random binary trees and random binary search trees.

20 February, 2020

Details: Svante Janson, Uppsala University, Ångström 64119, 10:15 - 11:15 am
Title: Central limit theorems for additive functionals and fringe trees in tries

Abstract: We prove central limit theorems for additive functionals of tries, undersuitable conditions.  Several methods are used and combined; these include: 
Poissonization (introducing more independence);
approximation with a sum of independent terms (coming from disjoint subtrees);
dePoissonization using a conditional limit theorem;
moment asymptotics by renewal theory.

As examples, we consider some properties of fringe trees.

13 February, 2020

Details: Ilse Fischer, Universität Wien, Ångström 64119, 10:15 - 11:15 am
Title: Bijective proofs of skew Schur polynomial factorizations

Abstract: Schur polynomials and their generalizations appear in various differentcontexts. They are the irreducible characters of polynomial representations of the general linear group and an important basis of the space of symmetric functions. They are accessible from a combinatorial point of view as they are multivariate generating functions of semistandard tableaux associated with a fixed integer partition. Recently, Ayyer and Behrend discovered for a wide class ofpartitions factorizations of Schur polynomials with an even number of variables where half of the variables are the reciprocals of the others into symplectic and/or orthogonal group characters, thereby generalizing results of Ciucu and Krattenthaler for rectangular shapes. We present bijective proofs of such identities. Our proofs involve also what we call a ``randomized'' bijection. No prior knowledge on group characters and Schur polynomials is necessary. Joint work with Arvind Ayyer.

6 February, 2020

Details: Tony JohanssonStocholms Universitet, Ångström 64119, 10:15 - 11:15 am
Title: Finding Hamilton cycles in fixed-degree random graphs

Abstract: The fixed degree sequence random graph is obtained by fixing a sequence of n integers, then drawing a graph on n vertices uniformly at random from the set of graphs with the prescribed sequence as its degree sequence. We consider the problem of finding a Hamilton cycle in this graph.

If all degrees are equal to d we obtain the random regular graph, known to be Hamiltonian with high probability when d is at least 3. Otherwise not much is known; what if half the degrees are 3 and half are 4? Half 3 and half 1000? It is easy to come up with degree sequences which do not give Hamilton cycles, and we want to be able to determine which ones do and which ones don't.

I don't fully solve the problem, but I derive a graph condition which is essentially necessary and sufficient for Hamilton cycles in this class of random graphs. It remains open to determine for which degree sequences this condition holds.

23 January, 2020

Details: Pasha TkachovGran Sasso Science Institute, Ångström 64119, 10:15 - 11:15 am
Title: On stability of traveling wave solutions for integro-differential equations related to branching Markov processes

Abstract: The aim of the talk is to present results on stability of traveling waves for integro-differential equations connected with branching Markov processes. In other words, the limiting law of the left-most particle of a time-continuous branching Markov process with a Lévy non-branching part is shown. In particular, Bramson's correction is obtained. The key idea is to approximate the branching Markov process by a branching random walk and apply the result of Aïdékon on the limiting law of the latter one.

10 January, 2020 

Details: Laura Eslava, National Autonomous University of Mexico, Ångström 64119, 10:15 - 11:15 am
Title: Branching processes with merges and locality of hypercube’s critical percolation

Abstract: We define a branching process to understand the locality of the critical percolation in the hypercube; that is, whether the local structure of the hypercube has an effect on the critical percolation as a function of the dimension of the hypercube. The branching process mimics the local behavior of an exploration of a percolated hypercube; it is defined recursively as follows. Start with a single individual in generation 0. On an first stage, each individual has independent Poisson offspring with mean (1+p)(1-q)^k where k depends on the ancestry of the individual;  on the merger stage, each pair of cousins merges with probability q.

There is a threshold function q_c=q_c(p) for extinction of the branching process. When p is sufficiently small, the first order terms of q_c coincide with those of the critical percolation for the hypercube, suggesting that percolation in the hypercube is dictated by its local structure. This is work in progress with Sarah Penington and Fiona Skerman.

Last modified: 2021-04-01