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

Upcoming seminars

Previous seminars

2024

Game connectivity and adaptive dynamics

Date: 30 May 2024, 1015-1115
Lecturer: Tom Johnston (Bristol University, UK)

Abstract: We consider a generic game where there are $n$ players who can each be in one of $k$ states and at each time step the players can choose to change their state based on the current states of the other players. It is known that there are no ``simple'' dynamics which converge to a pure Nash equilibrium in every generic game that has one, but are there a small number of difficult games or is it hard to converge in most of the games? One simple dynamic is the best response with inertia dynamic, in which case convergence is a question about the connectivity of the best-response graph. We will look at the connectivity of a random best-response graph and show that this simple dynamic converges to a pure Nash equilibrium in almost all generic games that have one. Based on joint work with Michael Savery, Alex Scott and Bassel Tarbush.

Persistent hubs in generalised preferential attachment trees

Date: 23 May 2024, 10:15–11:15
Lecturer: Tejas Iyer (Weierstrass Institute, Berlin)

Abstract: In a generalised preferential attachment tree, nodes arrive one at a time, and connect to existing nodes with probability proportional to a function of their degree, for some fixed function $f$. In such a process, a node is called a persistent hub if it becomes, and remains, the fixed node of maximal degree during the evolution of the process.
For a large class of generalised preferential attachment trees, we provide necessary and sufficient criteria for the emergence of a persistent hub, building on previous work by Dereich and Mörters; Galashin, and Banerjee and Bhamidi. In this talk, we explore some of the motivation behind this result, and some aspects of the proof.

Induced saturation problems for POSets

Date: 24 April 2024, 10:15–11:15
Lecturer: Maryam Sharifzadeh (Umeå University)

Abstract:I will talk about saturation type problems. These questions can be considered as a dual to Tur\'an type questions. The main focus would be on the induced saturation questions for POSets.

For a fixed poset $P$, a family $\mathcal F$ of subsets of $[n]$ is induced $P$-saturated if $\mathcal F$ does not contain an induced copy of $P$, but for every subset $S$ of $[n]$ such that $ S\not \in \mathcal F$, $P$ is an induced subposet of $\mathcal F \cup \{S\}$. I will mainly talk about some recent developments, proof techniques and some open questions.

Elephant random walks

Date: 18 April, 10:15–11:15
Lecturer: Allan Gut (Uppsala University)

Abstract for the seminar "Elephant random walks"

Uniform Turán density of hypergraphs

Date: 11 April, 10:15–11:15
Lecturer: Daniel Kráľ (Masaryk University, Brno)

Abstract: In the early 1980s, Erdős and Sós, initiated the study of the classical Turán problem with a uniformity condition: the uniform Turán density of a hypergraph H is the infimum over all d for which any sufficiently large hypergraph with the property that all its linear-size subhyperghraphs have density at least d contains H. In particular, they raise the questions of determining the uniform Turán densities of K_4^3, the complete 4-vertex 3-uniform hypergraph, and K_4^3-, the hypergraph K_4^3 with an edge removed. The latter question was solved only recently in [Israel J. Math. 211 (2016), 349–366] and [J. Eur. Math. Soc. 97 (2018), 77–97], while the former still remains open for almost 40 years. In this talk, we survey recent and some very recent results concerning the uniform Turán density of hypergraphs, in particular, we present constructions of 3-uniform hypergraphs with uniform Turán density equal to 1/27, 4/27, 1/4 and 8/27, which are all non-zero values for which a construction of a 3-uniform hypergraph is known.

The talk is based on results obtained jointly with (subsets of) Matija Bucić, Jacob W. Cooper, Frederik Garbe, Daniel Iľkovič, Filip Kučerák, Ander Lamaison, Samuel Mohr and David Munhá Correia.

Ramsey numbers of cycles versus general graphs

Date: 21 March, 10:15–11:15
Lecturer: John Haslegrave (Lancaster University)

Abstract: The Ramsey number R(F,H) is the smallest value of n such that, for every graph G on n vertices, either G contains a copy of F or its complement contains a copy of H. In general it is very difficult to get good bounds on Ramsey numbers. However, in cases where one of the graphs is sparse, it may be possible to determine the value exactly. Burr and Erdös defined F to be H-good whenever a specific lower-bound construction for R(F,H) gives the correct value. Burr proved for any graph H that sufficiently long cycles are H-good. Allen, Brightwell and Skokan conjectured that it is sufficient for the cycle to have length at least the product of the order and chromatic number of H.

Pokrovskiy and Sudakov previously showed that this conjecture is true if the order of H is sufficiently large in terms of its chromatic number (and the chromatic number is also sufficiently large). We prove a bound valid for any graph H, which gives a strengthening of the Allen-Brightwell-Skokan conjecture for all graphs with chromatic number at least some constant. This is joint work with Joseph Hyde (Victoria), Jaehoon Kim (KAIST) and Hong Liu (IBS).

Inference in low-rank networks: Information-theoretical limits and algorithms

Date: 14 March, 10:15–11:15
Lecturer: Alexandre Proutiere (KTH)

Abstract: We present recent results related to inference tasks in random networks with low-rank structure. Examples of such networks include the celebrated Stochastic Block Model (SBM) and its extensions (labeled and degree-corrected SBMs) as well as those arising in Reinforcement Learning with low-rank representation. We derive information-theoretical limits pertaining to the recovery of the network structure, and devise algorithms approaching these limits. Our results accommodate for the potential dependence in the way the data is gathered, and in particular handle scenarios where this is done by navigating in the network.

Joint work with Yassir Jedra (MIT), Junghyun Lee (KAIST), Stefan Stojanovic (KTH), and Seyoung Yun (KAIST)

Semirestricted Rock, Paper, Scissors

Date: 22 February, 10:15–11:15
Lecturer: Svante Janson (Uppsala University)

Abstract: A semirestricted variant of the well-known game Rock, Paper, Scissors (Swedish: Sten, sax, påse) was recently studied by Spiro et al (Electronic J. Comb. 30 (2023), #P4.32). They assume that two players R (restricted) and N (normal) agree to play 3n rounds, where R is restricted to use each of the three choices exactly n times each, while N can choose freely. Obviously, this gives an advantage to N. How large is the advantage?

The main result of Spiro et al is that the optimal strategy for R is the greedy strategy, playing each round as if it were the last. (I will not give the proof, and I cannot improve on this.) They also show that with optimal play, the expected net score of N is \Theta(\sqrt{n}). In the talk, I will show that with optimal play, the game can be regarded as a twice stopped random walk, and I will show that the expected score is asymptotic to c \sqrt{n}, where c = 3\sqrt{3}/(2\sqrt{\pi}}.

Non-parametric volatility estimation in SPDE driven by white-coloured noise

Date: 8 February, 10:15–11:15
Lecturer: Valentin Garino (Uppsala University)

Abstract: The term "Stochastic partial differential equations" (SPDE) refers to a class of partial differential equations perturbed by a random additional noise. Thus, they can be seen as a generalisation of the notion of stochastic differential equation driven by a Brownian motion.

From a theoretical standpoint, the study of SPDE is a very active topic of research which is currently going through major advances. In practice, SPDE are an important ingredient in the modeling of various physical phenomena.

In this talk, we are going to look at the statistical problem of estimating the volatility of an SPDE with known differential operator. This question has already been adressed in a few recent works, but only in a parametric setting (constant volatility). We are going to build an estimator to tackle the case where the volatility is an unknown function of the solution, as well as looking at a practical implementation of said estimator on simulated datas.

Electrical Networks and Their Probabilistic Interpretations

Date: 25 January, 10:15–11:15
Lecturer: Erik Jonsson (Uppsala University)

Abstract: I will talk about electrical concepts such as Electrical Networks, Voltage functions, Effective Resistances and how these concepts can be linked to, and interpreted as, probabilistic concepts such as Markov processes, hitting probabilities and escape probabilities. I will finish off by proving Pólya's theorem (which was famously referenced by Shizuo Kakutani with the quote "A drunk man always finds his way home, but a drunk bird may get lost forever.") using electrical arguments.

2023

Extending Stanley’s Nonnegativity Theorem

Date: 30 November 2023
Speaker: Katharina Jochemko (KTH)

Abstract: The Ehrhart polynomial of a lattice polytope counts the number of lattice points in positive integer dilates of the polytope. A fundamental theorem by Stanley states that the Ehrhart polynomial, expressed in a particular basis, has only nonnegative coefficients. In this talk, we present generalizations of this and related results to weighted integer point counting in rational polytopes where the weights are given by polynomial functions. In particular, we show that Stanley’s Nonnegativity Theorem extends to weights given by homogeneous polynomials decomposable as sums of products of linear forms that are nonnegative over the polytope. This is joint work with Esme Bajo, Robert Davis, Jesús de Loera, Alexey Garber, Sofía Garzón Mora and Josephine Yu.

Permutations with few inversions

Date: 23 November, 10:15–11:15
Lecturer: Anders Claesson (University of Iceland)

Abstract: We consider permutations of [n] with at most n inversions; this is what we mean by permutation with few inversions. In particular, we present a curious generating function for permutations of [n] with exactly n inversion. Furthermore, we consider permutations that in addition to having few inversions avoid some fixed pattern. We present a simple-sounding conjecture that if proved correct would lead to a new record for the upper bound of the Stanley-Wilf limit of the notoriously difficult pattern 1324.

Expected hitting time estimates on finite graphs

Date: 17 November, 10:15–11:15
Lecturer: Yuwen Wang (University of Innsbruck)

Abstract: The expected hitting time from vertex a to vertex b, H(a,b), is the expected value of the time it takes a random walk starting at a to reach b. In this talk, we shall discuss estimates for H(a,b) when the distance between a and b is comparable to the diameter of the graph, and the graph satisfies a Harnack condition. We show that, in such cases, H(a,b) can be estimated using a formula in terms of the volumes of balls around b. We give an outline of the proof using Green functions and heat kernel estimates. Using this result, we can then estimate H(a,b) on various graphs, such as rectangular tori, some convex traces on the integer lattice, and fractal graphs. Joint work with Laurent Saloff-Coste.

Fast and Accurate Algorithms to Calculate Expected Modularity in Probabilistic Networks

Date: 16 November, 10:15–11:15
Lecturer: Xin Shen (IT department, Uppsala University)

Abstract: Many real-life networks are uncertain and can thus be better modeled using probabilistic networks, where each edge is associated with a probability representing the likelihood of its existence. Probabilistic networks have been studied in many applications, such as protein-protein interaction networks, social networks, and co-authorship networks. Modularity is a fundamental measure to study networks, for example, to study communities and core-periphery structures. However, while the problem of finding modules in probabilistic networks has received some attention in the literature, no existing work has studied how to extend modularity to this context. Particularly, it is challenging to efficiently calculate expected modularity when all possible worlds are considered. To address this problem, we propose two algorithms, namely PWP^EMOD and APWP^EMOD, partitioning the possible worlds based on their modularities to significantly reduce the number of probability calculations.

The out-of-sample prediction error of the square-root lasso and related estimators

Date: 26 October, 10:15–11:15
Lecturer: Cynthia Rush (Columbia University)

Abstract: We study the classical problem of predicting an outcome variable, Y, using a linear combination of a d-dimensional covariate vector, X. We are interested in linear predictors whose coefficients solve: inf_β (E[(Y - < β, X >)^r])^(1/r) + δ || β ||, where r >1 and δ > 0 is a regularization parameter. We provide conditions under which linear predictors based on these estimators minimize the worst-case prediction error over a ball of distributions determined by a type of max-sliced Wasserstein metric. A detailed analysis of the statistical properties of this metric yields a simple recommendation for the choice of regularization parameter. The suggested order of δ, after a suitable normalization of the covariates, is typically d/n, up to logarithmic factors. Our recommendation is computationally straightforward to implement, pivotal, has provable out-of-sample performance guarantees, and does not rely on sparsity assumptions about the true data generating process. This is joint work with Jose Montiel Olea, Amilcar Velez and Johannes Wiesel. Our recommendation is computationally straightforward to implement, pivotal, has provable out-of-sample performance guarantees, and does not rely on sparsity assumptions about the true data generating process. This is joint work with Jose Montiel Olea, Amilcar Velez and Johannes Wiesel.

Strong limit laws for triangular Pólya urns

Date: 19 October, 10:15–11:15
Lecturer: Svante Janson (Uppsala University)

Abstract: Consider a triangular Pólya urn, and let $X_{ni}$ be the number of balls of
colour $i$ after $n$ drawings. We show, under very mild technical conditions, that there exist constants $\beta_i \ge 0$ and $\gamma_i\in(-\infty,\infty)$ such that
$ X_{in}/(n^{\beta_i} (\log n)^{\gamma_i}) $ converges a.s. to some strictly positive random variable. The numbers $\beta_i$ and $\gamma_i$ have explicit definitions.
The limit random variable is sometimes degenerate (= a constant); we more or
less describe when this happens.
The proof is based on the old method of embedding in a continuous-time version
of the urn, and proving corresponding results in continuous time.

The minimum number of maximal independent sets in twin-free graphs

Date: 12 October, 10:15–11:15
Lecturer: Stephan Wagner, Uppsala University

Abstract: The problem of determining the maximum number of maximal independent sets in different graph classes dates back to a paper of Miller and Muller and a question of Erdős and Moser from the 1960s. The analogous problem for the minimum is trivial, but becomes significantly more interesting when restricted to twin-free graphs, where no two vertices have the same open neighbourhood. With this restriction, the minimum number of maximal independent sets turns out to be logarithmic in the number of vertices for arbitrary graphs, linear for bipartite graphs and exponential for trees. Joint work with Stijn Cambie (Kortrijk).

Isoperimetric bounds for critical exponents for long range percolation

Date: 28 September, 10:15–11:15
Lecturer: Noam Berger, Technical University of Munich

Abstract: We prove lower bounds for certain critical exponents for long range percolation, using isoperimetric inequalities. In particular, in some cases we rule out mean-field behaviour, and in some other cases our bounds match known upper bounds. The talk will include a long introductory part where the background and the terminology will be thoroughly explained. Based on joint work with J. Bäumler.

Components in meandric systems and the infinite noodle

Date: 21 September, 10:15–11:15
Lecturer: Paul Thévenin, University of Vienna

Abstract: A meandric system of size n is a topological configuration of non-crossing closed loops in the plane which cross the real line at exactly 2n points. We are interested in the number cc(Mn) of loops in a meandric system Mn of size n chosen uniformly at random. We prove that cc(Mn) grows linearly with n and is concentrated around its mean. The main idea is to show the convergence of Mn in a local sense, towards a discrete infinite object which we call the infinite noodle, first introduced by Curien, Kozma, Sidoravicius and Tournier.

If time permits, I will discuss some new interesting problems and results on meandric systems.

Joint work with Valentin Féray (IECL, France) )

The chromatic number of G(n,1/2): bounds, concentration and conjectures

Date: 7 September, 10:15–11:15
Lecturer: Annika Heckel

Abstract: I will discuss the chromatic number of the random graph G(n,p), which is the minimum number of colours needed for a vertex colouring where neighbours are always coloured differently. In particular I will talk about the concentration (or lack thereof) of the chromatic number of G(n,1/2), and how this behaviour changes drastically if we restrict ourselves to colourings which don't contain very large colour classes. This leads to a number of conjectures about the exact limiting distribution of the chromatic number of G(n,1/2). Based on joint work with Oliver Riordan and with Konstantinos Panagiotou.

Maximal local mean and local density of a tree

Date: 1 June, 10:15–11:15
Lecturer: Ruoyu Wang, Uppsala University

Abstract: Given a tree T and a subtree S, the local mean at S can be defined as the average order of the subtrees containing S. Properties of subtrees that attains maximal local mean are then of interest. It will be shown that such maximal subtrees have at most one leaf with degree greater than 2. Local density is a normalization of local mean so that one can compare subtrees of different orders. I will discuss some basic properties of local densities such as upper/lower bounds.

"Distances in random trees" and "Sampling and community structure in bipartite graphs"

Date: 25 May, 10:15–12:00
Lecturer: Jacob Lundblad and Ekaterina Toropova

Abstract for the presentation "Sampling and community structure in bipartite graphs" by Ekaterina Toropova: Consider a sampled graph Gp, which is derived from a bipartite graph G by preserving each edge with probability p. To assess how clearly the community structure is present in a graph and which vertex partition captures it best, it is common to use modularity. We provide sufficient conditions for the edge sampling probability p such that the bipartite modularity of the sampled graph is likely to be a good approximation of the bipartite modularity of the underlying graph.

Abstract for the presentation "Distances in random trees" by Jacob Lundblad: The Wiener index of a graph G is defined as the sum of the distances between all pairs of vertices in G. In this master thesis we introduce recursive trees, plane oriented recursive trees (PORTs) and simply generated trees. We then present results by Neininger [1], Munsonius and R ̈uschendorf [2] and Janson [3] for the expectation and limiting distribution of the Wiener index of these families. For recursive trees and PORTs the results follow from analysing the recursive structure of the trees and the contraction method, while the results for simply generated trees is based on a limiting object, the continuum random tree. [1] R. Neininger, The Wiener index of random trees, Combin. Probab. Comput. 11 (6) (2002) 587–597. [2] G.O.Munsonius, L.Ruschendorf, Limit theorems for depths and distances in weighted random b-ary recursive trees, Journal of Applied Probability 48 (4) (2011) 1060–1080. [3] S. Janson, The Wiener index of simply generated random trees, Random Structures Algorithms 22 (4) (2003) 337–358

Limit theorems for Fishburn matrices

Date: 11 May, 10:15–11:15
Lecturer: Hsien-Kuei Hwang (Academia Sinica)

Abstract: Fishburn matrices are upper-triangular square matrices with nonnegative integers as entries such that no row and no column contains exclusively zeros. They have been found to be bijectively equivalent to several other combinatorial structures such as (2+2)-free posets, ascent sequences, certain pattern avoiding permutations, (2-1)-avoiding inversion sequences, Stoimenow matchings, and regular linearized chord diagrams. In addition to their rich combinatorial connections and modeling capabilities, the corresponding asymptotic enumeration and the finer distributional properties are equally enriching and challenging. We present a general, direct, analytic approach for dealing with the asymptotic enumeration and stochastic properties on generalized Fishburn matrices. Many normal and Poisson limit laws are given, and they represent the first of their kinds. This talk is based on joint work with Emma Yu Jin and Michael Schlosser. PS our papers on Fishburn matrices

Incorporating Negative Connections: Signed Networks and Their Properties

Date: 4 May, 10:15–11:15
Lecturer: Yu Tian (Nordita)

Abstract: Two competing types of interactions often play an important part in shaping system behavior, such as activatory or inhibitory functions in biological systems. Hence, signed networks, where each connection can be either positive or negative, have become popular models over recent years. In this talk, I will first introduce a classification of signed networks into balanced, antibalanced or strictly balanced ones, and then characterise each type of signed networks in terms of the spectral properties of the signed weighted adjacency matrix. In particular, the spectral radius of the matrix with signs is smaller than that without if and only if the signed network is strictly unbalanced. These properties are important to understand the dynamics on signed networks, both linear and nonlinear ones. Later in this talk, I will show consistent patterns in a linear and a nonlinear dynamics, depending on their type of balance, together with the numerical experiments on both synthetic and real networks

A brief encounter with parametrized probabilistic graphical models

Date: 27 April
Lecturer: Vera Koponen (Uppsala University)

Abstract: In Statistical Relational AI, a subfield of AI and machine learning which combines the logical and probabilistic schools of AI, Parametrized Probabilistic Graphical Models (PGMs) are used for describing dependencies between ("parametrized") random variables and for describing probability distributions on "possible worlds/scenarios". PGMs are in general a quite powerful theoretical formalism, but in practise there are issues concerning the computational (in)efficiency of learning a PGM or using it to make inferences. Metods from finite model theory (a branch of mathematical logic) can be used to tackle such issues. This will be a nontechnical talk where I will explain most things by examples and by "hand waving".

Superconcentration, chaos and multiple valleys in first passage percolation

Date: 20 April, 10:15–11:15
Lecturer: Mia Deijfen (Stockholm University)

Abstract: We consider a dynamical version of first-passage percolation on the d-dimensional integer lattice with i.i.d. edge weights, where edge weights are resampled independently in time. Let T(n) denote the passage time from the origin to the site n steps along the first coordinate axis at time t=0, and let \mu(t) denote the expected overlap between the time minimizing paths at time 0 and t>0. We show that a subdiffusive behaviour of T(n) is equivalent to a chaotic behavior of the time minimizing paths, manifested in that \mu(t)=o(n). Known bounds for Var(T(n)) thus imply that indeed \mu(t)=o(n) for t>0. As a consequence we show that there are many almost disjoint paths with almost optimal passage time. This gives evidence that earlier work by Sourav Chatterjee for certain Gaussian disordered systems reflects a more general principle.

Fringe trees for random trees with given vertex degrees

Date: 13 April, 11:15–12:15
Lecturer: Gabriel Berzunza Ojeda (University of Liverpool)

Abstract: In this talk, we consider fringe trees of random plane trees with given vertex statistics (i.e., a given number of vertices of each degree). The main results are laws of large numbers and central limit theorems for the number of fringe trees of a given type.
The key tool for our proofs is an extension to the multivariate setting of a theorem by Gao and Wormald (2004), which provides a way to show asymptotic normality by analyzing the behaviour of sufficiently high factorial moments.
Our results also apply to random simply generated trees (or conditioned Galton–Watson trees) by conditioning on their degree statistic, and to random labelled trees with given vertex degrees.
Joint work with Cecilia Holmgren and Svante Janson (Uppsala University).

Laplacian growth models on the Sierpinski gasket

Date: 23 March, 10:15–11:15
Lecturer: Nico Heizmann, TU Chemnitz

Abstract: In this talk we will introduce the three Laplacian growth models Internal Diffusion Limited Aggregation, Rotor-Router Aggregation, and the Divisible Sandpile model. We will investigate their Scaling limits on the Sierpinski gasket and for this purpose very briefly introduce basic Analysis on the Sierpinski gasket including the definition of an Laplacian and its Green function.

The number of descendants in a random directed acyclic graph

Date: 9 March, 10:15–11:15
Lecturer: Svante Janson

Abstract: Consider a random directed acyclic graph, obtained by recursively adding vertices, where each new vertex has a fixed outdegree $d$ and the endpoints of the $d$ edges from it are chosen uniformly at random among previously existing vertices. For simplicity we assume $d=2$. We study the set of vertices that are descendants of a given vertex $n$ (asymptotically, for large $n$). The main result is that the number of such vertices, divided by $\sqrt{n}$, converges in distribution together with all moments. The limit distribution is, up to a constant factor, a chi distribution $\chi(4)$. The talk is based on a recent preprint arXiv:2302.12467 or my web page.

From Kreweras to Gessel: A walk through patterns in the quarter plane

Date: 2 March, 10:15–11:15
Lecturer: Sarah Jane Selkirk, University of Klagenfurt

Abstract: The study of patterns in lattice paths is one of the major research topics within statistics on lattice paths. Several recent articles have developed the vectorial kernel method, which provides a general framework for studying patterns (and pattern avoidance) in directed lattice paths. In this talk I will discuss pattern avoidance in directed lattice paths and some first combinatorial steps towards studying pattern avoidance in the more complex case of the quarter plane, with unexpected links between famous models. This is joint work with Andrei Asinowski and Cyril Banderier.

Analysis of Regular and Recursive Sequences

Date: 23 Febrary, 10:15-11:15
Lecturer: Clemens Heuberger, Alpen-Adria-Universität Klagenfurt

Abstract: Regular Sequences have been introduced by Allouche and Shallit and can be described as matrix products depending on the digit expansion of the index. A prominent example is the sum of digit function; sequences induced by the divide-and-conquer paradigm are also related. We present results on the asymptotic analysis, discuss the special case of recursive sequences. Finally, we discuss the adaptation of the minimisation algorithm of Berstel and Reutenauer for recognisable sequences to regular sequences. (Based on joint work with Daniel Krenn and Gabriel Lipnik)

Conservative random walk and related topics

Date: 16 February, 10:15–11:15
Lecturer: Stanislav Volkov, Lund University

Abstract: Consider the following modification of a simple random walk (SRW) on Z^d, d>=1. The usual SRW chooses its direction at random uniformly from all 2d possibilities at every moment of time. But now suppose that at time n=0,1,2,... the walk just keeps going in the same direction it was going previously, and only decides to update its direction with probability p_n, where p_n is a given (non-random) sequence. Is this walk recurrent/transient? What is its scaling limit? I am going to answer these questions during my talk. Based on the joint work with János Engländer.

Community detection with censoring

Date: 9 February, 10:15–11:15
Lecturer: Souvik Dhara, Brown University

Abstract: Recovering latent communities is a key unsupervised learning task in network data with applications spanning across a multitude of disciplines. For example, identifying communities in web pages can lead to faster search, classifying regions of the human brain in communities can be used to predict onset of psychosis, and identifying communities of assets can help investors manage risk by investing in different communities of assets. However, the scale of these massive networks has become so large that it is often impossible to work with the entire network data. In this talk, I will talk about some theoretical progress for community detection in a probabilistic set up especially when we have missing data about the network. Based on joint works with Julia Gaudio, Elchanan Mossel and Colin Sandon.

Multi-conditioned random planar maps

Date: 19 January, 10:15–11:15
Lecturer: Igor Kortchemski (École polytechnique)

Abstract: We will be interested in the structure of large random random planar maps (which can informally be seen as random surfaces obtained by gluing together polygons), where the numbers of edges, faces and vertices are all fixed. Using a bijection, the main ingredient is to obtain local estimates on random walks in large deviation regimes. This is joint work with Cyril Marzouk.

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 Louf, Uppsala 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 Pak, University 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 Johansson, Stocholms 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 Tkachov, Gran 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.