Probability and Statistics

Statistics & Probability > MATHS> BI> FSE> RUG

Groningen Probability Seminar

If you are interested in giving a talk or want to suggest a speaker, please send an email with the title and abstract to a member of the Probability and Statistics Group.

Future Talks

 Dec 13, 2022 14:00-15:00 5161.0041b Sophie Huiberts (Columbia University, NYC) Smoothed analysis of projected polyhedra

Past Talks

 Nov 29, 2022 14:00-15:00 Nov 15, 2022 14:00-15:00 Jimmy He (MIT) Shift invariance of half space integrable models Régine Marchand (Lorraine university) Growth of the contact process in a (fixed) random environment. Jakub Kwaśny (AGH University) Neighbour-distinguishing edge colourings of graphs Danila Cherkashin (IMI BAS) Random approach to a proper coloring of 3-graphs Valentin Feray (Nancy) The theory of permutons and a universality result for pattern avoiding permutations Daniel Willhalm (Groningen) Limit theory of sparse random geometric graphs in high dimensions Dan Romik (University of California, Davis) The oriented swap process, exclusion processes and random matrix theory Nicholas Fraiman (UNC) Approximating the Potts model on expander graphs Jeff Kahn (Rutgers University) Linear cover time is exponentially unlikely Johan Tykesson (Chalmers) Phase transitions in the fractal cylinder process Konstantinos Panagiotou (Munich) Asymptotic enumeration and limit laws for multisets Matej Stehlik (IRIF) Edge-critical subgraphs of Kneser graphs Andreas Goebel (University of Potsdam) Sampling and approximation algorithms for Gibbs point processes Daniel Ahlberg (Stockholm University) Multi-colour competition on a cycle Nicola Turchi (University of Milano-Bicocca) The slicing problem via random polytopes Sjoerd Dirksen (Universiteit Utrecht) Sharp estimates on random hyperplane tessellations Matthias Reitzner (University of Osnabrück) Convex Hulls of Random Points Xinyi Li (Peking University) Shape theorem and surface fluctuation for Poisson cylinders Suman Chakraborty (Eindhoven University of Technology) Sparse random graphs with many triangles Teun Verstraaten (University of Gronigen) Cycles in Mallows random permutations Ron Peled (Tel Aviv University) Packing squares on the square lattice Mihyun Kang (Graz University of Technology) Local limits of sparse random planar graphs Malwina Luczak (University of Melbourne) Long-term concentration of measure and cut-off Daniel Rosen (Ruhr University Bochum) Fluctuations of lambda-geodesic Poisson hyperplanes in hyperbolic space Carina Betken (Ruhr University Bochum) Central limit theory for Poisson cylinder processes Thomas Godland (University of Münster) Beta-star polytopes and hyperbolic stochastic geometry Yu Liu (Peking University) Sharpness of phase transition for Voronoi percolation in hyperbolic space Gilles Bonnet (University of Groningen) Combinatorial Diameter of Random Polytopes Paweł Prałat (Ryerson University) Semi-random process Steven Kelk (Department of Data Science and Knowledge Engineering (DKE), Maastricht University) Convex characters, algorithms and matchings D. Yogeshwaran (Indian Statistical Institute, Bangalore) Poisson process approximation under stabilization and Palm coupling Dieter Mitsche (Institut Camille Jordan UMR CNRS-UNS) The jump of the clique chromatic number of random graphs Elliot Paquette (McGill University) The threshold for simple-connectedness in hypercube percolation Eric Cator (Radboud University) Contact process on low-rank graphs Piet Lammers (IHES Paris) Height function delocalisation on cubic planar graphs Serte Donderwinkel (University of Oxford) What do the strongly connected components of a large directed graph with i.i.d. degree tuples look like? Balázs Ráth (Budapest University of Technology) Percolation of worms Jun Yu (Umeå University) Statistical learning and inference for spatiotemporal data Xavier Pérez Giménez (University of Nebraska-Lincoln) Perfect matchings in the random bipartite geometric graph Aernout van Enter (University of Groningen) Dyson models with random boundary conditions Guillem Perarnau (Universitat Politècnica de Catalunya) Extremal stationary values for random digraphs Tobias Müller (University of Groningen) Percolation on hyperbolic Poisson-Voronoi tessellations Christian Hirsch (University of Groningen) Maximum likelihood estimation in stochastic channel models Victor Bernal (University of Groningen) Improved network reconstruction with shrinkage-based Gaussian graphical models Luca del Core (University of Groningen) Stochastic modelling of COVID-19 spread in Italy Abdul Salam (University of Groningen) Non Homogeneous Dynamic Bayesian Network Models Rangel Baldasso (University of Leiden) Sharp thresholds for Glauber dynamics percolation Deepan Basu (University of Groningen) A class of stick breaking models Jo Ellis-Monaghan (University of Amsterdam) Graph theoretical design strategies for tile-based DNA self-assembly Daniel Valesin (University of Groningen) The contact process on random hyperbolic graphs Markus Heydenreich (LMU Munich) The weight-dependent random connection model Daniel Willhalm (University of Groningen) Large deviation estimates for subsets of size conditioned Galton-Watson trees Christian Hirsch (University of Groningen) Functional CLT for persistent Betti numbers on point processes and networks Leandro Chiarini (IMPA/Utrecht) TBA Johannes Krebs (TU Braunschweig) On the law of the iterated logarithm and strong invariance principles in stochastic geometry Benjamin Hansen (University of Groningen) Voronoï percolation in the hyperbolic plane Bernardo N. B. de Lima (Federal University of Minas Gerais) The Constrained-degree percolation model Miloš Stojaković (Novi Sad) Mini Course: Introduction to Positional Games Fiona Skerman (Masaryk) Community structure in Networks - limits of learning Guilherme Reis (Bahia-UFBA) Interacting diffusions on sparse random graphs Stein Andreas Bethuelsen (Stavanger) On projections of the supercritical contact process: uniform mixing and cutoff phenomenon Luca Avena (Leiden) Loop-erased partitioning: two-point correlations on mean-field models Guus Regts (Amsterdam) On the location of zeros of the independence polynomial for bounded degree graphs Alessandra Cipriani (Delft) The discrete Gaussian free field on a compact manifold Clara Stegehuis (Eindhoven) Optimizing constrained and unconstrained network structures Dieter Mitsche (Nice) k-regular subgraphs near the k-core threshold of a random graph Bernardo N. B. de Lima (Federal University of Minas Gerais) Truncated long-range percolation on oriented graphs Moritz Schauer (Leiden) A generator approach to stochastic monotonicity and propagation of order Evgeny Verbitskiy (Leiden) Solvable models from the ergodic point of view Rodrigo Ribeiro (IMPA) Building your path to escape from home Renato Santos (Weierstrass Institute) Random walk on random walks Conrado Costa (Leiden) Law of large numbers and LDP for the Random Walk in the Cooling random Environment Daniel Valesin (Groningen) Monotonicity for multi-range percolation on oriented trees

Abstracts

Title: Smoothed analysis of projected polyhedra

Speaker Sophie Huiberts

Abstract: Motivated by the study of linear optimization algorithms, we are interested in two-dimensional projections of higher-dimensional polyhedra, and specifically how many vertices these 'shadows' have. I will describe upper and lower bounds on this number for a class of semi-random models known under the heading of 'smoothed analysis'. This talk is based on joint work with Yin Tat Lee and Xinzhi Zhang.

Title: Shift invariance of half space integrable models

Speaker Jimmy He

Abstract: I'll discuss recent work on shift invariance in a half space setting. These are non-trivial symmetries allowing certain observables of integrable models with a boundary to be shifted while preserving their joint distribution. The starting point is the colored stochastic six vertex model in a half space, from which we obtain results on the asymmetric simple exclusion process, as well as for the beta polymer through a fusion procedure, both in a half space setting. An application to the asymptotics of a half space analogue of the oriented swap process is also given.

Title: Growth of the contact process in a (fixed) random environment.

Speaker Régine Marchand

Abstract: This talk is based on joint works with Olivier Garet and Tom Riblet. I will start by recalling the shape theorem for the supercritical contact process in Zd: starting from the origin, conditionaly on its survival, the contact process grows asymptotically linearily in time. The contact process in a fixed random environment is a natural generalization of the contact process. First, the environment is chosen randomly and fixed: we can for instance replace the constant infection rate by a collection of iid infection rates indexed by the edges of Zd, or replace Zd itself by the infinite cluster of a supercritical Bernoulli percolation... Many important properties are lost: if we work in the fixed (quenched) environment, we keep the Markov property of the contact process but we lose the stationarity in space, while if we work in the annealed setting, we recover the stationarity in space but we lose the Markovianity of the contact process. The aim of the talk is to show how and under which assumptions we can recover a shape theorem for the contact process in random environment

Title: Neighbour-distingushing edge colourings of graphs

Speaker Jakub Kwaśny

Abstract: Let $c$ be a proper edge colouring of a simple graph $G=(V,E)$ of maximum degree $\Delta$. For such a colouring we define a \textit{palette} $S_c(v)$ of each vertex $v$ as the set of colours of the incident edges, i.e.:

$\displaystyle{S_c(v)=\{c(uv)\colon uv\in E\}.}$

In 2002, Zhang et al. stated a conjecture that $\Delta+2$ colours are sufficient to colour the edges so that the neighbouring vertices have distinct palettes. We present a result for the list version of Zhang's problem and introduce another generalisation of that condition. These results are joint work with Jakub Przybyło.

Title: Random approach to a proper coloring of 3-graphs

Speaker Danila Cherkashin

Abstract: TBA

Title: Limit theory of sparse random geometric graphs in high dimensions

Speaker Daniel Willhalm

Abstract: We study topological and geometric functionals of high-dimensional $l_\infty$-random geometric graph in a sparse regime, where the expected number of neighbors decays exponentially in the dimension. More precisely, we establish moment asymptotics, central limit theorems and Poisson approximation theorems for certain functionals that are additive under disjoint unions of graphs. For instance, this includes simplex counts and Betti numbers of the Rips complex, as well as general subgraph counts of the random geometric graph. We also present multi-additive extensions that cover the case of persistent Betti numbers of the Rips complex.

Joint work with Gilles Bonnet, Christian Hirsch and Daniel Rosen.

Title: The theory of permutons and a universality result for pattern avoiding permutations

Speaker: Valentin Feray

Abstract: The talk is divided in two parts. In the first one, I will present the theory of "permutons", or "permutation limits". Permuton convergence can be seen either as a scaling limit theory for permutation matrices or, equivalently, as the convergence of substructure densities (in an analog way as graphon convergence in graph theory). I will show examples of random permutation models, which converge to nontrivial permutons (not giving details, but showing pictures).

The second part will cover a result obtained as a joint work with F. Bassino, M. Bouvel, L. Gerin, M. Maazoun and A. Pierrot, regarding permuton convergence of random permutations, conditioned to avoid some substructures (pattern avoiding permutations). We have shown that a dichotomy phenomenon: for a large family of such permutation models, we have convergence either towards a "Brownian" permuton, or towards an $X$-permuton.

Title: The oriented swap process, exclusion processes and random matrix theory

Speaker: Dan Romik

Abstract: The oriented swap process is a natural directed random walk on the symmetric group which can be visualized as follows: N particles labeled 1,...,N are initially placed in respective positions 1,...,N, then begin performing adjacent swaps according to the rule that each pair of particles occupying adjacent positions j, j+1 attempt to swap at random times prescribed by a rate 1 Poisson clock, independent of all other clocks, with the swap succeeding if and only if the particle in position j has smaller label than the particle in position j+1.

In this talk I will explain how many aspects of the behavior of this process can be understood in terms of a coupled family of totally asymmetric simple exclusion processes, or equivalently in terms of last passage percolation. This makes it possible to use known results from random matrix theory to show that the stopping time of individual particles converges after scaling to the Tracy-Widom GUE distribution, and prove other asymptotic results. I will describe recent joint works with Bisi-Cunden-Gibbons and Bufetov-Gorin in which we extended this connection further to show that the absorbing time of the entire process converges after scaling to the Tracy-Widom GOE distribution. The proof involves a remarkable equality in distribution between the absorbing time and a statistic defined in terms of last passage percolation. A recent extension of this result by Lingfu Zhang suggests that deeper connections between the two pictures may yet be in play.

Title: Approximating the Potts model on expander graphs

Speaker: Nicholas Fraiman

Abstract: We give algorithms to approximate the ferromagnetic Potts model on d-regular expander graphs. Our method relies on a sharp analysis of abstract polymer models, via extremal graph theory and applications of Karger’s algorithm. Since it is #BIS-hard to approximate the partition function at low temperatures on d-regular graphs, our method is evidence that hard instances of #BIS are rare.

This is joint work with Charlie Carlson, Ewan Davies, Alexandra Kolla, Aditya Potukuchi and Corrine Yap.

Title: Zero-one laws for provability logic (and other modal logics)

Speaker: Rineke Verbrugge

Abstract: It has been shown in the late 1960s that each formula of first-order logic without constants and function symbols obeys a zero-one law: As the number of elements of finite models increases, every formula holds either in almost all or in almost no models of that size. Therefore, many properties of models, such as having an even number of elements, cannot be expressed in the language of first-order logic. For modal logics, limit behavior for models and frames may differ. In 1994, Halpern and Kapron proved zero-one laws for classes of models corresponding to the modal logics K, T, S4, and S5. They also proposed zero-one laws for the corresponding classes of frames, but their zero-one law for K-frames has since been disproved.

In this talk, we first give a short introduction to propositional provability logic and to validity in frames (structures) and validity in models (structures with valuations). Subsequently, we prove zero-one laws for provability logic with respect to both model and frame validity. Moreover, we axiomatize validity in almost all irreflexive transitive finite models and in almost all irreflexive transitive finite frames, leading to two different axiom systems. In the proofs, we use a combinatorial result by Kleitman and Rothschild about the structure of almost all finite partial orders. The countably infinite random Kleitman-Rothschild frame will play an important role in the proof of the zero-one law for frames. On the way, we also show that a previous result by Halpern and Kapron about the axiomatization of almost sure frame validity for S4 is not correct.

Title: Linear cover time is exponentially unlikely

Speaker: Jeff Kahn

Abstract: Proving a 2009 conjecture of Itai Benjamini, we show:

For any $C$ there is $c > 0$ so that for any simple random walk on an n-vertex graph $G$, the probability that the first Cn steps of the walk see every vertex is less than $\exp[-cn]$.

A first ingredient in the proof of this is a similar statement for Markov chains in which all transition probabilities are less than a suitable function of $C$.

Joint with Quentin Dubroff.

Title: Phase transitions in the fractal cylinder process

Speaker: Johan Tykesson

Abstract: We consider a semi-scale invariant version of the Poisson cylinder model which in a natural way induces a random fractal set. We show that this random fractal exhibits an existence phase transition for any dimension $d\geq 2$, and a connectivity phase transition whenever $d\geq 4$. A key ingredient when analysing the connectivity phase transition is to consider a restriction of the full process onto a subspace. We show that this restriction results in a fractal ellipsoid model and it is key to obtaining our main results.

The talk is based on joint work with Erik Broman, Olof Elias and Filipe Mussini

Title: Asymptotic enumeration and limit laws for multisets

Speaker: Konstantinos Panagiotou

Abstract: For a given combinatorial class $\mathcal{C}$ we study the class $\mathcal{G} = {Mset}(\mathcal{C})$ obeying the multiset construction, that is, any object in $\mathcal{G}$ is uniquely determined by a set of $\mathcal{C}$-objects paired with their multiplicities. For example, ${Mset}(\mathbb{N})$ is (isomorphic to) the class of number partitions of positive integers, a prominent and well-studied case. The multiset construction appears naturally in the study of unlabeled objects, for example graphs or various structures related to number partitions. We perform a thorough analysis of the set $\mathcal{G}_{n,N}$ that contains all multisets in $\mathcal{G}$ having size $n$ and being comprised of $N$ objects from $\mathcal{C}$ when the counting sequence of $\mathcal{C}$ is governed by subexponential growth. In particular, we determine the asymptotic growth of $\mathcal{G}_{n,N}$ and we describe the typical limiting shape of these objects as $n\to\infty$ and $1 \ll N \le n$.

This is joint work with L. Ramzews.

Title: Edge-critical subgraphs of Kneser graphs

Speaker: Matej Stehlik

Abstract: In a landmark paper from the late 1970s, Lovász proved a conjecture on the chromatic number of Kneser graphs using one of the first applications of algebraic topology in combinatorics. Schrijver sharpened the result by exhibiting a vertex-critical subgraph of the Kneser graph with the same chromatic number. I will sketch how we can go a step further, by constructing an edge-critical subgraph of the Kneser graph with the same chromatic number. If time permits, I will briefly discuss an application of our construction by Kiselev and Kupavskii to random Kneser graphs.

Joint work with Tomas Kaiser.

Title: Sharp estimates on random hyperplane tessellations

Speaker: Sjoerd Dirksen

Abstract: In my talk I will consider the following question. Take independent random hyperplanes with standard Gaussian directions and uniformly distributed shifts. How many hyperplanes are needed to uniformly tessellate a given subset of \R^n with high probability? In my talk I will first explain two motivating applications for this question: data dimensionality reduction and signal processing under coarse quantization. I will then present a generally optimal answer to this question, which surprisingly deviates from the answer that was conjectured in the literature. If time permits, I will show an extension of this result to a specific structured random tessellation, which is designed for computationally fast data dimensionality reduction.

The talk is based on joint work with Shahar Mendelson (ANU Canberra, Warwick) and Alexander Stollenwerk (UCLouvain)

Title: Shape theorem and surface fluctuation for Poisson cylinders

Speaker: Xinyi Li

Abstract: In this talk I will introduce the model of Poisson cylinders and discuss a shape theorem for Poisson cylinders with a power-law bound on surface fluctuations. This is a joint work with M. Hilario (Universidade Federal de Minas Gerais) and P. Panov (The University of Chicago).

Title: Sparse random graphs with many triangles

Speaker: Suman Chakraborty

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 we investigate the following questions: how (un)likely is it that a sparse random graph will contain a large number of triangles? How does the graph look like when it contains a large number of triangles? We also study another related question: what is the probability that in a sparse random graph large number of vertices will be part of some triangle? We will discuss these questions and some possible applications to exponential random graph models.

Title: TBA

Speaker: Sophie Huiberts

Abstract: TBA

Title: Cycles in Mallows random permutations

Speaker: Teun Verstraaten

Abstract: We study cycle counts in permutations of $1,\dots,n$ drawn at random according to the Mallows distribution. Under this distribution, each permutation $\pi \in S_n$ is selected with probability proportional to $q^{\text{inv}(\pi)}$, where $q>0$ is a parameter and $\text{inv}(\pi)$ denotes the number of inversions of $\pi$. For $\ell$ fixed, we study the vector $(C_1(\Pi_n),\dots,C_\ell(\Pi_n))$ where $C_i(\pi)$ denotes the number of cycles of length $i$ in $\pi$ and $\Pi_n$ is sampled according to the Mallows distribution. Here we show that if $0<q<1$ is fixed and $n\to\infty$ then there are positive constants $m_i$ such that each $C_i(\Pi_n)$ has mean $(1+o(1)) \cdot m_i\cdot n$ and the vector of cycle counts can be suitably rescaled to tend to a joint Gaussian distribution. Our results also show that when $q>1$ there is striking difference between the behaviour of the even and the odd cycles. The even cycle counts still have linear means, and when properly rescaled tend to a multivariate Gaussian distribution. For the odd cycle counts on the other hand, the limiting behaviour depends on the parity of $n$ when $q>1$. Both $(C_1(\Pi_{2n}),C_3(\Pi_{2n}),\dots)$ and $(C_1(\Pi_{2n+1}),C_3(\Pi_{2n+1}),\dots)$ have discrete limiting distributions -- they do not need to be renormalized -- but the two limiting distributions are distinct for all $q>1$. We describe these limiting distributions in terms of Gnedin and Olshanski's bi-infinite extension of the Mallows model. We also investigate these limiting distributions, and study the behaviour of the constants involved in the Gaussian limit laws. We for example show that as $q\downarrow 1$ the expected number of 1-cycles tends to $1/2$ -- which, curiously, differs from the value corresponding to $q=1$. In addition we exhibit an interesting "oscillating" behaviour in the limiting probability measures for $q>1$ and $n$ odd versus $n$ even. Joint work with Tobias Müller.

Title: Packing squares on the square lattice

Speaker: Ron Peled

Abstract: We study random packings of 2 x 2 squares with centers on the square lattice, in which the probability of a packing is proportional to a parameter lambda raised to the number of squares in the packing. Classical methods show that low-density random packings (small lambda) are disordered, but the behavior of high-density random packings (large lambda) remained open in the mathematical literature due to a "sliding instability" in the optimal packings. We resolve the high-density behavior, proving that typical random packings exhibit columnar order, in which either the centers of most tiles agree on the parity of their x-coordinate or the centers of most tiles agree on the parity of their y-coordinate. In technical language, our results show the existence of four extremal and periodic Gibbs measures in which the lattice rotational symmetry is broken while the translational symmetry is only broken along a single axis. We also prove that every periodic Gibbs measure is a mixture of these four measures. Joint work with Daniel Hadas.

Title: Sampling and approximation algorithms for Gibbs point processes.

Speaker: Andreas Goebel

Abstract: Gibbs point processes are frequently used in statistical physics to model gasses and liquids of interacting particles. The main computational tasks related to such models are sampling from the point process and computing its partition function, which is the normalising constant of its distribution. In this talk, we will discuss computational aspects of Gibbs point processes that are defined by a fugacity parameter $\lambda \in \mathbb{R}_{\ge 0}$ and a repulsive symmetric pair potential $\phi$ on a bounded measurable region $\mathbb{V}$ of a complete separable metric space, equipped with a locally finite reference volume measure $\nu$. Our approach, developed over a series of articles, yields polynomial-time algorithms for approximately sampling from such point processes and for obtaining a randomised approximation of their partition functions, as well as quasi-polynomial deterministic algorithms for approximating their partition functions. Under mild assumptions, such as a uniform sampler for $\mathbb{V}$, our algorithms have running time polynomial in the volume $\nu(\mathbb{V})$ of the region for all fugacities $\lambda < \text{e}/C_{\phi}$, where $C_{\phi}$ denotes the temperedness constant of the potential.

Our algorithmic approach is based on mapping repulsive Gibbs point processes to hard-core models on a natural family of geometric random graphs. Previous attempts to discretize Gibbs point processes based on hard-core models, which we will aslo discuss in this talk, used deterministically constructed graphs, which limited the results to not only hard-constraint potentials but also to box-shaped regions $\mathbb{V}=[0, \ell]^d$ in $d$-dimensional Euclidean space. We overcome both limitations by randomization of the considered graph. Specifically, for all $n \in \mathbb{N}_{\ge 1}$, we define a distribution of random graphs $\zeta^(n)_{\mathbb{V}, \phi}$ such that the partition function of a hard-core model on a random graph from this distribution concentrates around the partition function of a Gibbs point process with potential $\phi$ on the region $\methbb{V}$ for $n \in \Theta\left(\nu(\mathbb{V})^2\right)$. We show this concentration result by deriving a corollary of the Efron–Stein inequality, which allows proving concentration for a function of independent random inputs, given that the output of this function only exhibits small relative changes when one of its inputs is altered. A randomized approximation for the partition function of a Gibbs point process follows from approximating the hard-core partition function of a random graph from $\zeta^(n)_{\mathbb{V}, \phi}$. Furthermore, we obtain an efficient sampler for the Gibbs point process by utilizing an approximate sampler for the hard-core model on a random graph from $\zeta^(n)_{\mathbb{V}, \phi}$. By deriving the density of our spampler with respect to a Poisson point process via the Rényi–Mönch theorem, we show that it is close to the density of the original Gibbs point process.

Title: Multi-colour competition on a cycle

Speaker: Daniel Ahlberg

Abstract: Polya’s urn is the archetypical example of a random process with reinforcement. In this talk we shall be concerned with an interacting system of urns, where balls of different colour compete for their survival. Consider a cycle of length N and position at each vertex an urn. Each urn may contain balls of K different colours, but is only allowed to contain balls of one colour at any given time. Each ball is equipped with a Poisson clock, and at the ring of its clock the ball sends a copy of itself to each neighbour. Balls of different colour that appear in the same urn annihilate immediately on a 1-1 basis. Griffiths, Janson, Morris and myself proved that for K=2 for this process there will eventually be a single surviving colour, and conjectured that the same should hold also for K>2. We prove this conjecture. This is joint work with C. Fransson.

Title: The slicing problem via random polytopes

Speaker: Nicola Turchi

Abstract: The slicing problem is one of the most important open conjectures in convex geometry. It admits an equivalent formulation in terms of the so-called isotropic constant of a convex body. J. Bourgain first conjectured the absolute boundedness of this quantity. We will talk about this problem first in the deterministic setting and afterwards about how a random model can be used to investigate it. In particular, we show that if $L_{K_N}$ is the isotropic constant of an n-dimensional random polytope $K_N$ generated by $N$ independent random points which are distributed according to the cone probability measure on the boundary of an unconditional convex body $K$, then with overwhelming probability $L_{K_N}< C$ for an absolute constant $C>0$. The proofs are based on concentration inequalities for sums of sub-Gaussian random variables and on a new $\Psi_2$-estimate for linear functionals with respect to the cone measure.

Based on a joint work with J. Prochno and C. Thäle.

Title: Local limits of sparse random planar graphs

Speaker: Mihyun Kang

Abstract: In this talk we will discuss some classical and recent results on local limits of random graphs. It is well known that the limiting object of the local structure of the classical Erdos-Renyi random graph is a Galton-Watson tree. This can nicely be formalised in the language of Benjamini-Schramm or Aldous-Steele local weak convergence. Regarding local limits of sparse random planar graphs, there is a smooth transition from a Galton-Watson tree to a Skeleton tree. This talk is based on joint work with Michael Missethan.

Title: Long-term concentration of measure and cut-off

Speaker: Malwina Luczak

Abstract: We present new concentration inequalities for Markov chains (in discrete and continuous time), generalising results for chains that are contracting in Wasserstein distance. We further extend the notion of cut-off to chains with infinite state space. We illustrate our results with examples. (Based on joint work with Andrew Barbour and Graham Brightwell.)

Title: Fluctuations of lambda-geodesic Poisson hyperplanes in hyperbolic space

Speaker: Daniel Rosen

Abstract: The Poisson hyperplane tessellation in Euclidean space is a classical and well-studied model of Stochastic Geometry. In this talk we will consider its counterpart(s) in hyperbolic space. As it turns out, Euclidean hyperplanes have more than one analogue in hyperbolic space, corresponding, roughly speaking, to thinking of hyperplanes as either totally geodesic hypersurfaces, equidistant sets from other hyperplanes, or spheres of infinite radius. In hyperbolic space these notions give rise to a parametric family of hyperplane-like hypersurfaces, known collectively as lambda-geodesic hypersurfaces, for lambda between 0 and 1. We will consider the isometry-invariant Poisson process of lambda-geodesic hyperplanes, and in particular its total surface area within a growing spherical window. We will study its limit theory, and prove central and non-central limit theorems, depending on the value of lambda and the ambient dimension. Based on joint work with Z. Kabluchko and C. Thäle

Title: Convex Hulls of Random Points

Speaker: Matthias Reitzner

Abstract: Choose n random points either in the interior or on the boundary of a convex body. The convex hull of these points generates a random polytope. We report on investigations concerning properties of such a random polytope if the underlying convex set is either a smooth convex body or a simple polytope.

In the first part of the talk we will be interested in asymptotic formulas for expectation and variance of the number of vertices and faces, and of the intrinsic volumes.

In the second part we will focus on the limit distribution of these quantities.

Title: Central limit theory for Poisson cylinder processes

Speaker: Carina Betken

Abstract: We consider the union set of a stationary Poisson process of cylinders in $\mathbb{R}^n$, where by a cylinder we understand any set of the form $X \times E$, where $E$ is an $m$-dimensional linear subspace of $\mathbb{R}^n$ and $X \subset E^\perp$ is a compact subset in the orthogonal complement of $E$. The concept jointly generalises those of a Boolean model and a Poisson hyperplane or $m$-flat process. Using techniques from Malliavin-Stein method we develop a quantitative central limit theory for a broad class of geometric functionals, including volume, surface area and intrinsic volumes.

Title: Beta-star polytopes and hyperbolic stochastic geometry

Speaker: Thomas Godland

Abstract: Motivated by problems of hyperbolic stochastic geometry we introduce and study the class of beta-star polytopes. A beta-star polytope is defined as the convex hull of an inhomogeneous Poisson processes on the complement of the unit ball in $\mathbb{R}^d$ with density proportional to $(||x||^2−1)^\beta$, where $||x||>1$ and $\beta>d/2$. Explicit formulas for various geometric and combinatorial functionals associated with beta-star polytopes are provided, including the expected number of $k$-dimensional faces, the expected external angle sums and the expected intrinsic volumes. Beta-star polytopes are relevant in the context of hyperbolic stochastic geometry, since they are tightly connected to the typical cell of a Poisson-Voronoi tessellation as well as the zero cell of a Poisson hyperplane tessellation in hyperbolic space. The general results for beta-star polytopes are used to provide explicit formulas for the expected $f$-vector of the typical hyperbolic Poisson-Voronoi cell and the hyperbolic Poisson zero cell. Their asymptotics for large intensities and their monotonicity behaviour is discussed as well. Finally, stochastic geometry in the de Sitter half-space is studied as the hyperbolic analogue to recent investigations about random cones generated by random points on half-spheres in spherical or conical stochastic geometry.

Title: Sharpness of phase transition for Voronoi percolation in hyperbolic space

Speaker: Yu Liu

Abstract: In this paper, we consider Voronoi percolation in the hyperbolic space $\mathbb{H}^d$ ($d\geq2$) and show that the phase transition is sharp. More precisely, we show that for Voronoi percolation with parameter $p$ generated by a homogeneous Poisson point process with intensity $\lambda$, there exists $p_c:= p_c(\lambda,d)$ such that the probability of a monochromatic path from the origin reaching a distance of $n$ decays exponentially fast in $n$. We also prove the mean-field lower bound $\mathbb{P}_{\lambda,p}(0 \leftrightarrow \infty) \geq c(p-p_c)$ for $p>p_c$.

Title: Combinatorial Diameter of Random Polytopes

Speaker: Gilles Bonnet

Abstract: I will present a joint work (in progress) with Daniel Dadush, Uri Grupel, Sophie Huiberts and Galyna Livshyts. The combinatorial diameter $\mathrm{diam}(P)$ of a polytope $P$ is the maximum shortest path distance between any pair of vertices. In this paper, we provide upper and lower bounds on the combinatorial diameter of a random \textit{spherical} polytope, which is tight to within one factor of dimension when the number of inequalities is large compared to the dimension. More precisely, for an $n$-dimensional polytope $P$ defined by the intersection of $m$ i.i.d.\ half-spaces whose normals are chosen uniformly from the sphere, we show that $\mathrm{diam}(P)$ is $\Omega(n m^{\frac{1}{n-1}})$ and $O(n^2m^{\frac{1}{n-1}} + n^5 4^n)$ with high probability when $m \geq2^{\Omega(n)}$. For the upper bound, we first prove that the number of vertices in any fixed two dimensional projection sharply concentrates around its expectation when $m$ is large, where we rely on the $\Theta(n^2 m^{\frac{1}{n-1}})$ bound on the expectation due to Borgwardt [Math. Oper. Res., 1999]. To obtain the diameter upper bound, we stitch these \textit{shadows paths} together over a suitable net using worst-case diameter bounds to connect vertices to the nearest shadow. For the lower bound, we first reduce to lower bounding the diameter of the dual polytope $P^\circ$, corresponding to a random convex hull, by showing the relation $\mathrm{diam}(P) \geq (n-1)(\mathrm{diam}(P^\circ)-2)$. We then prove that the shortest path between any nearly'' antipodal pair vertices of $P^\circ$ has length $\Omega(m^{\frac{1}{n-1}})$.

Title: Semi-random process

Speaker: Paweł Prałat

Abstract: The semi-random graph process is a single-player game that begins with an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. During the talk, we will focus on the following problems: a) perfect matchings, b) Hamilton cycles, c) constructing a subgraph isomorphic to an arbitrary fixed graph G. We will also consider a natural generalization of the process to s-uniform hypergraphs.

Title: Convex characters, algorithms and matchings

Speaker: Steven Kelk

Abstract: A phylogenetic (i.e. evolutionary) tree is an unrooted binary tree T in which the leaves are in bijection with a set of labels X, where X represents a set of contemporary species. Here we present a number of enumeration results pertaining to convex characters: partitions of X in which the minimal spanning trees induced by the blocks of the partition, are vertex disjoint in T. Via a number of transformations we show that enumerating specially chosen subfamilies of convex characters is sufficient to give an algorithm with running time O*(1.6181^n) for computing the “2-state maximum parsimony distance” between two phylogenetic trees, where n=|X| and O*(.) suppresses polynomial factors – this distance is used to quantify how different two evolutionary histories are. Next, we show that one of these subfamilies of convex characters is actually in bijection with a constrained subfamily of matchings (i.e. disjoint sets of edges) defined over a secondary, auxiliary tree structure. By proving that there are at most O(1.5895^n) such constrained matchings, we obtain a faster algorithm for the aforementioned distance problem, and as a corollary obtain a tight upper bound on the number of matchings in general trees with certain degree restrictions, extending results from the matchings literature. For the O(1.5895^n) result we leverage recent techniques that have been developed for bounding the rate of growth of certain structured families of recurrences.

This is joint work with Ruben Meuwese (Maastricht) and Stephan Wagner (Uppsala).

Title: Poisson process approximation under stabilization and Palm coupling

Speaker: D. Yogeshwaran

Abstract: We present some Poisson process approximation results for stabilizing functionals of Poisson (or Binomial) processes that arise in stochastic geometry. Our bounds are derived for the Kantorovich-Rubinstein distance between a point process and an appropriate Poisson point process. We will discuss application to largest k-nearest neighbour distances. This is based on a joint project with Omer Bobrowski (Technion) and Matthias Schulte (Hamburg Institute of Technology) [see arXiv:2104.13261].

Title: The jump of the clique chromatic number of random graphs

Speaker: Dieter Mitsche

Abstract: The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no maximal clique is monochromatic. In 2016 together with McDiarmid and Pralat we noted that around pm n^{-1/2} the clique chromatic number of the random graph G(n,p) changes by n^{\Omega(1)} when we increase the edge-probability p by n^{o(1)}, but left the details of this surprising phenomenon as an open problem. In this paper we settle this problem, i.e., resolve the nature of this polynomial jump of the clique chromatic number of the random graph G(n,p) around edge-probability p = n^{-1/2}. Our proof uses a mix of approximation and concentration arguments, which enables us (i) to go beyond Jansons inequality used in previous work and (ii) to determine the clique chromatic number of G(n,p) up to logarithmic factors for any edge-probability p. Joint work with Lyuben Lichev and Lutz Warnke.

Title: The threshold for simple-connectedness in hypercube percolation

Speaker: Elliot Paquette

Abstract: We study the fundamental group of certain random 2-dimensional cubical complexes. We show a 2-dimensional generalization of a theorem of Burtin and Erdos-Spencer on the connectivity threshold for bond percolation. In the 2-dimensional setting, the natural analogue is a transition for the simple-connectivity of the space. This is in contrast to the 2-dimensional analogue of simplicial complexes, in which the natural analogue of the Erdos-Renyi theorem is the threshold for homological connectivity of the space (due to Linial–Meshulam). We also show that below the connectivity threshold, the fundamental group factors as a product of a finitely generated pieces, and that as the density parameter goes to 0, every finitely generated group appears. Based on joint work with Matt Kahle (The Ohio State University) and Érika Roldán (TU Munich).

Title: Contact process on low-rank graphs

Speaker: Eric Cator

Abstract: In this talk I will introduce the contact process for general infection matrices (which is slightly more general than graphs) as a model for the spread of disease or information. Since in general the contact process is hard to analyse, many ways of approximating the process have been studied. An important example of such an approximation is a type of mean field approach. I will show that this corresponds to approximating the infection matrix with a rank 1 matrix. We will extend this to higher finite rank approximations, and we will give an exact description of the behaviour of the contact process on such a finite rank matrix, as the number of nodes goes to infinity. In particular, we will be able to describe the meta-stable state of the contact process as a Gaussian process with known covariance structure.

Title: Height function delocalisation on cubic planar graphs

Speaker: Piet Lammers

Abstract: We consider models of integer-valued height functions on shift-invariant planar graphs whose maximum degree is three. We prove delocalisation for a large class of such models. This provides a simplified proof of the Kosterlitz-Thouless phase transition, and is, to the knowledge of the author, the first height function delocalisation proof which is not tied to a specific model. Included are: the discrete Gaussian and solid-on-solid models, as well as the uniformly random K-Lipschitz function, on the vertices of the hexagonal lattice. This talk is based on arXiv:2012.09687.

Title: What do the strongly connected components of a large directed graph with i.i.d. degree tuples look like?

Speaker: Serte Donderwinkel

Abstract: Universal scaling limits of random graph models can be considered the Central Limit Theorems of graph theory and have attracted a lot of interest in recent years. We consider the strongly connected components (SCC) of a uniform directed graph on $n$ vertices with i.i.d. degree tuples, under suitable moment conditions on the degree distribution. The moment conditions ensure that the graph is critical: the largest SCC contains $O(n^{1/3})$ vertices, and there are many other SCC of that order. We show that the sequence of SCC ordered by decreasing length converges under rescaling of the edge lengths to a random sequence of directed multigraphs with edge lengths that are all 3-regular or loops. The talk is based on joint work with Zheneng Xie.

Title: Percolation of worms

Speaker: Balázs Ráth

Abstract: We consider the following correlated percolation model on the d dimensional lattice $Z^d, d \geq 5$. From each vertex of $Z^d$, we start POI$(v)$ number of worms $(v>0)$, where the number of worms are i.i.d. for different vertices. Each worm $w$ has a random length $L_w$, moreover the lengths are i.i.d. for different worms. Each worm $w$ (independently of other worms) performs a simple symmetric random walk of length $L_w-1$ on $Z^d$. Let us consider the set $S^v$ of sites visited by these worms. How do the percolation properties of $S^v$ depend on the length distribution of worms?
We give an easy sufficient condition under which $S^v$ exhibits percolation phase transition and a more involved sufficient condition under which $S^v$ percolates for all $v>0$. We compare our model to other known models (e.g., finitary random interlacements, Poisson-Boolean percolation model) and argue that the percolative behaviour of our model is quite close to being "extremal" in a natural family of similar models. Joint work with Sándor Rokob.

Title: Statistical learning and inference for spatiotemporal data

Speaker: Jun Yu

Abstract: In this presentation, I will talk about what we as a statistician can do for our society and how we can help to find solutions for real-life problems, by a number of examples from statistical learning and inference for spatiotemporal data, coming from real applications.

Title: Perfect matchings in the random bipartite geometric graph

Speaker: Xavier Pérez Giménez

Abstract: We consider the standard random bipartite geometric graph process in which n red vertices and n blue vertices are placed at random on the unit d-dimensional cube and edges are added sequentially, between vertices of different colors, in increasing order of edge-length. A natural question is to ask whether the first edge in the process that results in the minimum degree being at least one coincides, with high probability, with the first edge that creates a perfect matching. While this was already known to be false when d=2, as the thresholds are not even of the same order, we are able to positively answer it for d at least 3. This is joint work with Abigail Raz.

Title: Dyson models with random boundary conditions

Speaker: Aernout van Enter

Abstract: I discuss the low-temperature behaviour of Dyson models (long-range Ising models in one dimension) in the presence of random boundary conditions. As for typical random (i.i.d.) boundary conditions Chaotic Size Dependence occurs, that is, the pointwise thermodynamic limit of the finite-volume Gibbs states for increasing volumes does not exist, but the sequence of states moves between various possible limit points, as a consequence it makes sense to study distributional limits, the so-called metastates which are measures on the possible limiting Gibbs measures. The Dyson model is known to have a phase transition for decay parameters α between 1 and 2. We show that the metastate changes character at α =3/2. It is dispersed in both cases, but it changes between being supported on two pure Gibbs measures when α is less than 3/2 to being supported on mixtures thereof when α is larger than 3/2. Joint work with Eric Endo and Arnaud Le Ny.

Title: Extremal stationary values for random digraphs

Speaker: Guillem Perarnau

Abstract: In this talk, we will discuss the extremal values of the stationary distribution of a random walk on a directed random graph with given degrees. While for undirected graphs the stationary distribution is simply determined by the degrees, the graph geometry plays a major role in the directed case. Understanding typical stationary values is key to determine the mixing time of the walk. However, typical results provide no information on extremal values, which are important for many applications. In this talk, we will show that the minimum value may be polynomially smaller than the average value, and that the correct exponents comes from the combination of two factors: (1) the contribution of atypically thin in-neighborhoods, controlled by subcritical branching processes; and (2) the contribution of atypically “light” trajectories, controlled by large deviation rate functions. This result has direct consequences for the understanding of random walks in random digraphs. In particular, we will show how one can obtain an estimate on the cover time of the random digraph. This is joint work with Xing Shi Cai.

Title: Percolation on hyperbolic Poisson-Voronoi tessellations

Speaker: Tobias Müller

Abstract: I will discuss percolation on the Voronoi tessellation generated by a homogeneous Poisson point process on the hyperbolic plane. That is, we colour each cell of the hyperbolic Poisson-Voronoitessellation black with probability and white with probability 1−p, independently of the colours of all other cells. We say that percolation occurs if there is an infinite connected cluster of black cells. I will sketch joint work with the doctoral candidate Ben Hansen that resolves a conjecture and an open question, posed by Benjamini and Schramm about twenty years ago, on the behaviour of the“critical probability for percolation” as a function of the intensity parameter of the underlying Poisson process. (Unlike in Euclidean Poisson-Voronoi percolation, this critical value depends on the intensity of the Poisson process.) Based on joint work with Benjamin Hansen.

Title: Maximum likelihood estimation in stochastic channel models

Speaker: Christian Hirsch

Abstract: We propose Monte Carlo maximum likelihood estimation as a novel approach in the context of calibration and selection of stochastic channel models. First, considering a Turin channel model with inhomogeneous arrival rate as a prototypical example, we explain how the general statistical methodology is adapted and refined for the specific requirements and challenges of stochastic multipath channel models. Then, we illustrate the advantages and pitfalls of the method on the basis of simulated data. Finally, we apply our calibration method to wideband signal data from indoor channels. Based on joint work with Ayush Bharti, Troels Pedersen, Rasmus Waagepetersen.

Title: Improved network reconstruction with shrinkage-based Gaussian graphical models

Speaker: Victor Bernal

Abstract: Gaussian graphical models (GGMs) are undirected network models where the nodes represent the random variables and the edges their partial correlations. GGMs are straightforward to implement, easy to interpret, and have an acceptable computational cost. These advantages have made GGMs popular to reconstruct gene regulatory networks from high throughput data. In this talk, I will discuss the reconstruction of GGMs in the high dimensional case (n « p). In this scenario, the inference becomes challenging and requires regularization/shrinkage. I will present a novel approach to infer GGMs structures based on the Ledoit-Wolf (LW) shrinkage, which accounts for the sample size, the number of variables, and the shrinkage value.

Title: Stochastic modelling of COVID-19 spread in Italy

Speaker: Luca del Core

Abstract: Italy was particularly hard hit during COVID-19 pandemic and the aim of this work is to describe the dynamics of infections within each region and the geographical spread of the virus over time. To this end we extend the standard SIRD framework by introducing pairwise interaction terms between the region-specific infected compartments. That is, we check how the increments of infected people of one region depends on that of another region. That information could be used as a proxy to measure how the epidemics spread geographically. Furthermore, we make all the transition parameters dependent on time so as to capture potential changes in the epidemic spread due to the effect of external factors such as containment measures. We also include the information of the number of tests performed as predictor for the infection parameters. We then use the master equation as probabilistic model to describe the evolution of the temporal process of the states and we focus on its first two-order moments by considering a local linear approximation. Finally we infer the corresponding parameters using a step-wise optimisation procedure which leads to the maximum likelihood estimate.

Title: Non Homogeneous Dynamic Bayesian Network Models

Speaker: Abdul Salam

Abstract: One of the main objectives of systems biology is to learn network topologies from gene expression time series. The ultimate goal is to infer the dependency between random variables in the form of a network. To deal with this task, the class of dynamic Bayesian network (DBNs) models have been widely applied. The essential assumption for DBNs is that the regulatory processes are homogenous, so that the interaction parameters are constant over time. However, this assumption is too restrictive for many real-world applications. To overcome this issue, non-homogenous dynamic Bayesian networks (NH-DBNs) are considered as the best alternatives. In this work, we applied the class of NH-DBNs models to infer the network structure from gene expression time series. Particularly, we will discuss the results for two types of gene networks, firstly, the yeast network (true structure of the network is known) and secondly, mTOR network (true structure of this network is unknown). In the presentation we will put the main focus on the mTOR network, as we currently struggle with the data analysis. All our network models are based on the assumption that measurements have been taken at equidistant time points. But this assumption is not fulfilled for the mTOR data, where after a stimulation of the system the measurements were taken after 0, 1 ,3, 5, 10, 15, 30, 45, 60 and 120 minutes.

Title: Sharp thresholds for Glauber dynamics percolation

Speaker: Rangel Baldasso

Abstract: Sharp threshold is a phenomena that characterizes abrupt change of behavior in a phase transition. In this talk, we prove that the two-dimensional model obtained by running Glauber dynamics up to some finite time yields a percolation model that presents a sharp threshold. The proof is based on special properties of a graphical construction of the model that allows us to pass from annealed to quenched measures. Based on a joint work with C. Alves, G. Amir, and A. Teixeira.

Title: A class of stick breaking models

Speaker: Deepan Basu

Abstract: (Joint work with Krishanu Maulik and Subhabrata Sen). We start with a white stick of unit length and for a uniformly chosen point, we color the left or right side black with certain probability functions of the distance of the chosen point from one end. We keep iterating this on the white part of the stick, and attempt at characterizing the distribution of the location of ’vanishing white point’ of the stick by the aforementioned function.

Title: Graph theoretical design strategies for tile-based DNA self-assembly

Speaker: Jo Ellis-Monaghan

Abstract: Recent advances in DNA self-assembly have resulted in increasingly sophisticated nanoscale wire-frame structures that can be modeled by graphs. These constructs serve emergent applications in biomolecular computing, nanoelectronics, biosensors, drug delivery systems, and organic synthesis. One construction method uses k-armed branched junction molecules, called tiles, whose arms are double strands of DNA with one strand extending beyond the other, forming a ‘sticky end’ at the end of the arm that can bond to any other sticky end with complementary Watson-Crick bases. A vertex of degree k in the target graph is formed from a k-armed tile, and joined sticky ends form the edges. We use graph theory to determine optimal design strategies for scientists producing these nanostructures. This includes computational complexity results, algorithms, and pragmatic approaches for special classes of graphs, as well as new mathematical theory and new graphs invariants.

Title: The contact process on random hyperbolic graphs

Speaker: Daniel Valesin

Abstract: We consider the contact process on the model of hyperbolic random graph, in the regime when the degree distribution obeys a power law with finite mean and infinite second moment. We show that the probability of non-extinction as the rate of infection goes to zero decays as a power law with an exponent that only depends on the power law exponent and which is the same as in the configuration model, suggesting some universality of this critical exponent. We also consider finite versions of the hyperbolic graph and prove metastability results, as the size of the graph goes to infinity. Joint work with Amitai Linker, Dieter Mitsche and Bruno Schapira.

Title: The weight-dependent random connection model

Speaker: Markus Heydenreich

Abstract: We investigate a large class of random graphs on the points of a Poisson process in d-dimensional space, which combine scalefree degree distributions and long-range effects. Every Poisson point carries an independent random weight and given weight and position of the points we form an edge between two points independently with a probability depending on the two weights and the distance of the points. This generalises many spatial random graph models. Our focus is on the question whether infinite components are recurrent or transient, and we demonstrate that the answer depends on the model parameters. In a plain version of the random connection model, where weights are ignored, we can even analyse the model at the phase transition point. Indeed, we obtain an infrared bound for the critical connectivity function if the dimension is sufficiently large or if the pair connection function has sufficiently slow decay. This is achieved through an adaptation of the percolation lace expansion for Poisson processes. Based on joint work with Peter Gracar, Remco van der Hofstad, Günter Last, Kilian Matzke, Christian Mönch, and Peter Mörters.

Title: Large deviation estimates for subsets of size conditioned Galton-Watson trees

Speaker: Daniel Willhalm

Abstract: We prove a Large Deviation Principle for the logarithmic number of subtrees of size conditioned Galton-Watson trees, provided that two assumptions about Large Deviation Principles being transferable are fulfilled. The proof is based on general large deviation techniques that are linked to conditioned Galton-Watson trees via so-called additive functionals.

Title: Functional CLT for persistent Betti numbers on point processes and networks

Speaker: Christian Hirsch

Abstract: Persistent Betti numbers form a key tool in topological data analysis as they track the appearance and disappearance of topological features in a sample. In this talk, we derive a goodness of fit test of point patterns and random networks based on the persistence diagram in large volumes. On the conceptual side, the tests rely on functional central limit theorems for the sub-level filtration in cylindrical networks and for bounded-size features of the Čech-complex of planar point patterns. The proof is based on methods from a recently developed framework for CLTs on point processes with fast decay of correlations. We analyze the power of tests derived from this statistic on simulated point patterns and apply the tests to a point pattern from an application context in neuroscience.

Title: On the law of the iterated logarithm and strong invariance principles in stochastic geometry

Speaker: Johannes Krebs

Abstract: The law of the iterated logarithm (LIL) dates back to the findings of Khinchin (1933) and Kolmogorov (1929). The LIL operates in between the law of large numbers and the central limit theorem and describes the order of fluctuations of a random walk, resp. an empirical process. Today's formulation is due to Hartman–Wintner (1940): Let $X_1,X_2,\dots$ be iid random variables with mean zero and unit variance, then $\limsup_{n\to\infty} \frac{\sum_{k=1}^n X_k}{\sqrt{2n \log\log n} } = 1 \quad a.s.$ In this talk we study the LIL and related strong invariance principles (SIP) in stochastic geometry for certain functionals $H$. On the domain $W_n = [-n^{1/d}/2, n^{1/d}/2]^d$ we observe a homogeneous Poisson or binomial process $X_n$. The LIL takes then the form $\limsup_{n\to\infty} \frac{ H(X_n) - \mathbb{E}[H(X_n) ] }{\sqrt{2n \log\log n} } = \sigma \quad a.s.$ where $\sigma^2>0$ is the limiting variance of $n^{-1/2} H(X_n)$. Strong invariance principles, describe the approximability of an empirical process by a Brownian motion. Using the Skorokhod embedding, we show that in the case of a one-dimensional stretched domain $H(X_n) - \mathbb{E}[H(X_n) ]$ can be approximated with a rescaled Brownian motion up to an accuracy of order $O_{a.s.}(n^{1/4} (\log n)^{1/2} (\log\log n)^{1/4} )$ in a Poisson setting. A similar result is valid in a binomial setting. As potential applications, we think of well-known functionals defined on the k-nearest neighbors graph and important functionals in topological data analysis such as the Euler characteristic and persistent Betti numbers.

Title: Voronoï percolation in the hyperbolic plane

Speaker: Benjamin Hansen

Abstract: We consider site percolation on Voronoï cells generated by a Poisson point process on the hyperbolic plane H2. Each cell is coloured black independently with probability p, otherwise the cell is coloured white. Benjamini and Schramm proved the existence of three phases: For p ∈ [0, pc] all black clusters are bounded and there is a unique infinite white cluster. For p ∈ (pc, pu), there are infinitely many unbounded black and white clusters. For p ∈ [pu, 1] there is a unique infinite black cluster and all white clusters are bounded. They also showed pu = 1 − pc. The critical values pc and pu depend on the intensity of the Poisson point process. We prove that pc tends to 1/2 as the intensity tends to infinity. This confirms a conjecture of Benjamini and Schramm.

Joint work with Tobias Müller.

Title: The Constrained-degree percolation model

Speaker: Bernardo N. B. de Lima

Abstract: In the Constrained-degree percolation model on a graph $(V,E)$ there are a sequence, $(U_e)_{e\in\E}$, of i.i.d. random variables with distribution $U[0,1]$ and a positive integer $k$. Each bond $e$ tries to open at time $U_e$, it succeeds if both its end-vertices would have degrees at most $k-1$. We prove a phase transition theorem for this model on the square lattice $\mathbb{L}^2$, as well on the d-ary regular tree. We also prove that on the square lattice the infinite cluster is unique in the supercritical phase. Joint work with R. Sanchis, D. dos Santos, V. Sidoravicius and R. Teodoro.

Title: Mini Course: Introduction to Positional Games

Speaker: Miloš Stojaković

Locations and Times:
Tue 18, 10.00-13.00, Room 5161.0222 (Bernoulliborg)
Wed 19, 13.00-16.00, Room 5161.0293 (Bernoulliborg)
Thu 20, 14.00-17.00, Room 5161.0151 (Bernoulliborg)

Abstract: Positional Game Theory provides a solid mathematical footing for a variety of two-player games of perfect information, usually played on discrete objects (like graphs), with a number of applications in other branches of mathematics and computer science. The field is just a few decades old, and it has experienced a considerable growth in recent years. Our goal is to introduce some basic concepts and notions, followed by recent results and numerous open problems.
The prerequisites include undergraduate knowledge of discrete mathematics and probability, and the lectures could be of interest to people with a wide range of backgrounds and different levels of seniority.

Title: Community structure in Networks - limits of learning

Speaker: Fiona Skerman

Abstract: Modularity is at the heart of the most popular algorithms for community detection. For a given network 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 network G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q*(G) ≤ 1.

1. "When is there Modularity from fluctuations in Random Graphs?" Guimera et al 2004 showed that the Erdös-Rényi random graph Gn,p with n vertices and edge-probability p can have surprisingly high modularity and that this should be taken into account when determining statistical significance of community structures in networks. Further, they predicted Gn,p to have modularity order (np)-1/3.

Our two key findings are that the modularity is 1 + o(1) with high probability (whp) for np up to 1 + o(1) and no further; and when np ≥ 1 and p is bounded below 1, it has order (np)−1/2 whp, in accord with a competing prediction by Reichardt and Bornholdt in 2006 based on spin glass methods.

2. Sampling sufficiency for determining modularity. We analyse when community structure of the underlying graph can be determined from observations of the network which we model by random sampling of the graph.

Joint work with Colin McDiarmid and based on the paper 'Modularity of Erdös-Rényi random graphs' arxiv.org/abs/1808.02243.

Title: Interacting diffusions on sparse random graphs

Speaker: Guilherme Reis

Abstract: We consider systems of diffusion processes whose interactions are described by a graph. For example, traditional mean-field interacting diffusions correspond to a complete interaction graph. In recent years some effort has been directed to understanding more general interactions. When the interaction graph is random, in the particular case of the Erdős–Rényi random graph, we show how the behavior of this particle system changes whether the mean degree of the Erdős–Rényi graph diverges to infinity or converges to a constant. In this talk we will focus on the case that the mean degree converges to a constant. In this case we prove a strong law of large numbers for the empirical measures. To achieve this we exploit the local weak convergence and a locality property of this system. Loosely speaking, the locality property states that information does not propagate too fast over the graph for this kind of particle system. This tool allow us to manage the dependencies of the system. Joint work with Roberto Imbuzeiro Oliveira.

Title: On projections of the supercritical contact process: uniform mixing and cutoff phenomenon

Speaker: Stein Andreas Bethuelsen

Abstract: In this talk I will present the findings in https://arxiv.org/abs/1810.06840. This paper concerns the supercritical contact process on general graphs and the study of the asymptotic properties of its projections onto finite subsets. We will see that, under minimal assumptions on the graph structure, such projections have a surprisingly strong temporal loss-of-memory property as soon as the infection rate is large enough. Furthermore, I will discuss certain relations between these results and similar findings for the projection of the 2d Ising model onto a line, as studied in https://arxiv.org/abs/1802.02059 (joint work with Diana Conache (TUM)). When time permits, I will also discuss a particular motivation for these two papers stemming from random walks on (dynamic) random environments.

Title: Loop-erased partitioning: two-point correlations on mean-field models

Speaker: Luca Avena

Abstract: We consider a certain random partitioning of the vertex set of an arbitrary graph that can be efficiently sampled using loop-erased random walks with killing. The related random blocks tend to cluster nodes visited by the random walk-with infinitesimal generator the graph Laplacian- on time scale 1/q, with q > 0 being a tuning parameter. We explore the emerging macroscopic structure by analyzing 2-point correlations. To this aim, we define an interaction potential between pair of vertices of a graph, as the probability that they do not belong to the same block of the random partition. This interaction potential can be seen as an affinity measure for “densely connected nodes” and capture well-separated communities in network models presenting non-homogenous landscapes. In this spirit, we compute the potential and its scaling limits on a complete graph and on a non-homogenous weighted version with community structures. For the latter we show a phase-transition for detectability as a function of the tuning parameter and the edge weights.

Joint work with ALEXANDRE GAUDILLIEĚRE, PAOLO MILANESI (Marselle) AND MATTEO QUATTROPANI (Rome)

Title: Local weak convergence for PageRank

Speaker: Nelly Litvak

Abstract: PageRank is a well-known algorithm for measuring centrality in networks. It was originally proposed by Google for ranking pages in the World-Wide Web. One of the intriguing empirical properties of PageRank is the so-called `power-law hypothesis': in a scale-free network the PageRank scores follow a power law with the same exponent as the (in-)degrees. Up to date, this hypothesis has been confirmed empirically and in several specific random graphs models. In contrast, in this talk we do not focus on one random graph model but investigate the existence of an asymptotic PageRank distribution, when the graph size goes to infinity, using local weak convergence. The local weak convergence is one of recent notions of graph limits, originally developed for undirected graphs. We will extend this notion to directed graphs and use this to prove the existence of an asymptotic PageRank distribution. As a result, the limiting distribution of PageRank can be computed directly as a function of the limiting object. This may help to identify general network structures in which the power-law hypothesis holds. We apply our results to the directed configuration model and continuous-time branching processes trees, as well as preferential attachment models.

This is a joint work with Alessandro Garavaglia (TU/e) and Remco van der Hofstad (TU/e)

Title: On the location of zeros of the independence polynomial for bounded degree graphs

Speaker: Guus Regts

Abstract: In this talk I will introduce the independence polynomial (a.k.a. the partition function of the hard-core model in statistical physics) and motivate the study of the location of its zeros by applications to statistical physics and theoretical computer science.

Along the way I will indicate how the theory of complex dynamical systems has been used to settle a conjecture of Alan Sokal on the location of the zeros of the independence polynomial for bounded degree graphs. I will end with some open problems.

Title: The discrete Gaussian free field on a compact manifold

Speaker: Alessandra Cipriani

Abstract: In this talk we aim at defining the discrete Gaussian free field (DGFF) on a compact manifold. Since there is no canonical grid approximation of a manifold, we construct a suitable random graph that replaces the square lattice Z^d in Euclidean space, and prove that the scaling limit of the DGFF is given by the manifold continuum Gaussian free field. Joint work with Bart van Ginkel (TU Delft).

Title: Optimizing constrained and unconstrained network structures

Speaker: Clara Stegehuis

Abstract: Subgraphs contain important information about network structures and their functions. We investigate the presence of subgraphs in inhomogeneous random graphs with infinite-variance degrees. We introduce an optimization problem which identifies the dominant structure of any given subgraph. The unique optimizer describes the degrees of the vertices that together span the most likely subgraph and allows us count and characterize all subgraphs.

We then show that this optimization problem easily extends to other network structures, such as clustering, which expresses the probability that two neighbors of a vertex are connected. The optimization problem is able to find the behavior of clustering in a wide class of random graph models.

Title: k-regular subgraphs near the k-core threshold of a random graph

Speaker: Dieter Mitsche

Abstract: We prove that $G_{n,p}$ whp has a k-regular subgraph if $c$ is at least $e^{-\Theta(k)}$ above the threshold for the appearance of a subgraph with minimum degree at least k; i.e. an non-empty k-core. In particular, this pins down the threshold for the appearance of a k-regular subgraph to a window of size $e^{-\Theta(k)}$.

Joint work with Mike Molloy and Pawel Pralat.

Title: Truncated long-range percolation on oriented graphs

Speaker: Bernardo N. B. de Lima

Abstract: We consider different problems within the general theme of long-range percolation on oriented graphs. Our aim is to settle the so-called truncation question, described as follows. We are given probabilities that certain long-range oriented bonds are open; assuming that the sum of these probabilities is infinite, we ask if the probability of percolation is positive when we truncate the graph, disallowing bonds of range above a possibly large but finite threshold. We give some conditions in which the answer is affirmative. We also translate some of our results on oriented percolation to the context of a long-range contact process.

Joint work with A. Alves, A. van Enter, M. Hilário and D. Valesin

Title: A generator approach to stochastic monotonicity and propagation of order

Speaker: Moritz Schauer

Abstract: We study stochastic monotonicity and propagation of order for Markov processes with respect to stochastic integral orders characterized by cones of functions satisfying Φ f ≥ 0 for some linear operator Φ.

We introduce a new functional analytic technique based on the generator A of a Markov process and its resolvent. We show that the existence of an operator B with positive resolvent such that Φ A - B Φ is a positive operator for a large enough class of functions implies stochastic monotonicity. This establishes a technique for proving stochastic monotonicity and propagation of order that can be applied in a wide range of settings including various orders for diffusion processes with or without boundary conditions and orders for discrete interacting particle systems.

Joint work with Richard Kraaij

Title: Solvable models from the ergodic point of view

Speaker: Evgeny Verbitskiy

Abstract: In this review talk, I will discuss a link between solvable models of statistical mechanics (dimers, spanning trees, sandpiles) and algebraic dynamical systems. Even though the question about the existence of such a link was raised almost two decades ago, this problem remained largely inaccessible. The development of the theory of symbolic covers of algebraic dynamical systems has only recently provided a suitable framework.

Title: Building your path to escape from home

Speaker: Rodrigo Ribeiro

Abstract: We consider a random walker in a dynamic random environment given by a system of independent simple symmetric random walks. We will describe some perturbative results that can be obtained via multi-scale analysis, including regimes of high density, low density and large drift on particles. Based on joint works with Oriane Blondel, Marcelo Hilário, Frank den Hollander, Vladas Sidoravicius and Augusto Teixeira.

Title: Random walk on random walks

Speaker: Renato Santos

Abstract: In this talk we introduce one of the simplest conceivable model of a random walk that can modify its domain. The model works as follows: before every walker step, with probability p a new leaf is added to the vertex currently occupied by the walker. We discuss questions related to the walker such as the speed it moves away from its initial position and how its neighborhood may looks like asymptotically. This is a joint work with D. Figueiredo, G. Iacobellu, R. Olivera and B. Reed.

Title: Law of large numbers and LDP for the Random Walk in the Cooling random Environment