Seminar series in Probability and Combinatorics

You are welcome to participate in our seminars where our own and invited researchers talk about their research. The seminars usually takes place on Thursdays every or every two weeks at 10:15 - 11:15. 

Contact: Tiffany Lo and Paul Thévenin

Upcoming seminars

Previous seminars in Probability and Combinatorics

2022

Counting combinatorial 3-spheres using Shannon entropy

  • Date: 1 December, 10:15–11:15
  • Lecturer: Joel Danielsson, Lund University

Abstract: How many combinatorial d-spheres are there with m facets? That is, how many simplicial complexes with m maximal faces are there whose geometric realizations are homeomorphic to the unit sphere in Euclidean (d+1)-space? 
While this has been solved for d=1 (cycle graphs) and for d=2 (triangulations of the 2-sphere), it is still an open problem for d≥3. We prove an upper bound on the number of 3-spheres, by estimating the entropy of a sphere picked uniformly at random. For this we use a corollary of Shannon’s noiseless encoding theorem from a recent paper by Palmer & Pálvölgyi. 

Sparse Random Graphs with Many Triangles

  • Date: 17 November, 10:15
  • Lecturer: Suman Chakraborty, Uppsala University

Abstract: It is well known that sparse random graphs (where the number of edges is of the order of the number of vertices) contain only a small number of triangles. On the other hand, many networks observed in real life are sparse but contain a large number of triangles. Motivated by this discrepancy we ask the following two questions: How (un)likely is it that a sparse random graph contains a large number of triangles? What does the graph look like when it contains a large number of triangles? We also ask a related question: What is the probability that in a sparse random graph a large number of vertices are part of some triangle? We discuss these questions, as well as some applications to exponential random graph models.

Joint work with Remco van der Hofstad and Frank den Hollander.

Uncovering a graph

  • Date: 10 November, 10:15
  • Lecturer: Svante Janson

Abstract: Let G be a graph, deterministic or random, and uncover its vertices one by one, in uniformly random order. This yields a growing sequence of (random) induced subgraphs of G, and we study the evolution of this sequence. More precisely, we study only the evolution of the number of edges in these subgraphs. 
This question (among others) was studied by Hackl, Panholzer and Wagner (AofA 2022) for the case when $G$ is a uniformly random labelled tree. They showed that the stochastic process given by the number of visible edges, after suitable rescaling, converges to a continuous Gaussian process, which resembles a Brownian bridge but with a somewhat different distribution. (The proof uses an exact formula for a multivariate generating function.) Our main result is that this result extends to a wide class of deterministic and random trees and graphs. 
The problem can be seen as dual to the random graph process introduced by Erdös and Renyi, where the edges of a complete graph are uncovered in random order. Our proof uses an adaption of a method introduced for that problem (Janson 1990, 1994). 

Stein’s method for exponential random graph models and assessing goodness of fit

  • Date: 3 November, 10:15 
  • Lecturer: Gesine Reinert, Oxford University

Abstract: Exponential random graph models are a key tool in network analysis but due to an intractable normalising constant are difficult to manipulate. In this talk we shall use Stein's method to approximate these models by Bernoulli random graphs in ``high temperature" regimes. 
For assessing the goodness of fit of a model, often independent replicas are assumed. When the data are given in the form of a network, usually there is only one network available. If the data are hypothesised to come from an exponential random graph model, the likelihood cannot be calculated explicitly. Using a Stein operator for these models we introduce a kernelized goodness of fit test and illustrate its performance. 
Finally, we extend the ideas of this goodness of fit test to provide an approximate goodness of fit test for potentially black-box graph generators. 
This talk is based on joint work with Nathan Ross and with Wenkai Xu. 

Friend of a friend models of network growth

  • Date: 26 October
  • Lecturer: Watson Levens, University of Dar es Salaam and Uppsala University

Abstract: A model for a friend of a friend network growth is based on the idea that individuals joining the social network choose one individual at random and link to her with probability p, then they choose a friend of that person and link with probability q. The model is more general and conceptually simple, yet it produces power-law degree distributions, small world clustering and super-hub networks with non-stationary degree distributions. 
I will discuss a general framework for analysing a friend of a friend models of network growth and look at some special cases which produce scale-free and super-hubs networks. I will then discuss the general results of the models and show examples of misleading claims about how some cases of models similar to the friend of a friend models can be used as a form of local mechanism for motivating preferential attachment. 
Finally, I will mention some results about the early evolution of 2018/2019 Tanzania Twitter and compare it with the 2012 Twitter networks of USA, Brazil and Japan. 
The talk is based on some recent studies by Watson Levens, David J. T. Sumpter and Alex Szorkovszky. 

Is it easier to count communities than to find them?

  • Date: 20 October, 10:15
  • Lecturer: Fiona Skerman, Uppsala University

Abstract: 
We study the planted-dense-subgraph model where an Erdős–Rényi base graph is augmented by adding one or more `communities' - subsets of vertices with a higher-than-average connection probability between them. The detection problem is to distinguish between the vanilla Erdős–Rényi model and that with one or many planted communities and the recovery problem is to approximately recover the position of the community structure within the graph. A detection-recovery gap is known to occur, for some parameter combinations (sizes of structure, edge probabilities), we have fast algorithms to perform detection but recovery is not possible. We investigate something in-between: we want to infer some property of the community structure without needing to recover it. We say counting is the problem of distinguishing a single community from many. Our result is to show counting is no easier than detection. 
The combinatorics at play: let a=(a_H)_H and b=(b_H)_H be two sequences, indexed by graphs. We define a graph sequence r by setting the empty graph to have r-value 1, and via the following recursion r_G = a_G - \sum_H b_H r_{G\H} where the sum is over all non-empty subgraphs of G. Central to our proof is to show that the sequence r inherits properties of the sequences a and b. Loosely, in our context the sequence a (resp. b) encodes information of the probability space with many communities (resp. one community) and whether one can distinguish these two probability spaces is characterised by the value of the sum of squares of the r-values. Joint work with Cindy Rush, Alex Wein and Dana Yang.

Fragmentation of trees and drifted excursions

  • Date: 13 October, 10:15
  • Lecturer: Paul Thévenin, Uppsala University

Abstract: The fragmentation of a tree is a process which consists in cutting the tree at random points, thus splitting it into smaller connected components as time passes. In the case of the so-called Brownian tree, it turns out that the sizes of these subtrees, known as the Aldous-Pitman fragmentation process, have the same distribution as the lengths of the excursions over its current infimum of a linearly drifted Brownian excursion, as proved by Bertoin. We provide a natural coupling between these two objects. To this end, we make use of the so-called cut-tree of the Brownian tree, which can be seen as the genealogical tree of the fragmentation process. Joint work with Igor Kortchemski. 

Extremal trees with fixed degree sequence

  • Lecturer: Eric Andriantiana (Rhodes University)
  • Date: 6 October, 10:15

Abstract: Joint work with Valisoa Razanajatovo Misanantenaina and Stephan G. Wagner. The so-called greedy tree G(D) and alternating greedy tree M(D) are known to be extremal graphs among elements of the set T_D of trees with degree sequence D, with respect to various graph invariants. This talk will discuss a generalized proof that covers a larger family of invariants for which G(D) or M(D) is an extremal graph in T_D. The result implies known results on the Wiener index, the number of subtrees, the number of independent subsets, the Hosoya index, the terminal Wiener index, and the energy of graphs. Furthermore, new results on the number of rooted spanning forests, the incidence energy and the solvability of a graph also follow. By comparing greedy trees, and alternating greedy trees, with different degree sequences, the results in T_D are extended to the set of trees whose degree sequences are majorized by D. 

Some topics on random graphs

  • Lecturer: Tiffany Lo (Uppsala University)
  • 22 September

Abstract: We consider the preferential attachment (PA) tree with additive fitness and the duplication divergence (DD) random graph. In particular, we discuss the construction of the local weak limit of the PA tree, and study the expected degree distribution of the DD graph using a certain type of birth-catastrophe process. The work on the DD random graph is joint with A.D. Barbour.

2021

16 December, 2021

Details: Benny Avelin,  Uppsala University  - Seminarierum of Ångström, Hus 6, Rum 64119, 10:15 - 11:15                                                                                                                         Title: Universal approximation and regularity of periodic neural networks

Abstract: In this talk, I will focus on the approximation of functions of Bounded Variation (BV) using periodic neural networks. I will present a calculus of variations approach to the regularity and localization of the approximation problem.

9 December, 2021

Details: Gabriel Lipnik,  Graz University of Technology  - Online, 10:15 - 11:15                                                                                                                                     Title: Fragmentation Process derived from $\alpha$-stable Galton-Watson trees

Abstract: Many well-known combinatorial sequences satisfy some sort of recurrence
relations. In this talk, we discuss a special class of such sequences,
so-called q-recursive sequences. For an integer q at least 2, a q-recursive
sequence is defined by recurrence relations on subsequences of indices modulo
some fixed power of q. Precise asymptotic results for these sequences are obtained
via a detour to q-regular sequences in the sense of Allouche and Shallit. It turns out that many combinatorial sequences are in fact q-recursive. We conclude the talk by studying some specific q-recursive sequences in detail. This is joint work with Clemens Heuberger and Daniel Krenn.

Recorded: https://media.medfarm.uu.se/play/kanal/920/video/14791

25 November, 2021

Details: Colin Desmarais,  Uppsala University  - Seminarierum of Ångström, Hus 6, Rum 64119, 10:15 - 11:15                                                                                                                      Title: Broadcasting induced colourings of preferential attachment trees

Abstract: A random recursive tree is a rooted tree constructed by successively choosing a vertex uniformly at random and adding a child to the selected vertex. A random preferential attachment tree is grown in a similar manner, but the vertex selection is made proportional to a linear function of the number of children of a vertex. Preferential attachment trees are the tree version of the Barabasi-Albert preferential attachment model. We consider a red-blue colouring of the vertices of preferential attachment trees, which we call a broadcasting induced colouring: the root is either red or blue with equal probability, while for a fixed value p between 0 and 1, every other vertex is assigned the same colour as its parent with probability p and the other colour otherwise. In this talk I will discuss properties of preferential attachment trees with broadcasting induced colourings, including limit laws for the number of vertices, clusters (maximal monochromatic subtrees) and leaves of each colour. The main focus of the talk will be on the size of the root cluster, that is, the maximal monochromatic subtree containing the root. Joint work with Cecilia Holmgren and Stephan Wagner.

Recorded: https://media.medfarm.uu.se/play/kanal/920/video/14732

18 November, 2021

Details: Open problem session  - Seminarierum of Ångström, Hus 6, Rum 64119, 10:15 - 11:15                                                                                                                     

4 November, 2021

Details: Annika Heckel,  University of Munich  - Seminarierum of Ångström, Hus 6, Rum 64119, 10:15 - 11:15                                                                                                                      Title: How does the chromatic number of a random graph vary?

Abstract: How much does the chromatic number of the random graph G(n, 1/2) vary? A classic result of Shamir and Spencer shows that it is contained in some sequence of intervals of length about n^(1/2). Until recently, however, no non-trivial lower bounds on the fluctuations of the chromatic number of a random graph were known, even though the question was raised by Bollobás many years ago. I will talk about the main ideas needed to prove that, at least for infinitely many n, the chromatic number of G(n, 1/2) is not concentrated on fewer than n^(1/2-o(1)) consecutive values. I will also discuss the Zigzag Conjecture, made recently by Bollobás, Heckel, Morris, Panagiotou, Riordan and Smith: this proposes that the correct concentration interval length 'zigzags' between n^(1/4+o(1)) and n^(1/2+o(1)), depending on n. Joint work with Oliver Riordan.

Recorded: https://media.medfarm.uu.se/play/kanal/920/video/14666

28 October, 2021

Details: Gabriel Berzunza-Ojeda,  University of Liverpool  - Online, 10:15 - 11:15                                                                                                                                     Title: Fragmentation Process derived from $\alpha$-stable Galton-Watson trees

Abstract: Aldous, Evans and Pitman (1998) studied the behavior of the fragmentation process derived from deleting the edges of a uniform random tree on n labelled vertices. In particular, they showed that, after proper rescaling, the above fragmentation process converges as n -> \infty to the fragmentation process of the Brownian CRT obtained by cutting-down the Brownian CRT along its skeleton in a Poisson manner. In this talk, we will discuss the fragmentation process obtained by deleting randomly chosen edges from a critical Galton-Watson tree t_n conditioned on having n vertices, whose offspring distribution belongs to the domain of attraction of a stable law of index \alpha in (1,2]. The main result establishes that, after rescaling, the fragmentation process of t_n converges, as n -> \infty, to the fragmentation process obtained by cutting-down proportional to the length on the skeleton of an \alpha-stable Lévy tree. We will also explain how one can construct the latter by considering the partitions of the unit interval induced by the normalized \alpha-stable Lévy excursion with a deterministic drift. In particular, the above extends the result of Bertoin (2000) on the fragmentation process of the Brownian CRT. The approach uses the Prim's algorithm (or Prim-Jarník algorithm) to define a consistent exploration process that encodes the fragmentation process of t_n. We will discuss the key ideas of the proof. Joint work with Cecilia Holmgren (Uppsala University)

Recorded: https://media.medfarm.uu.se/play/kanal/920/video/14658

21 October, 2021

Details: Baptiste Louf & Paul Thévenin, Uppsala University - Seminarierum of Ångström, Hus 6, Rum 64119, 10:15 - 11:15                                                                                              Title: Asymptotic behaviour of a factorization of fixed genus of the n-cycle

Abstract: A factorization of the n-cycle is a way of writing the cycle (1, 2, ..., n) as a product of transpositions. It is well-known that the minimal number of transpositions in a factorization of the n-cycle est n-1. More generally, a factorisation as a product of n-1+2g transpositions is called factorisation of genus g. We will expose a bijection between the factorizations of the n-cycle and a set of graphs with n vertices, as well as an algorithm inspired by this bijection and sampling an asymptotically uniform factorization of fixed genus. We will also show how this algorithm allows us to describe the scaling limit of a uniform factorization of given genus. Joint work with Valentin Féray.

Recorded: https://media.medfarm.uu.se/play/kanal/920/video/14641

14 October, 2021

Details: Cyril Marzouk, Ecole Polytechnique - Online, 10:15 - 11:15                                   Title: On the geometry of biconditioned random trees

Abstract: We consider simply generated random plane trees with n vertices and k_n leaves, sampled from a sequence of weights. Motivated by questions on random planar maps, we will focus on the asymptotic behaviour of the largest degree. Precisely we will give conditions on both the number of leaves and the weight sequence that ensure the convergence in distribution of the associated Lukasiewicz path (or depth-first walk) to the Brownian excursion. This should also provide a first step towards the convergence of their height of contour function. The proof scheme is to reduce step by step to simpler and simpler objects and we will discuss excursion and bridge paths, non decreasing paths conditioned by their tip, and finally estimates of the form of the local limit theorem which may be of independent interest.

Recorded: https://media.medfarm.uu.se/play/kanal/920/video/14640

7 October, 2021

Details: Benjamin Hackl, Uppsala University - Ångström 4006, 10:15 - 11:15
Title:  Hands-On Workshop: Mathematical Animations with Manim

Abstract: Manim [1] is an open source Python framework for visualizing mathematical concepts and ideas in animated videos. Originally, the library was created by Grant "3Blue1Brown" Sanderson, whose Manim-produced YouTube videos [2] get millions of clicks and are a driving force contributing to the popularization of Mathematics. To battle the usual shortcomings of large one-person software projects (unstable interface, little to no documentation), a small community has formed that is actively maintaining, cleaning and continuously improving Manim [3]. We will explore the framework's basic functionalities by creating a series of short (but cool!) animations, and learn about further references. The talk / workshop will be interactive, you are encouraged to bring your own device and work along; all you need is a working internet connection.

[1] https://www.manim.community                                                                                                [2] https://www.youtube.com/3blue1brown                                                                                [3] https://github.com/ManimCommunity/manim

Recorded: https://media.medfarm.uu.se/play/kanal/920/video/14642

30 September, 2021

Details: Svante Janson, Uppsala University - Online, 10:15 - 11:15                                   Title: Asymptotic normality for m-dependent and constrained U-statistics, with applications to pattern matching in random strings and permutations

Abstract: We study U-statistics based on a stationary sequence of m-dependent variables, and constrained U-statistics with some restrictions on the gaps between indices. A law of large numbers and a central limit theorem are extended from the standard case to this setting. The results are motivated by applications to pattern matching in random strings and permutations. We obtain both new results and new proofs of old results.

10 June, 2021

Details: Michael Missethan, Graz University of Technology - Online, 10:15 - 11:15
Title:  Random planar graphs

Abstract: In this talk we consider random planar graphs with a fixed 
number of vertices and edges. We will discuss recent results on 
longest and shortest cycles, the two-point concentration of the 
maximum degree, and the Benjamini-Schramm local limit in such a random 
planar graph and will compare them to related classical results in the 
Erdős-Rényi random graph. This talk is based on joint work with Mihyun 
Kang.

20 May, 2021

Details: Benjamin Hackl, Uppsala Universitet - Online, 10:15 - 11:15
Title: Combinatorial aspects of flip-sorting and pop-stacked permutations

Abstract: Flip-sorting describes the process of sorting a permutation by iteratively reversing (``flipping'') all of its maximal descending consecutive subsequences (``falls''). The combinatorial structure induced by this procedure can be illustrated by the associated sorting tree: a graph whose vertices are permutations, and where an edge between two permutations models that one results from the other after flipping its falls.

In this talk, we will first make sure that flip-sorting is actually a sorting procedure (and hence the sorting tree is actually a tree rooted at the identity permutation), and then explore the surprisingly rich structure of the tree in order to identify which permutations are very close to or very far away from the root.

22 Avril, 2021

Details: Guillem Perarnau, Universitat Politècnica de Catalunya - Online, 10:15 - 11:15
Title: Rankings in directed random graphs
 

Abstract: In this talk we will consider the extremal values of the stationary distribution of the sparse directed configuration model. Under the assumption of linear $(2+\eta)$-moments on the in-degrees and of bounded out-degrees, we obtain tight comparisons between the maximum value of the stationary distribution and the maximum in-degree. Under the further assumption that the order statistics of the in-degrees have power-law behavior, we show that the extremal values of the stationary distribution also have power-law behavior with the same index. Moreover, these results extend to the PageRank scores of the model, thus confirming a version of the so-called power-law hypothesis. Joint work with Xing Shi Cai, Pietro Caputo and Matteo Quattropani.

15 April, 2021

Details: Sarai Hernandez-Torres, Technion - Online, 10:15 - 11:15
Title: Chase-escape with death

Abstract: Chase-escape is a competitive growth process in which red particles spread to adjacent uncolored sites while blue particles overtake adjacent red particles. We can think of this model as rabbits escaping from wolves pursuing them on an infinite graph. There are two phases for chase-escape. If the rabbits spread fast enough, then both species coexist at all times. Otherwise, the wolves eat all the rabbits in a finite time, and we have extinction. This talk presents a variation of chase-escape where each rabbit has a random lifespan, after which it dies. This process is chase-escape with death, and we will study it on d-ary trees. Chase-escape with death exhibits a new phase where death benefits the survival of the rabbit population. We will understand the phase transitions of this process through a connection between probability and analytic combinatorics. This talk is joint work with Erin Beckman, Keisha Cook, Nicole Eikmeier, and Matthew Junge.

8 April, 2021

Details: Noela Müller, Ludwig Maximilians Universität München - Online, 10:15 - 11:15
Title: Belief Propagation on the random k-SAT model

Abstract: Corroborating a prediction from statistical physics, we prove that the Belief Propagation message passing algorithm approximates the partition function of the random k-SAT model well for all clause/variable densities and all inverse temperatures for which a modest absence of long-range correlations condition is satisfied. This condition is known as “replica symmetry” in physics language. From this result we deduce that a replica symmetry breaking phase transition occurs in the random k-SAT model at low temperature for clause/variable densities below but close to the
satisfiability threshold.
This is joint work with Amin Coja-Oghlan and Jean Bernoulli Ravelomanana.

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: 2022-12-15