Groningen Probability and Statistics Seminar
This seminar is organized by the Probability and Statistics group of the University of Groningen, whose members are broadly interested in Statistics, Probability, Discrete Mathematics, Convex Geometry and the interactions of these fields.
The audience consists typically of Gilles Bonnet, Serte Donderwinkel, Aernout van Enter, Marco Grzegorczyk Wim Krijnen, Tobias Müller, Réka Szabó, Pieter Trapman, the PhD students of our group (John Astoquillca Aguilar, Leah Dijkshoorn, Maddalena Dona, Joseph Gordon, Elaine Herrera, Ruben IJpma, Matthias Irlbeck, Albert Šilvans), Master students and occasionally external guests.
To the attention of speakers who give an online talk: We use the software Zoom. The link will be sent to you some time before the talk. If, a few hours ahead, you still did not receive it, simply write to Gilles. Please connect 5 minutes prior to the talk so that we can test the audio, video and screen sharing. The audience gathers in one room where the talk will be streamed. Feel free to share the link with other people who might be interested. Unless requested by the speaker, the talk is not recorded. Talks last up to 45 minutes, with additional time for discussion. The beginning should be understandable to Master students. Please send a title at your earliest convenience, and an abstract at least 10 days in advance (for announcement purposes).
Future talks are announced below, in a Google calendar, as well as per email. To be added to the mailing list, to suggest a speaker, or for any other question related to the seminar, please contact Réka or Gilles.
Future Talks
| March 11, 2025
13:00-14:00 Room BB293 | Maddalena Donà
(Rug) | The real-time growth rate of stochastic epidemics on random intersection graphs |
|---|---|---|
| March 25, 2025
13:00-14:00 Room BB293 | Natalia Cardona-Tobón
(Universidad Nacional de Colombia) | TBA |
| April 15, 2025
13:00-14:00 Room BB293 | Michel Mandjes
(UvA) | TBA |
| May 20, 2025
13:00-14:00 Room BB293 | Dieter Mitsche
(University of Santiago, Chile) | TBA |
| June 3, 2025
13:00-14:00 Room BB293 | Alessandra Caraceni
(SNS Pisa) | TBA |
| September 30, 2025
13:00-14:00 Room TBA | Frank den Hollander
(Leiden) | TBA |
Past Talks
| February 25, 2025
13:00-14:00 | Nicolas Broutin
(LPSM Sorbonne) | The scaling limit of critical hypercube percolation |
|---|---|---|
| February 11, 2025
13:00-14:00 | Ivan Kryven
(Utrecht) | Branching process solution for conservation PDEs |
| January 28, 2025
13:00-14:00 | Matthias Irlbeck
(RUG) | Poisson-Voronoi percolation in high dimensions |
| December 17, 2025
13:00-14:00 | Jhon Astoquillca Aguilar
(RUG) | Percolation on the Stationary Measures of the Voter Model with Stirring |
| December 10, 2024
13:00-14:00 | Dirk Husmeier
(Glasgow) | Statistical emulation and uncertainty quantification in cardiovascular disease modelling |
| December 3, 2024
13:00-14:00 | Ronald Meester
(VU Amsterdam) | An epistemic interpretation of the posterior likelihood ratio distribution |
| November 26, 2024
13:00-14:00 | Marta Milewska
(CWI) | SIR Epidemics on Dynamically Converging Graphs: The Role of Local Time-Marked Union Convergence |
| November 19, 2024
13:00-14:00 | Gábor Pete
(Rényi, Budapest) | Non-amenable Poisson Zoo |
| November 12, 2024
13:00-14:00 | Barbara Dembin
(IRMA Strasbourg) | Supercritical sharpness for Voronoi percolation |
| October 22, 2024
13:00-14:00 | Márton Balázs
(Bristol) | Road layout in the KPZ class |
| October 15, 2024
13:00-14:00 | Markus Schepers
(Mainz) | Statistical inference for network data |
| October 8, 2024
13:00-14:00 | Lucas R. de Lima
(São Paulo) | First-passage percolation on random geometric graphs: Asymptotic shape, speed of convergence and its geodesics |
| September 24, 2024
13:00-14:00 | Marco Grzegorczyk
(RUG) | The Flexibility of Gaussian Bayesian Networks |
| September 17, 2024
13:00-14:00 | Augusto Teixeira
(IMPA) | Two-neighbour bootstrap percolation is local |
| July 16, 2024
11:00-12:00 | Moumanti Podder
(IISER Pune India) | A model of social learning on rooted regular trees |
| June 25, 2024
13:00-15:00 | Andrew Packer / Jordan Ekelenburg
(RUG) | Getting My Teeth into Survival Analysis / Robust Methods For Linear Regression |
| June 11, 2024
13:00-14:00 | Darragh Spillane
(RUG) | A Survey of Mortality Modeling Techniques |
| June 18, 2024
13:00-14:00 | Darren Zammit
(RUG) | Unraveling Evolutionary Histories Through Statistics |
| June 4, 2024
13:00-14:00 | Tanguy Lions
(ENS Paris) | Large genus random hyperbolic surfaces with many cusps |
| May 28, 2024
13:00-14:00 | Rob van den Berg
(CWI, Amsterdam) | An OSSS-type inequality for uniformly drawn subsets of fixed size |
| May 21, 2024
13:00-14:00 | Matthias Schulte
(Technische Universität Hamburg) | First passage percolation on Erdős-Rényi graphs with general weights |
| May 14, 2024
13:00-14:00 | Ivailo Hartarsky
(TU Wien) | Catalan percolation |
| May 7, 2024
13:30-14:30 | Jhon Astoquillca Aguilar
(RUG) | The voter model on dynamic random environments |
| April 23, 2024
13:00-14:00 | Frank Ball
(University Of Nottingham) | Epidemics on networks with preventive rewiring |
| April 16, 2024
13:00-14:00 | Moritz Otto
(Aarhus) | Poisson approximation for determinantal score functionals |
| April 9, 2024
13:00-14:00 | Hugo Vanneuville
(Université Grenoble Alpes) | A new proof of exponential decay for Bernoulli percolation |
| March 26, 2024
13:00-14:00 | Laure Marêché
(IRMA, Strasbourg) | Limit theorems for a self-repelling random walk |
| March 12, 2024
13:00-14:00 | Maaike Los
(RUG) | On the Graph Theory of Majority Illusions: Theoretical Results and Computational Experiments |
| March 19, 2024
13:00-14:00 | Pim van der Hoorn
(TU Eindhoven) | Spatial inhomogeneous random graphs: limits and clustering |
| March 5, 2024
13:00-14:00 | Raphaël Lachièze-Rey
(Paris cité) | Optimal transport and matching of point processes |
| February 27, 2024
13:00-14:00 | Serte Donderwinkel
(Groningen) | Counting graphic sequences |
| February 20, 2024
13:00-14:00 | Tomas Kaiser
(University of West Bohemia, Plzen) | Independent transversals in graphs |
| February 13, 2024
13:00-14:00 | Oriol Serra
(UPC Barcelona) | Vertex bisection of random regular graphs |
| January 9, 2024
13:00-14:00 | Cristina Toninelli
(Paris Dauphine) | Fredrickson-Andersen 2-spin facilitated model: sharp threshold |
| December 19, 2023
13:00-14:00 | Pierre Charbit
(Paris Cité) | Chromatic Number and Clique Number for Directed Graphs |
| December 12, 2023
13:00-14:00 | Christoph Thäle
(Bochum) | Random (beta) polytopes |
| November 28, 2023
13:00-14:00 | Brett Kolesnik
(Oxford) | Rapidly sampling Coxeter tournaments |
| November 21, 2023
13:00-14:00 | Hrvoje Planinic
(Zagreb) | Extremes of stationary heavy-tailed time series |
| November 7, 2023
13:00-14:00 | Pierre Calka
(Rouen) | Fluctuations of random polytopes in smooth convex bodies |
| November 14, 2023
13:00-14:00 | Olivier Devillers
(Inria, France) | Walking in random Delaunay triangulations |
| October 31, 2023
13:00-14:00 (Colloquium) | Matej Stehlik
(Irif, Paris) | Criticality in Sperner’s lemma |
| October 17, 2023
13:00-14:00 | Nicolas Chenavier
(Calais) | Maximum Composite Likelihood Estimators for a Brown-Resnick random field in infill |
| October 10, 2023
13:00-14:00 | Pieter Trapman
(RUG) | Maximizing the size of a giant |
| July 11, 2023
14:00-15:00 BB 222 (Colloquium) | Zakhar Kabluchko
(University of Münster) | Angles of random simplices and face numbers of random polytopes |
| June 20, 2023
16:00-17:00 (Colloquium) | Maksim Zhukovskii
(University of Sheffield) | Spanning regular subgraphs of random graphs: sharp thresholds |
| May 30, 2023 14:00-15:00 | Daniel Valesin
(Warwick) | Degree-penalised contact processes |
| May 16, 2023 14:00-15:00 | Erik Broman
(Gothenburg / Chalmers) | Cover times and the Random Walk Loop Soup |
| May 2, 2023 14:00-15:00 | Remco van der Hofstad
(Utrecht) | It's hard to kill fake news |
| Apr 18, 2023 14:00-15:00 | Christophe Garban
(Lyon) | Surface law and charge rigidity for the Coulomb gas on $Z^d$ |
| Apr 4, 2023 14:00-15:00 | Daniel Willhalm
(Groningen) | Lower large deviations for geometric functionals in sparse and dense regimes |
| Mar 21, 2023 14:00-15:00 | Marie Albenque
(Université Paris Cité) | Sign clusters in the Infinite-Ising weighted triangulations |
| Mar 14, 2023 14:00-15:00 | David Coupier
(Mine Télécom Nord Europe) | Asymptotic directions of infinite paths in the hyperbolic Radial Spanning Tree |
| Feb 21, 2023 14:00-15:00 | Frank Redig
(TU Delft) | Gaussian concentration and uniqueness of Gibbs measures |
| Feb 7, 2023 14:00-15:00 | Matthew Kwan
(IST Austria) | The rank of random graphs |
| Jan 24, 2023 14:00-15:00 | Rineke Verbrugge
(University of Groningen) | Zero-one laws for provability logic (and other modal logics) |
| Jan 17, 2023 14:00-15:00 | Zakhar Kabluchko
(University of Münster) | Totally unbalanced random polytopes: An extremal case of spherically symmetric random polytopes. |
| Dec 15, 2022 15:00-16:00 | Sophie Huiberts
(Columbia University, NYC) | Smoothed analysis of projected polyhedra |
| Nov 29, 2022 14:00-15:00 | Jimmy He
(MIT) | Shift invariance of half space integrable models |
| Nov 15, 2022 14:00-15:00 | Régine Marchand
(Lorraine university) | Growth of the contact process in a (fixed) random environment. |
| Oct 18, 2022 14:00-15:00 | Jakub Kwaśny
(AGH University) | Neighbour-distinguishing edge colourings of graphs |
| Oct 13, 2022 15:00-16:00 | Danila Cherkashin
(IMI BAS) | Random approach to a proper coloring of 3-graphs |
| Jul 20, 2022 16:00-17:00 | Valentin Feray
(Nancy) | The theory of permutons and a universality result for pattern avoiding permutations |
| Jul 12, 2022 16:00-17:00 | Daniel Willhalm
(Groningen) | Limit theory of sparse random geometric graphs in high dimensions |
| Jun 22, 2022 16:00-17:00 | Dan Romik
(University of California, Davis) | The oriented swap process, exclusion processes and random matrix theory |
| Jun 15, 2022 16:00-17:00 | Nicholas Fraiman
(UNC) | Approximating the Potts model on expander graphs |
| Jun 1, 2022 (!)15:00-16:00(!) | Jeff Kahn
(Rutgers University) | Linear cover time is exponentially unlikely |
| May 25, 2022 16:00-17:00 | Johan Tykesson
(Chalmers) | Phase transitions in the fractal cylinder process |
| May 18, 2022 16:00-17:00 | Konstantinos Panagiotou
(Munich) | Asymptotic enumeration and limit laws for multisets |
| May 11, 2022 16:00-17:00 | Matej Stehlik
(IRIF) | Edge-critical subgraphs of Kneser graphs |
| May 4, 2022 | Andreas Goebel
(University of Potsdam) | Sampling and approximation algorithms for Gibbs point processes |
| Apr 20, 2022 | Daniel Ahlberg (Stockholm University) | Multi-colour competition on a cycle |
| Apr 5, 2022 16:00-17:00 | Nicola Turchi
(University of Milano-Bicocca) | The slicing problem via random polytopes |
| Mar 29, 2022 16:00-17:00 | Sjoerd Dirksen
(Universiteit Utrecht) | Sharp estimates on random hyperplane tessellations |
| Mar 22, 2022 16:00-17:00 | Matthias Reitzner
(University of Osnabrück) | Convex Hulls of Random Points |
| Mar 15, 2022 16:00-17:00 | Xinyi Li
(Peking University) | Shape theorem and surface fluctuation for Poisson cylinders |
| Mar 8, 2022 16:00-17:00 | Suman Chakraborty
(Eindhoven University of Technology) | Sparse random graphs with many triangles |
| Mar 1, 2022 16:00-17:00 | Teun Verstraaten
(University of Gronigen) | Cycles in Mallows random permutations |
| Feb 25, 2022 16:00-17:00 | Ron Peled
(Tel Aviv University) | Packing squares on the square lattice |
| Feb 11, 2022 16:00-17:00 | Mihyun Kang
(Graz University of Technology) | Local limits of sparse random planar graphs |
| Feb 4, 2022 16:00-17:00 | Malwina Luczak
(University of Melbourne) | Long-term concentration of measure and cut-off |
| Jan 28, 2022 16:00-17:00 | Daniel Rosen
(Ruhr University Bochum) | Fluctuations of lambda-geodesic Poisson hyperplanes in hyperbolic space |
| Jan 14, 2022 16:00-17:00 | Carina Betken
(Ruhr University Bochum) | Central limit theory for Poisson cylinder processes |
| Dec 17, 2021 16:00-17:00 | Thomas Godland
(University of Münster) | Beta-star polytopes and hyperbolic stochastic geometry |
| Dec 10, 2021 16:00-17:00 | Yu Liu
(Peking University) | Sharpness of phase transition for Voronoi percolation in hyperbolic space |
| Nov 26, 2021 16:00-17:00 | Gilles Bonnet
(University of Groningen) | Combinatorial Diameter of Random Polytopes |
| Nov 19, 2021 16:00-17:00 | Paweł Prałat
(Ryerson University) | Semi-random process |
| Nov 12, 2021 16:00-17:00 | Steven Kelk
(Department of Data Science and Knowledge Engineering (DKE), Maastricht University) | Convex characters, algorithms and matchings |
| Oct 22, 2021 16:00-17:00 | D. Yogeshwaran
(Indian Statistical Institute, Bangalore) | Poisson process approximation under stabilization and Palm coupling |
| Oct 8, 2021 16:00-17:00 | Dieter Mitsche
(Institut Camille Jordan UMR CNRS-UNS) | The jump of the clique chromatic number of random graphs |
| Oct 1, 2021 16:00-17:00 | Elliot Paquette
(McGill University) | The threshold for simple-connectedness in hypercube percolation |
| May 28, 2021 16:00-17:00 | Eric Cator
(Radboud University) | Contact process on low-rank graphs |
| May 28, 2021 16:00-17:00 | Piet Lammers
(IHES Paris) | Height function delocalisation on cubic planar graphs |
| May 21, 2021 16:00-17:00 | Serte Donderwinkel
(University of Oxford) | What do the strongly connected components of a large directed graph with i.i.d. degree tuples look like? |
| May 14, 2021 16:00-17:00 | Balázs Ráth (Budapest University of Technology) | Percolation of worms |
| Apr 30, 2021 16:00-17:00 | Jun Yu
(Umeå University) | Statistical learning and inference for spatiotemporal data |
| Apr 16, 2021 16:00-17:00 | Xavier Pérez Giménez
(University of Nebraska-Lincoln) | Perfect matchings in the random bipartite geometric graph |
| Apr 9, 2021 16:00-17:00 | Aernout van Enter
(University of Groningen) | Dyson models with random boundary conditions |
| Mar 19, 2021 13:15-14:15 | Guillem Perarnau (Universitat Politècnica de Catalunya) | Extremal stationary values for random digraphs |
| Feb 25, 2021 17:00-18:00 | Tobias Müller
(University of Groningen) | Percolation on hyperbolic Poisson-Voronoi tessellations |
| Feb 23, 2021 13:15-14:15 | Christian Hirsch
(University of Groningen) | Maximum likelihood estimation in stochastic channel models |
| Feb 12, 2021 16:00-17:00 | Victor Bernal
(University of Groningen) | Improved network reconstruction with shrinkage-based Gaussian graphical models |
| Jan 22, 2021 16:00-17:00 | Luca del Core
(University of Groningen) | Stochastic modelling of COVID-19 spread in Italy |
| Jan 8, 2021 16:00-17:00 | Abdul Salam
(University of Groningen) | Non Homogeneous Dynamic Bayesian Network Models |
| Dec 11, 2020 16:00-17:00 | Rangel Baldasso
(University of Leiden) | Sharp thresholds for Glauber dynamics percolation |
| Nov 27, 2020 16:00-17:00 | Deepan Basu
(University of Groningen) | A class of stick breaking models |
| Oct 23, 2020 16:00-17:00 | Jo Ellis-Monaghan
(University of Amsterdam) | Graph theoretical design strategies for tile-based DNA self-assembly |
| Oct 09, 2020 16:00-17:00 | Daniel Valesin
(University of Groningen) | The contact process on random hyperbolic graphs |
| Sep 25, 2020 16:00-17:00 | Markus Heydenreich
(LMU Munich) | The weight-dependent random connection model |
| Sep 18, 2020 16:00-17:00 | Daniel Willhalm
(University of Groningen) | Large deviation estimates for subsets of size conditioned Galton-Watson trees |
| Sep 04, 2020 16:00-17:00 | Christian Hirsch
(University of Groningen) | Functional CLT for persistent Betti numbers on point processes and networks |
| Apr 20, 2020 14:00-15:00 | Leandro Chiarini
(IMPA/Utrecht) | TBA |
| Apr 02, 2020 16:00-17:00 | Johannes Krebs
(TU Braunschweig) | On the law of the iterated logarithm and strong invariance principles in stochastic geometry |
| January 23, 2020 Room 5161.0293 (Nijenborgh 4) 11:00-12:00 | Benjamin Hansen
(University of Groningen) | Voronoï percolation in the hyperbolic plane |
| September 25, 2019 16:00-17:00 | Bernardo N. B. de Lima
(Federal University of Minas Gerais) | The Constrained-degree percolation model |
| June 18-20, 2019 | Miloš Stojaković
(Novi Sad) | Mini Course: Introduction to Positional Games |
| June 5, 2019 Room 5161.0267 11:00 - 12:00 | Fiona Skerman
(Masaryk) | Community structure in Networks - limits of learning |
| March 21, 2019 Room 5161.0041B 14:00 - 15:00 | Guilherme Reis
(Bahia-UFBA) | Interacting diffusions on sparse random graphs |
| February 28, 2019 Room 5161.0289 14:00 - 15:00 | Stein Andreas Bethuelsen
(Stavanger) | On projections of the supercritical contact process: uniform mixing and cutoff phenomenon |
| December 12, 2018 Room 5172.0804 15:00 - 16:00 | Luca Avena
(Leiden) | Loop-erased partitioning: two-point correlations on mean-field models |
| November 21, 2018 Room 5173.0176 (Linnaeusborg) 15:00 - 16:00 | Guus Regts
(Amsterdam) | On the location of zeros of the independence polynomial for bounded degree graphs |
| November 7, 2018 Room 5161.0289 14:00 - 15:00 | Alessandra Cipriani
(Delft) | The discrete Gaussian free field on a compact manifold |
| October 24, 2018 Room 5111.0006 15:00-16:00 | Clara Stegehuis
(Eindhoven) | Optimizing constrained and unconstrained network structures |
| September 19, 2018 Room 5173.0045 (Linnaeusborg) 15:30 - 16:30 | Dieter Mitsche
(Nice) | k-regular subgraphs near the k-core threshold of a random graph |
| June 20, 2018 Room 5161.0222 11:00 - 12:00 | Bernardo N. B. de Lima
(Federal University of Minas Gerais) | Truncated long-range percolation on oriented graphs |
| June 18, 2018 Room 5161.0165 15:00 - 16:00 | Moritz Schauer
(Leiden) | A generator approach to stochastic monotonicity and propagation of order |
| April 23, 2018 Room 5161.0293 16:00 - 17:00 | Evgeny Verbitskiy
(Leiden) | Solvable models from the ergodic point of view |
| March 15, 2018 Room 5115.0020 11:00-12:00 | Rodrigo Ribeiro
(IMPA) | Building your path to escape from home |
| February 16, 2018 Room 5161.0222 15:00-16:00 | Renato Santos
(Weierstrass Institute) | Random walk on random walks |
| February 1, 2018 Room 5161.0293 16:00 - 17:00 | Conrado Costa
(Leiden) | Law of large numbers and LDP for the Random Walk in the Cooling random Environment |
| January 24, 2018 Room 5161.0222 16:00 - 17:00 | Daniel Valesin
(Groningen) | Monotonicity for multi-range percolation on oriented trees |
Speaker: Frank den hollander
Speaker: Alessandra Caraceni
Speaker: Michel Mandjes
Speaker: Natalia Cardona-Tobón
Speaker: Dieter Mitsche
Abstract: TBA
Title: The real-time growth rate of stochastic epidemics on random intersection graphsBA
Speaker: Maddalena Donà
Abstract: In this talk we examine the growth rate of SIR (Susceptible Infectious-Recovered) epidemics with general infectious period distribution on random intersection graphs. This type of graph is characterized by the presence of cliques (fully connected subgraphs). We study epidemics on random intersection graphs with a mixed Poisson degree distribution and show that in the limit of large population sizes the number of infected individuals grows exponentially during the early phase of the epidemic, as is generally the case for epidemics on asymptotically unclustered networks. The Malthusian parameter is shown to satisfy a variant of the classical Euler-Lotka equation. To obtain these results we construct a coupling of the epidemic process and a continuous-time multitype branching process, where the type of an individual is (essentially) given by the length of its infectious period. Asymptotic results are then obtained via an embedded single-type Crump-Mode-Jagers branching process.
This talk is based on joint work with Dr. Carolina Fransson.
Title: The scaling limit of critical hypercube percolation
Speaker: Nicolas Broutin
Abstract: I will talk about the critical phase of bond percolation on the Hamming hypercube {0,1}^m, and more precisely of the scaling limit of the large connected components. We will see that the limit is the same for critical Erdős-Rényi random graphs, which is much easier to study. This is based on a joint work with Arthur Blanc-Renaudie and Asaf Nachmias.
Title: Branching process solution for conservation PDEs
Speaker: Yvan Kryven
Abstract: In this talk we will see how a simple branching process can be used to ’solve’ a partial differential equation. Since the appearance of the Feynman-Kac formula, many parabolic partial differential equations have been linked to Brownian motion. These results build on the fact that the diffusion process can be represented in two ways: continuously, using the Laplace operator, and discretely, as a random walk. We show how to write a similar type of formula but for a hyperbolic setting by considering a conservation PDE with a polynomial nonlinearity: u_t + F(u)u_x = 0. The key innovation is that, unlike in the parabolic case, the solution is represented using a branching process instead of a random walk. This process has independent and identically distributed offspring, and, in some cases, its criticality can even be mapped to the blow-up of the PDE solution. The proofs are simple and mostly use combinatorial arguments. At the end of the talk, we will also see a connection to a family of Smoluchowski-like coagulation processes as a side result.
Based on joint work with Jochem Hoogendijk, arxiv.org/pdf/2310.11338, and the side-result on work also with Camilo Schenone, https://arxiv.org/pdf/2401.12844.
Title: Poisson-Voronoi percolation in high dimensions
Speaker: Matthias Irlbeck
Abstract: We consider a Poisson point process with constant intensity in $ \mathbb{R}^d $ and independently color each cell of the resulting random Voronoi tessellation black with probability $ p $. The critical probability $ p_c(d) $ is the value for $ p $ above which there exists almost surely an unbounded black component and almost surely does not for values below. In this talk I aim to give an overview of the model and sketch a proof that $ p_c(d)=(1+o(1)) e d^{-1}2^{-d} $, as $ d\to\infty $. We also obtain the corresponding result for site percolation on the Poisson-Gabriel graph, where $ p_c(d)=(1+o(1))2^{-d} $.
Title: Percolation on the Stationary Measures of the Voter Model with Stirring
Speaker: Jhon Astoquillca Aguilar
Abstract: The voter model is a classical framework in the study of interacting particle systems. While it originated as a tool for studying opinion dynamics, it has found applications across disciplines such as statistical physics, mathematics, sociology, computer science, and neuroscience. Over time, the model has been extended in various ways to better capture complex real-world phenomena. One such extension is the voter model with stirring, which introduces additional dynamics to the classical voter model by allowing neighboring voters to exchange opinions at a rate called the stirring parameter.
This talk focuses on the stationary measures of voter models on the Euclidean lattice and their geometric properties, particularly examining percolation phenomena. We show that the family of (extremal) stationary measures exhibits a non-trivial percolation phase transition for large stirring parameter. Furthermore, as the stirring parameter approaches infinity, the critical density of this phase transition converges to the critical density for independent Bernoulli site percolation. Based on ongoing work with Réka Szabó and Daniel Valesin.
Title: Statistical emulation and uncertainty quantification in cardiovascular disease modelling
Speaker: Dirk Husmeier
Abstract: Pulmonary hypertension, i.e. high blood pressure in the lungs, is a serious medical condition that can damage the right ventricle of the heart and ultimately lead to heart failure. Standard diagnostic procedures are based on right-heart catheterization, which is an invasive technique that can potentially have serious side effects. Recent methodological advancements in fluid dynamics modelling of the pulmonary blood circulation system promise to mathematically predict the blood pressure based on non-invasive measurements of the blood flow, which would no longer require catheterization. However, in order for these alternative techniques to be applicable in the clinic, patient-specific model calibration and parameter estimation are needed, and the computational costs of repeated forward simulations as part of an iterative numerical optimisation or sampling scheme constitute a serious bottleneck for their practical use as real time digital twins in the clinic. Emulation is a common tool for overcoming this issue, yet an extensive investigation into the benefits, trade-offs, and limitations is warranted. In the present talk, I will give an overview of alternative emulation strategies for haemodynamics models of the pulmonary circulation, based on Gaussian processes, polynomial chaos expansions and physics-informed neural networks. Starting from a reduction of the parameter space of the models via global sensitivity analysis, the alternative emulation strategies are compared in both forward emulation on test data, as well as in their ability to infer the critical biophysical parameters in the inverse problem. The talk will also discuss the potential benefit of signal dimension reduction via principal component analysis.
Title: An epistemic interpretation of the posterior likelihood ratio distribution
Speaker: Ronald Meester
Abstract: Often the expression of a likelihood ratio involves model parameters. This fact prompted many researchers to argue that a likelihood ratio should be accompanied by a confidence interval, as one would do when estimating parameters. We first argue against this, based on our view of the likelihood ratio as a function of our knowledge of the model parameters, rather than being a function of the
parameters themselves. There is, however, another interval that can be constructed, and which has been introduced in the literature. This is the interval obtained upon sampling from the so-called
‘posterior likelihood ratio distribution’, after removing, say, the most extreme 5% of a sample from this distribution. Although this construction appears in the literature, its interpretation remained unclear, as explicitly acknowledged in the literature. We provide an interpretation: the posterior likelihood ratio distribution tells us which likelihood ratios we can expect if we were to
obtain more information. As such, it can play a role in decision making procedures, for instance about the question whether or not it is worthwhile to try to obtain more data. The posterior likelihood ratio distribution has no relevance for the evidential value of the current data with our current knowledge. We illustrate all this with a number of examples.
Title: SIR Epidemics on Dynamically Converging Graphs: The Role of Local Time-Marked Union Convergence
Speaker: Marta Milewska
Abstract: This talk examines the spread of SIR (Susceptible-Infected-Recovered) epidemics on dynamic random graphs, introducing a novel framework of dynamic local convergence. In static settings, local convergence is a well-established concept that provides insights into many graph properties, such as clustering and the existence of a giant component. Recent studies have also linked local convergence to epidemic behavior on static graphs. Building on these findings, we extend the analysis to dynamic settings, where edges appear and disappear over time. We begin by defining local convergence for dynamic graphs — the dynamic local convergence - and then highlight key differences and challenges that arise in the dynamic context compared to the static one. Specifically, we provide an intuitive explanation of why the dynamic case requires a form of convergence that is stronger than dynamic local convergence alone. We proceed by rigorously defining this stronger notion of convergence and demonstrate how it allows us to draw conclusions about the relationship between epidemic progression on a dynamic graph and its limit.
Title: Non-amenable Poisson Zoo
Speaker: Gábor Pete
Abstract: Take an infinite Cayley graph $\Gamma$, a probability measure $\nu$ on rooted finite connected subsets, called lattice animals, and place iid Poisson($\lambda$) independent copies of them at each vertex. This is the Poisson Zoo model, introduced by Ráth and Rokob (2022). It is easy to see that if the expected volume of the animals wrt $\nu$ is infinite, then the whole $\Gamma$ is covered for any $\lambda>0$; if the second moment of the volume is finite, then for small enough $\lambda$ the union of the animals has only finite clusters, while for $\lambda$ large enough there are also infinite clusters. In joint work with Sándor Rokob, we show that:
1. If $\Gamma$ is a free product, then for ANY $\nu$ with an infinite second but finite first moment and any $\lambda>0$, there will be infinite clusters, despite having arbitrarily low total density.
2. The same result holds for ANY nonamenable $\Gamma$, when the lattice animals are worms: simple random walk trajectories of random length.
For me, the main motivation for this work is that the Poisson Zoo might yield interesting constructions of Factor of IID percolations with low density infinite clusters, and thus could be relevant for questions in measurable group theory: Gaboriau's fixed price conjecture, and a quantitative version of the Chifan-Ioana indistinguishability theorem.
Title: Supercritical sharpness for Voronoi percolation
Speaker: Barbara Dembin
Abstract: Consider a Poisson point process $\eta$ of intensity 1 on $\mathbb R^d$. We associate to each point $x\in\eta$ its cells as the set of points in $\mathbb R ^d$ closer to $x$ than any other point in $\eta$. This defines the so-called Voronoi tessellation. We add a second level of randomness by coloring each cell independently with probability $p$ in black. We can prove that there exists a non trivial $p_c(d)$ such that almost surely for any $p>p_c(d)$ there exists an infinite black cluster. We prove here that the supercritical phase is well-behaved in the sense that for every $p>p_c(d)$ local uniqueness of macroscopic clusters happens with high probability. As a consequence, truncated connection probabilities decay exponentially fast and percolation happens on sufficiently thick 2D slabs. This is the analogue of the celebrated result of Grimmett \& Marstrand for Bernoulli percolation and serves as the starting point for renormalization techniques used to study several fine properties of the supercritical phase.
Title: Road layout in the KPZ class
Speaker: Márton Balázs
Abstract: In this talk I will be after a model for road layouts. Imagine a Poisson process on the plane for start points of cars. Each car picks an independent random direction and goes straight that way for some distance. I will start with showing that the origin (my house, that is) will see a lot of car traffic within an arbitrary small distance.
Which is not what we find in the real world out there, why? The answer is of course coalescence of paths in the random environment provided by hills and other geographic or societal obstacles. This points us towards first passage percolation (FPP), expected to be a member of the KPZ universality class. Due to lack of results for FPP, instead we built our model in exponential last passage percolation (LPP), known to be in the KPZ class. I will introduce LPP, then explain how to construct our road layout model in LPP, and what phenomena we can prove about roads and cars in this model using results from the LPP literature.
Title: Statistical inference for network data
Speaker: Markus Schepers
Abstract: Generative probabilistic models for network data have become essential tools for understanding complex systems. Several distinct frameworks have emerged from different fields over the years, including Graphical Models (GMs), Exponential Random Graph Models (ERGMs), Latent Space Models (LSMs), and, more recently, Graph Neural Networks (GNNs). In this talk, we will provide an overview of these models, highlighting their strengths, limitations, and the key statistical challenges they pose, such as model estimation, goodness-of-fit, and model selection.
These statistical considerations are critical for deriving accurate and reliable insights from network data, particularly in the context of biological networks. We will explore the controversies surrounding the empirical validity of power-law distributions in real-world networks and discuss how embedding protein interaction networks into hyperbolic space can reveal new insights into biological function and structure.
Title: First-passage percolation on random geometric graphs: Asymptotic shape, speed of convergence and its geodesics
Speaker: Lucas R. de Lima
Abstract: In recent years, the study of random geometric graphs, also known as the Gilbert disk model, and their properties has attracted a great deal of attention in the field of probability theory. This presentation delves into the first-passage percolation model, employing independent and identically distributed random variables on the infinite connected component of a random geometric graph. We establish sufficient conditions for the existence of the asymptotic shape, demonstrating that it converges to an Euclidean ball. Furthermore, we will present results on its speed of convergence, moderate deviations, fluctuations of geodesic paths, and an application in a competition model.
Title: The Flexibility of Gaussian Bayesian Networks
Speaker: Marco Grzegorczyk
Abstract: Gaussian Bayesian networks are very popular tools for inferring the dependency structures among interaction variables from data. The variables are assumed to follow a joint multivariate Gaussian distribution and directed acyclic graphs (DAGs) are used to impose conditional independence relations among them. Basically, a given DAG imposes restrictions on the structure of the covariance matrix, such that it implies the conditional independence relations encoded by the DAG. In Bayesian Statistics the DAGs can then be sampled from the posterior distribution. In the presentation it will be demonstrated how this framework of Gaussian Bayesian networks can be extended to deal with common situations, such as (i) learning Bayesian networks from incomplete data, (ii) learning Bayesian networks from ordinal (=discretized) data, and (iii) learning score-equivalent Bayesian networks from data with discrete and continuous Gaussian variables.
Title: Two-neighbour bootstrap percolation is local
Speaker: Augusto Teixeira
Abstract: Metastability thresholds lie at the heart of bootstrap percolation theory. Yet proving precise lower bounds for these quantities is notoriously hard. In this talk we show that for two of the most classical models (two-neighbour and Froböse), the same methodology that is typically used to prove upper bounds can be used to provide lower bounds as well. This is done by linking the models to their local counterparts. As a consequence, we are able to establish the second order term for the infection time of these two models. We will also see how this locality viewpoint can be used to resolve the so-called bootstrap percolation paradox. More precisely, we will present an exact (deterministic) algorithm which exponentially outperforms previous Monte Carlo approaches. We expect this methodology to be applicable to a wider range of models and we finish our talk with a number of open problems.
This talk will be based on a joint work with Ivailo Hartarsky.
Title: A model of social learning on rooted regular trees
Speaker: Moumanti Podder
Abstract: Let $\mathbb{T}_{m}$ be the rooted regular tree in which each vertex has $m$ children. An agent is stationed at each vertex of $\mathbb{T}_{m}$, and is allowed, at any point in time, to select one of two available technologies: $B$ and $R$. Let $C_{t}(v)$ denote the technology chosen by the agent at vertex $v$ at time-step $t$, for $t \in \mathbb{N}_{0}$. During the epoch $t$, the agent at $v$ performs an experiment that results in success with probability $p_{B}$ if $C_{t}(v)=B$, and with probability $p_{R}$ if $C_{t}(v)=R$. Letting $v_{1}, v_{2}, \ldots, v_{m}$ denote the children of $v$, the agent at $v$ updates their technology to $C_{t+1}(v)=B$ if the number of successes among all $v_{j}$, $1 \leqslant j \leqslant m$, with $C_{t}(v_{j})=B$, strictly exceeds the number of successes among all $v_{j}$, $1 \leqslant j \leqslant m$, with $C_{t}(v_{j})=R$. If these two numbers are equal, the agent at $v$ sets $C_{t+1}(v)=B$ with probability $1/2$. In all other cases, $C_{t+1}(v)=R$. We study the limit, as $t \rightarrow \infty$, of the process $\{C_{t}(v): v \in \mathbb{T}_{m}\}$, When
- $p_{B}, p_{R} \in [0,1]$ and $m=2$,
- $p_{B}=p_{R}=p$ and $m$ is an arbitrary positive integer with $m \geqslant 3$,
- $p_{B}=1$, $p_{R} \in [0,1)$ and $m=3$.
Phase transition phenomena are shown to take place in the latter two scenarios. This work can also be interpreted as a model for the diffusion of technologies throughout a population of agents.
Title: Robust Methods For Linear Regression
Speaker: Jordan Ekelenburg
Abstract: One of the most common types of statistical models used in practice is the linear model. Estimating the linear model under normality of errors is very well-known, but in practice we may need to deviate from the normality of errors due to heavier tails and/or skewness in the data. In this talk I will discuss how we can estimate the parameters of a linear model in the case that the errors have significantly heavier tails, such as Cauchy or t distributed errors. Finally, I will discuss the framework of M estimation as a suitable alternative to ML estimation and explain how M estimation encompasses ML estimation.
Title: Getting My Teeth into Survival Analysis
Speaker: Andrew Packer
Abstract: Survival analysis investigates the expected duration of time until individuals in a studied population undergo a specific event of interest. It is characterised by censoring: i.e. that the times-to-event of some portion of the study population are unobserved. The study that inspired this presentation is introduced. The assumptions, strengths and weaknesses of nonparametric and semiparametric models are enumerated. Methods are illustrated by authentic data from our study. Fundamental problems include the difficulty of testing assumptions about censoring and in deciding how confident one can be in inferences drawn from a highly censored data set.
Title: Unraveling Evolutionary Histories Through Statistics
Speaker: Darren Zammit
Abstract: Phylogenetics, the study of evolutionary relationships among organisms, lies at the intersection of biology, statistics, and computational science. The aim of phylogenetics algorithms is to discern significant similarities between diverging gene sequences of different species from random mutation and natural selection by constructing graphical representations of the evolutionary relationships.
In this talk I introduce the process of inferring a phylogeny through statistical methods starting with sequence evolution models, such as the Jukes and Cantor 1969 model, which assign a probability for a descendant sequence to be produced from an ancestral sequence. Following this, we discuss how these models can be applied in a maximum likelihood framework to infer a phylogenetic tree. Finally we discuss how to measure a tree’s reliability through bootstrapping/jackknifing and building a “consensus tree” which is a representation of a set of phylogenetic trees which attempts to summarise them in a way that captures their most frequently occurring characteristics.
Title: A Survey of Mortality Modeling Techniques
Speaker: Darragh Spillane
Abstract: The modeling of mortality rates plays a vital role in areas such as insurance, public health, pension planning, and policy-making. Since Lee and Carter (1992) introduced their method for modeling mortality rates, there has been a significant shift from deterministic to stochastic methods, with a specific focus on examining mortality rates across age, period, and cohort dimensions. Traditionally, these methods have concentrated on forecasting yearly mortality rates over extended periods. However, the COVID-19 pandemic has highlighted the necessity of modeling mortality at a more granular, monthly level to capture short-term fluctuations and immediate impacts. In this presentation I will provide an overview of the most popular mortality modeling methods and evaluate their suitability for generating short-term forecasts based on monthly mortality rates, addressing the challenges introduced by the COVID-19 pandemic.
Title: Large genus random hyperbolic surfaces with many cusps
Speaker: Tanguy Lions
Abstract: In the two last decades, random maps have been intensively studied by probabilists at both local and global scales. In particular, the case of random planar maps is now very well understood. At the same time, random hyperbolic surfaces have seen a rise in interest from geometers since the works of Maryam Mirzakhani. A recent result established by Budd-Curien shows that the scaling limit of random planar maps with a large number of faces and planar random hyperbolic surfaces with many cusps are the same : the Brownian sphere. It is natural to expect that the relation also holds for any fixed genus g > 0. In this talk, we will first give an introduction to random hyperbolic surfaces. Then we will focus our attention on the following problem : how many short geodesics are there on a large genus random hyperbolic surface with many cusps?
Title: An OSSS-type inequality for uniformly drawn subsets of fixed size
Speaker: Rob van der Berg
Abstract: The OSSS inequality (O'Donnell, Saks, Schramm and Servedio, 2005) gives an upper bound for the variance of a function of independent 0-1 valued random variables in terms of the influences of these random variables and the computational complexity of a (randomised) algorithm for determining the value of the function.
Duminil-Copin, Raoufi and Tassion, 2019, obtained a generalization of the OSSS inequality to monotonic measures and used it to prove new results for Potts models and random-cluster models. That generalization naturally triggers the question if there are still other measures for which such an inequality holds.
This talk concerns an OSSS-type inequality for a family of measures that are clearly not monotonic, namely the k-out-of-n measures (these measures correspond with drawing k elements from a set of size n uniformly).
The talk is related to my paper https://arxiv.org/pdf/2210.16100.pdf and to more recent progress with Henk Don (Nijmegen) on this topic.
Title: First passage percolation on Erdős-Rényi graphs with general weights
Speaker: Matthias Schulte
Abstract: In this talk, first passage percolation on the Erdős-Rényi graph with $n$ vertices and edge probability $\lambda/n$ for $\lambda>1$ is studied. The edges of the graph are given non-negative i.i.d. weights with a non-degenerate distribution such that the probability of zero is not too large. The paths with small total weight between two distinct typical vertices and the numbers of edges on such paths, the so-called hopcounts, are considered. For $n\to\infty$, it is shown that, after a suitable transformation, the pairs of hopcounts and total weights of these paths converge in distribution to a Cox process, i.e., a Poisson process with a random intensity measure. The random intensity measure is controlled by two independent random variables, whose distribution is the solution of a distributional fixed point equation and is related to branching processes. For non-arithmetic and arithmetic edge weight distributions different behaviours are observed. In particular, the limiting distribution for the minimal total weight and the corresponding hopcount(s) is derived. The results generalise earlier work of Bhamidi, van der Hofstad and Hooghiemstra, who studied the case of exponentially distributed edge weights, and are proven by the method of moments. This talk is based on joint work with Seva Shneer and Fraser Daly (both Heriot-Watt University).
Speaker: Ivailo Hartarsky
Abstract: In Catalan percolation, one declares the edges $\{i,i+1\}$ for $i\in\bbZ$ \emph{occupied} and each edge $\{i,j\}\subset\mathbb Z$ with $j\ge i+2$ \emph{open} independently with probability $p$. For $k\ge i+2$, we recursively define $\{i,k\}$ to be \emph{occupied}, if $\{i,k\}$ is open and both $\{i,j\}$ and $\{j,k\}$ are occupied for some $j\in\{i+1,\dots,k-1\}$. The model was introduced by Gravner and Kolesnik in the context of polluted bootstrap percolation, but is tightly linked with Catalan structures and oriented percolation. We establish that the critical parameter of the model is strictly between the natural lower and upper bounds given by $1/4$ and the critical probability of oriented site percolation on $\mathbb Z^2$ respectively. The most challenging part of the proof is a strict inequality for the critical parameter of an oriented percolation model with non-decaying infinite range dependencies, not relying on the Aizenman--Grimmett argument for essential enhancements.
Title: The voter model on dynamic random environments
Speaker: Jhon Astoquillca Aguilar
Abstract: The voter model is an interacting particle system describing the collective behavior of voters who constantly update their political opinions on a given graph. Following a graphical representation argument, we see that this Markov process is dual of a system of coalescing random walks on the graph. This duality relationship implies that the characterization of the set of stationary measures of the voter model is linked to the dynamics of the collision of random walks on graphs. In this presentation, we consider the voter model on connected and locally finite graphs, we show and explore the key ideas behind the duality relationship and the characterization statement. This understanding will serve as the foundation for establishing analogous characterizations for the voter model on dynamical percolation and a voter model that allows for the interchange of opinions, two variations of the voter model that will be introduced.
Title: Epidemics on networks with preventive rewiring
Speaker: Frank Ball
Abstract: We consider a stochastic SIR (susceptible $\to$ infective $\to$ recovered) model for the spread of an epidemic on a network, described initially by an Erd\H{o}s-R\'{e}nyi random graph, in which susceptible individuals connected to infectious neighbours may drop or rewire such connections as a preventive measure. A novel construction of the model is presented and used to both derive a deterministic model for epidemics started with a positive fraction initially infected and to prove convergence of the scaled stochastic model to that deterministic model as the population size $n \to \infty$. The final size (i.e.~total number of individuals infected) of the stochastic epidemic model is also studied, focussing on epidemics initiated by few infective that take off and lead to a major outbreak. For part of the parameter space, in the limit as $n \to \infty$, the fraction of the population infected by such a major outbreak is discontinuous in the infection rate $\lambda$ at its threshold $\lambda_c$, thus not converging to $0$ as $\lambda \downarrow \lambda_c$.
Based on work done jointly with Tom Britton (Stockholm University).
Title: Poisson approximation for determinantal score functionals
Speaker: Moritz Otto
Abstract: We consider stabilizing functionals of a determinantal point process with fast decay of correlations. Our main contribution is a Poisson approximation result in Kantorovich-Rubinstein distance. Its proof uses couplings of determinantal processes with different Palm measures and exploits their association properties. In the second part of the talk, we focus on the Ginibre process. We show in the asymptotic scenario of an increasing window size that the process of points with a large nearest neighbor distance converges after a suitable scaling to a Poisson point process. As a corollary, we obtain the scaling of the maximum nearest neighbor distance in the Ginibre process, which turns out to be different from its analogue for Poisson input.
Title: A new proof of exponential decay for Bernoulli percolation
Speaker: Hugo Vanneuville
Abstract: Bernoulli percolation of parameter p on Z^d is defined by deleting each edge of Z^d with probability 1-p, independently of the other edges. The exponential decay theorem -- proven in the 80's by Menshikov and independently by Aizenman and Barsky -- can be stated as follows: If the cardinality of the cluster of 0 is a.s. finite at some parameter p, then it has an exponential moment at every parameter q<p. I like to state this theorem this way because it illustrates the fact that "decreasing p infinitesimally has a regularising effect on the percolating clusters". A new -- shorter -- proof has been proposed by Duminil-Copin and Tassion in 2016. The goal of this talk is to discuss this theorem and to propose yet another proof of this theorem.
Title: Limit theorems for a self-repelling random walk
Speaker: Laure Marêché
Abstract: In this talk, we will consider a non-Markovian random walk such that the probability the walk goes to a given location is smaller if, in the past, it has often crossed the edge between the initial position and the target. The most studied such models are those in which edges are undirected. However, in 2008, Tóth et Vető introduced such a self-repelling random walk with directed edges, whose properties are very different from those of models with undirected edges. Despite the interest of such a behavior, very few results were obtained about this model afterwards. We will present new limit theorems for this random walk.
Title: Spatial inhomogeneous random graphs: limits and clustering
Speaker: Pim van der Hoorn
Abstract: Geometry is a powerful tool in many scientific domains, from fundamental physics to social science. It also plays and important role in the study of complex systems and random graphs, especially from the point of constructing models for networks. Here nodes are often assigned positions in some geometric space and connections are created based on the distances in that space. In this talk I will discuss a broad family of such geometric random graphs called: spatial inhomogeneous random graphs. These generalize many known models and can create networks that exhibit many key features found in real-world networks: sparcity, power-law degrees, clustering and short path lengths. One of the key technical advantages of these models is that we can describe their limits using the concept of local convergence, which allows us to study a wide range of local properties. I will present both results on local limits of these models and on the behavior of clustering on the resulting networks.
This is joint work with: Remco van der Hofstad and Neeladri Maitra
Title: On the Graph Theory of Majority Illusions: Theoretical Results and Computational Experiments
Speaker: Maaike Los
Abstract: The popularity of an opinion in one’s direct circles is not necessarily a good indicator of its popularity in one’s entire community. For instance, when confronted with a majority of opposing opinions in one’s circles, one might get the impression that one belongs to a minority. From this perspective, networks structures make local information about global properties of the group potentially inaccurate. However, the way a social network is wired also constrains what kind of information distortion can actually occur. In this paper, we discuss which classes of networks allow for a large enough proportion of the population to get a wrong enough impression about the overall distribution of opinions.We start by focusing on the ‘majority illusion’, the case where one sees an incorrect majority opinion in one’s direct circles. We show that no network structure can guarantee that most agents see the correct majority. We then generalize to other types of illusions. Finally, we perform computational experiments to study the likelihood of majority illusions in different classes of networks.
Title: Optimal transport and matching of point processes
Speaker: Raphaël Lachièze-Rey
Abstract: A matching between two point processes is a one-to-one mapping. We investigate the properties of optimal matchings between two stationary point processes, aiming at minimising the distance between two typically matched points, constituting a specific instance of the problem of optimal transport. We show that under mild conditions, a stationary point process behaves as a Poisson process in terms of magnitude. We also investigate the case of Hyperuniform point processes, encompassing many models of random matrices and Coulomb gases. These processes are characterized by low variance in the number of points within a large window, and despite their locally disordered structure, they are anticipated to exhibit global behavior akin to perturbed lattices. We prove that their expected transport cost is indeed comparable to that of a perturbed lattice, which yields in particular that in dimension 1 and 2 this cost is negligible with respect to that of disordered processes such as Poisson processes. Joint work with Yogeshwaran D.
Title: Counting graphic sequences
Speaker: Serte Donderwinkel
Abstract: A graphic sequence is a non-increasing sequence of natural numbers that can occur as the degree sequence of a graph. We show that the number of graphic sequences of length n grows like cn^{-3/4}4^n for some constant c. The foundation of our proof consists of a few reformulations that turn our problem into a question about the lazy simple symmetric random walk bridge. To be precise, we calculate the asymptotic probability that the integral of a (lazy) simple symmetric random walk bridge never goes negative. Our reformulation also yields a new, efficient algorithm for exact enumeration of graphic sequences, with which we are able to calculate many more exact values than previously known. This talk is based on joint work with Paul Balister, Carla Groenland, Tom Johnston and Alex Scott.
Title: Independent transversals in graphs
Speaker: Tomas Kaiser
Abstract: Suppose that G is a graph with a given partition P of its vertex set. An independent transversal of G is an independent set containing one vertex from each class of P. Sufficient conditions for theexistence of an independent transversal can be useful in many situations; the search for such conditions goes back to a conjecture of Erdős from 1972.
I will give an overview of results related to this problem, mention some of their applications, and focus on proof techniques used to obtain such results, particularly the Lovász Local Lemma and related methods. The talk includes joint work with Carla Groenland, Oscar Treffers and Matt Wales.
Title: Vertex bisection of random regular graphs
Speaker: Oriol Serra
Abstract: The vertex number of a bisection of the vertex set of a graph G is the minimum number of vertices in one of the two parts of the bisection whose deletion disconnects the graph. The minimum number among all bisections is the minimum vertex bisection of the graph. While the edge version of this problem, the minimum bisection width, has a rich history, relatively few results are known about the vertex version. Lower bounds for the minimum bisection of random regular graphs were provided by Kolesnik and Wormald. We will discuss an approach to obtain upper bounds for this problem which are obtained by a randomized algorithm analyzed with the differential equation method.
Title: Fredrickson-Andersen 2-spin facilitated model: sharp threshold
Speaker: Christina Toninelli
Abstract: The Fredrickson-Andersen 2-spin facilitated model (FA-2f) on $\mathbb{Z}^d$ is a paradigmatic interacting particle system with kinetic constraints (KCM) featuring cooperative and glassy dynamics. For FA-2f vacancies facilitate motion: a particle can be created/killed on a site only if at least 2 of its nearest neighbors are empty. We will present sharp results for the first time, $\tau$, at which the origin is emptied for the stationary process when the density of empty sites $(q)$ is small: in any dimension $d\geq 2$ it holds \[ \tau \sim \exp \left( \frac{d \lambda(d,2)+o(1)}{q^{1/(d-1)}} \right) \] w.h.p., with $\lambda(d, 2)$ the threshold constant for the 2-neighbour bootstrap percolation on $\mathbb{Z}^d$. This is the first sharp result for a critical KCM and settles various controversies accumulated in physics literature over the last four decades. We will explain the dominant relaxation mechanism leading to this result, give a flavour of the proof techniques, and discuss further results that can be obtained via our technique for more general KCM, including full universality results in two dimensions.
[Joint work with I.Hartarsky and F.Martinelli]
Title: Chromatic Number and Clique Number for Directed Graphs
Speaker: Pierre Charbit
Abstract:
In 1982, Victor Neumann Lara proposed a definition for the dichromatic number of a digraph : the minimum integer k such that the set of vertices of D can be partitioned into k acyclic subdigraphs. This generalizes the usual chromatic number in the sense that the chromatic number of a graph G is the same as the dichromatic of the digraph obtained from G by replacing each edge by a digon (two anti-parallel arcs). In the past two decades several theorems concerned with chromatic number of undirected graphs have been generalized to digraphs via the dichromatic number, and Neuman Lara’s definition is generally accepted as the « right » notion of colouring for digraphs.
As an optimization problem, chromatic number in the undirected setting has a natural dual and lower bound that is clique number - the maximum size of subgraph isomorphic to a clique. With Pierre Aboulker, Guillaume Aubian and Raul Lopes, we recently proposed a definition for clique number of digraphs, that seem to be a good counterpart of the undirected version and behaves properly with respect to dichromatic number.
During the talk, I’ll survey classical facts about dichromatic number then explore our notion of clique number and its relationship with the dichromatic number, mirroring the relationship between the clique number and chromatic number in undirected graphs. We will focus on studying the notion of chi-boundedness in particular, especially in the case of tournaments.
Title: Random (beta) polytopes
Speaker: Christoph Thäle
Abstract:
This talks starts with an introduction to classical random polytope models in $\mathbb{R}^d$: random convex hulls generated by uniform random points in convex bodies or on their boundary. We discuss various asymptotic results for the missed volume. Similar questions are then discussed for random polytopes on the $d$-dimensional unit sphere, which are generated by $n$ random points uniformly distributed in a spherically convex container set or on its boundary. In particular, we show how such a non-Euclidean model can be analysed by combining probabilistic tools with geometric estimates. Expanding the container set to a half-sphere gives rise to new phenomena and serves as our entrance card to the family of beta random polytopes. Their distinguished properties are discussed. We then present a selection of results demonstrating their central role in stochastic geometry, including random cones as well as random Voronoi tessellations.
Title: Rapidly sampling Coxeter tournaments
Speaker: Brett Kolesnik
Abstract: A tournament is an orientation of the complete graph. An edge is a competitive game between its endpoints, directed away from the winner. The score sequence is the out-degree sequence.
McShine (2000) showed that tournaments with given score sequence can be rapidly sampled, via simple random walk on the interchange graph of Brualdi and Li (1984).
We prove an analogue for Coxeter tournaments, which involve collaborative and solitaire games, as well as the usual competitive games. Geometric connections with the Coxeter permutahedra recently introduced by Ardila, Castillo, Eur and Postnikov (2020) will be discussed.
Joint work with Matthew Buckland, Rivka Mitchell and Tomasz Przybyłowski.
Title: Extremes of stationary heavy-tailed time series
Speaker: Hrvoje Planinic
Abstract:
We will present a framework for describing the asymptotic behavior of high-level exceedances for stationary (i.e. dependent) time series with heavy-tailed marginal distribution and whose exceedances occur in clusters; think of modelling e.g. financial returns or daily rainfall measurements. The main tools are the theory of point processes and the notion of the so-called tail process. The latter allows one to fully describe the asymptotic distribution of the extremal clusters using the language of standard Palm theory. We will illustrate the general theory on simple moving average models. If time permits, we will comment on how this framework can be extended to deal with extremes related to models from stochastic geometry.
Title: Walking in random Delaunay triangulations
Speaker: Olivier Devillers
Abstract:
Traversing a triangulation using neighbourhood relationships is a common tool, for example just to perform point location in the triangulation or to route a message if the triangulation represents a communication network. Analyzing walking algorithms is a classic of computational geometry and in the worst case, many results have been obtained, and several problems remain open. In this talk, we will focus on the random case: what are the expected performance of some walking strategies ?
\\References:
\\[1] Pedro Machado Manhães de Castro and Olivier Devillers. Expected Length of the Voronoi Path in a High Dimensional Poisson-Delaunay Triangulation, Discrete and Computational Geometry, Springer Verlag, 60(1), p200–219, 2018 .
\\[2] Nicolas Chenavier and Olivier Devillers. Stretch Factor in a Planar Poisson-Delaunay Triangulation with a Large Intensity. Advances in Applied Probability, Applied Probability Trust, 50 (1), p.35–56, 2018.
\\[3] Olivier Devillers and Louis Noizet. Walking in a Planar Poisson-Delaunay Triangulation: Shortcuts in the Voronoi Path. International Journal of Computational Geometry and Applications, World Scientific Publishing, 28 (3), p.255-269, 2018.
\\[4] Prosenjit Bose, Jean-Lou de Carufel and Olivier Devillers. Expected Complexity of Routing in Θ6 and Half-Θ6 Graphs.
Title: Fluctuations of random polytopes in smooth convex bodies
Speaker: Pierre Calka
Abstract:
We consider the random polytope generated as the convex hull of n independent and uniformly distributed points in a smooth convex body. When n is large, the random polytope converges to the smooth convex body itself and we are interested in studying its fluctuations, both in the radial and lateral directions. To do so, we study several functionals of the facets of the random polytope, namely the distance to the boundary, the volume and the diameter. Each of those functionals is coupled with the relative position of the facet, which is given by a boundary point of the underlying smooth convex body. We exhibit in particular explicit limit distributions for the typical distributions and prove similar explicit convergences of measures associated to the extreme value regime, including convergence in total variation. This leads us in particular to getting limiting extreme value distributions for the distance to the boundary and for the volume. In the particular case of dimension two and when the underlying convex body is an Euclidean ball, we obtain that the limit distribution of the typical height resembles a Tracy-Widom distribution. Moreover, the corresponding height process satisfies a so-called 1:2:3 scaling property which makes it similar to the growth processes from the infamous KPZ universality class, even though the limit process, known as the Burgers' festoon, does not involve any Airy process. This is joint work with Joe Yukich.
Title: Criticality in Sperner’s lemma
Speaker: Matej Stehlik
Abstract: Sperner’s lemma states that in any labelling of the vertices of a triangulation of a d-dimensional simplex with d+1 labels, such that each vertex of the d-simplex receives a distinct label and any vertex lying in a face of the d-simplex has the same label as one of the vertices of that face, there exists a rainbow facet (a facet whose vertices have pairwise distinct labels). Tibor Gallai proved (in a different but equivalent form) that for d=1 and d=2, we can pick any facet of the triangulation and find a labelling where that facet is the unique rainbow simplex. In this talk, I will show that this is not the case for higher dimensions, thereby giving a negative answer to a question of Gallai from 1969. The construction is based on the properties of a 4-dimensional polytope which had been used earlier to disprove a claim of Theodore Motzkin on neighbourly polytopes.
Joint work with Tomas Kaiser and Riste Skrekovski.
Title: Maximum Composite Likelihood Estimators for a Brown-Resnick random field in infill
Speaker: Nicolas Chenavier
Abstract:
Likelihood inference for max-stable random fields is in practice impossible because the finite-dimensional densities are unknown or cannot be computed efficiently. The weighted composite likelihood approach that utilizes lower dimensional marginal likelihoods (typically pairs or triples of sites that are not too distant) is rather favored. We consider the family of spatial Brown-Resnick random fields associated with isotropic fractional Brownian fields. The sites are given by only one realization of a homogeneous Poisson point process restricted to a fixed window and the random field is observed at these sites. We provide asymptotic properties of the composite likelihood estimators of the scale and Hurst parameters of the fractional Brownian fields as the intensity goes to infinity. Two different weighting strategies are used: we exclude either pairs that are not edges of the Delaunay triangulation or triples that are not vertices of triangles. Joint work with Christian. Y. Robert.
Title: Maximizing the size of a giant
Speaker: Pieter Trapman
Abstract: In a large Poissonian random graph of $n$ nodes, the nodes have i.i.d. weights distributed as the random variable $X$, and two nodes with respective weights $x_i$ and $x_j$ share an edge with probability $1-e^{x_i x_j/(\mu n)} \approx x_i x_j/(\mu n)$, where $\mu=\mathbb{E}[X]$. Conditioned on the weights, the presence or absence of edges between different pairs of vertices are independent. It is known that as $n \to \infty$, the fraction of the vertices that are in the largest connected component of the graph (the giant) converges in probability to some limit which depends on $X$.
We investigate which distribution with given expectation $\mu$ leads to the maximal size of the giant. We show that if $\mu> \mu_c \approx 1.756 $, then $\mathbb{P}(X=\mu)=1$ leads to the maximal giant. If $\mu< \mu_c$, the giant is maximized if $\mathbb{P}(X=0) + \mathbb{P}(X=\mu_c)=1$.
If time permits we address similar questions for so-called configuration model random graphs after Bernoulli percolation on the graph, where edges are open with probability $p<1$.
This talk is based on joint work with Tom Britton, Maria Deijfen and Sebastian Rosengren (Stockholm University) and on ongoing work with Maddalena Dona (Groningen).
See
Britton and T., Journal of Applied Probability 49, (2012): 1156–1165,
Deijfen, Rosengren and T., Journal of Statistical Physics 173 (2018): 736--745.
Title: Angles of random simplices and face numbers of random polytopes.
Speaker: Zakhar Kabluchko
Abstract:
The angle sum of any plane triangle is the same, but the angle sums of tetrahedra are not constant. In fact, two kinds of angle sums can be associated with a tetrahedron: one for solid angles at vertices and one for dihedral angles at edges, and neither of these sums is constant. What are the maximal and minimal values of these sums? Are there any relations satisfied by these sums? What are their average values? For example, if we take 4 points uniformly at random on the unit sphere in $\mathbb R^3$ (or in the unit ball), what are the expected values of the angle sums of the tetrahedron they span? We shall review results on these questions in the general setting of random simplices whose vertices follow the so-called beta or beta' distributions. The expected angle sums of these beta and beta' simplices can be determined exactly. As it turns out, several objects in stochastic geometry such as the typical cell of the Poisson-Voronoi tessellation or the zero cell of the homogeneous Poisson hyperplane tessellation (in Euclidean space or on the sphere) can be reduced to random polytopes whose vertices follow the beta' distribution. The expected face numbers of these polytopes can be expressed exactly through the expected angle sums of the random beta' simplices. The second part of the talk is mainly based on the papers
https://arxiv.org/abs/1909.13335
https://arxiv.org/abs/1905.01533
https://arxiv.org/abs/1805.01338
Title: Spanning regular subgraphs of random graphs: sharp thresholds.
Speaker: Maksim Zhukovskii
Abstract:
Given a constant d and a sequence of d-regular graphs F_n on n vertices, what is the threshold probability for containing a spanning subgraph isomorphic to F_n by a binomial random graph? In the talk, a fairly optimal answer to this question will be presented. In particular, it implies sharp thresholds for (asymptotically) almost all d-regular graphs F_n.
Title: Degree-penalised contact processesA
Speaker: Daniel Valesin
Abstract:
In this work, we introduce and study a degree-penalised contact process on graphs. The classical contact process on a graph is a model for the spread of an infection: vertices can be healthy or infected, infected vertices recover with rate one, and transmit the infection to each neighbor with rate lambda. In our version of the model, the rate with which a vertex u infects a neighbor v is lambda/f(d_u,d_v), where d_u and d_v are the degrees of u and v, respectively, and f is a positive and increasing function, called the penalization function; we focus on f(a,b) = max(a,b)^mu, where mu is positive. We study this model both on infinite trees and on sparse random graphs, and show that it presents a richer range of behavior than the contact process in these settings. Joint work with Júlia Komjáthy (TU Delft) and Zsolt Bartha (TU Eindhoven).
Title: Cover times and the Random Walk Loop Soup
Speaker: Erik Broman
Abstract:
The focus of this talk will be on the problem of cover times. This is a classical problem which exists in many variants, ranging from ``reaching every state in a Markov chain'' to the physical covering of a set in R^d or Z^d. I will present some history of this problem as well as more recent developments. In particular, I will focus on results (obtained jointly with F. Camia) concerning cover times for the so-called Random Walk Loop Soup (RWLS). This is a model which has received a fair amount of attention the last 15-20 years, and I will therefore also attempt to give an intuition about how this model works and how to think about it.
Title: It's hard to kill fake news
Speaker: Remco van der Hofstad
Abstract: Empirical findings have shown that many real-world networks are scale-free, in the sense that there is a high variability in the number of connections of the elements of the networks. Spurred by these empirical findings, models have been proposed for such networks. In this talk, we investigate the spread of fake news on them.
We assume that news starts spreading from a source using a first-passage percolation rumour spread dynamics. The source later realises that the news is in fact wrong. After this realisation, it starts spreading the correct news. We make the (optimistic) assumption that a vertex, once having heard the correct version of the news item, will only spread the correct information. As such, we are modelling misinformation rather than fake news, with fake news being able to sustain on a network even longer.
Our results show that in many settings, even when the correct news spreads faster, the incorrect news is likely to reach a large part of the network. We distinguish between the incorrect news weakly surviving, meaning that it reaching a growing number of vertices, and strong survival, where the incorrect news reaches a positive proportion of the vertices. We give explicit criteria for the incorrect news to weakly and strongly survive on the configuration model, which is one of the most popular networks models.
This lecture is based on joint work with Seva Shneer, and builds on earlier work with Gerard Hooghiemstra and Shankar Bhamidi.
Title: Surface law and charge rigidity for the Coulomb gas on $Z^d$
Speaker: Christophe Garban
Abstract:
I will start by introducing and motivating the (two-component) Coulomb gas on the d-dimensional lattice $Z^d$. I will then present some puzzling properties of the fluctuations of this Coulomb gas. The connection of this model with integer-valued fields and compact-valued spin systems will be emphasised through the talk. This is based on joint works with Avelio Sepúlveda and David Dereudre.
Title: Lower large deviations for geometric functionals in sparse and dense regimes
Speaker: Daniel Willhalm
Abstract:
We prove lower large deviations for geometric functionals in sparse, thermodynamic and dense regimes. Our results are tailored for functionals with nonexisting exponential moments, for which standard large deviation theory is not applicable. The rate functions are given in their relative entropy forms. The main tool of the proofs is a sprinkling technique that, adapted to the considered functionals, ensures a certain boundedness. This substantially generalizes previous approaches to tackle lower tails with sprinkling. Applications include sub graph counts and Betti numbers based on a sparse random geometric graph, power-weighted edge lengths of a $k$-nearest neighbor graph, a Poisson tree or a directed spanning forest in a thermodynamic regime and the volume of $k$-nearest neighbor balls in a dense regime.
Title: Sign clusters in the Infinite-Ising weighted triangulations
Speaker: Marie Albenque
Abstract:
In this talk, I will present recent results about the geometry of spin clusters in Ising-decorated triangulations.
In this model, triangulations are sampled together with a spin configuration on their vertices (i.e. a 2-coloring of its vertices), with a probability biased by the number of monochromatic edges, via a parameter nu. The fact that there exists a combinatorial critical value for this model has been initially established in the physics literature by Kazakov and was rederived by combinatorial methods by Bousquet-Mélou and Schaeffer, and Bouttier, Di Francesco and Guitter.
Here, we give geometric evidence that this model undergoes a phase transition by studying the volume and perimeter of its monochromatic clusters. In particular, we establish that, when nu is critical or subcritical, the cluster of the root is finite almost surely, and is infinite with positive probability for nu supercritical.
This is based on joint works with Laurent Ménard and with Laurent Ménard and Gilles Schaeffer.
Title: Asymptotic directions of infinite paths in the hyperbolic Radial Spanning Tree.
Speaker: David Coupier
Abstract:
In 2001, Howard & Newman introduced the central notion of straightness in order to decribe the infinite paths and their asymptotic directions in geometric random trees. Hence, for a straight geometric random tree, Howard & Newman are able to assert that any deterministic asymptotic direction u in S^{d-1} (the unit sphere in a d-dimensional space) is targeted by only one infinite path of the corresponding tree. There also exists a random set of directions which are targeted by at least two infinite paths (seen as 'exceptional directions'); this random set is only countable in dimension d=2. In this talk, we focus on 'very exceptional directions' in dimension d=2, i.e. targeted by at least three infinite paths. We prove that such 'very exceptional directions' do not exist in the case of the hyperbolic Radial Spanning Tree.
This is a joint work with Lucas Flammant and Chi Tran.
Title: Gaussian concentration and uniqueness of Gibbs measures
Speaker: Frank Redig
Abstract: We introduce the Gaussian concentration bound in the setting of lattice-spin systems (such as the Ising model). We provide context and motivation for this and related concentration inequalities. We show that the Gaussian concentration bound implies strict positivity of relative entropy density, and as a consequence uniqueness of translation invariant Gibbs measures. We show a generalization which is an analogue of the Bobkov-Götze theorem in the context of translation invariant lattice spin systems.
Based in joint works with JR Chazottes (Paris), J. Moles (Paris), E Ugalde (San Louis Potosi).
Title: The rank of random graphs
Speaker: Matthew Kwan
Abstract: Two landmark results in combinatorial random matrix theory, due to Komlós and Costello-Tao-Vu, show that discrete random matrices, and symmetric discrete random matrices, are typically nonsingular. In particular, in the language of graph theory, when p is a fixed constant, the biadjacency matrix of a random Erdős-Rényi bipartite graph G(n,n,p) and the adjacency matrix of an Erdős-Rényi random graph G(n,p) are both nonsingular with high probability. However, very sparse random graphs (i.e., where p is allowed to decay rapidly with n) are typically singular, due to the presence of "local" dependencies such as isolated vertices. In this work we give an essentially complete characterisation of such local dependencies, answering a question due to Vu.
Joint work with Margalit Glasgow, Ashwin Sah, Mehtaab Sawhney.
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: Totally unbalanced random polytopes: An extremal case of spherically symmetric random polytopes.
Speaker: Zakhar Kabluchko
Abstract:
Let $X_1,\ldots, X_n$ be i.i.d. random vectors in $\mathbb R^d$ with a rotationally invariant distribution. Their convex hull $ [X_1,\ldots, X_n] $ is a random polytope denoted by $P_{n,d}$. We are interested in expected values of various functionals of this polytope such as the number vertices or, more generally, the number of faces in a given dimension. How to choose the (rotationally invariant) distribution of $X_1$ to maximize/minimize the expected number of vertices of $P_{n,d}$ or the expected number of faces in a given dimension? One possible candidate for the minimizer is a polytope in which the tail function of $X_1$ is slowly varying. This situation has been studied in dimension 2 by Aldous, Fristedt, Griffin and Pruitt who proved that the expected number of vertices of $P_{n,2}$ converges to $4$ as $n\to\infty$. We shall extend their result to higher dimensions and discuss a series of conjectures on maximization/minimization of various functionals of $P_{n,d}$. The talk is based on a joint work in progress with Dmitry Zavadsky.
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.:
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
Speaker: Conrado Costa
Abstract: In this talk we discuss 2 main new results: the Strong Law of Large Numbers and a quenched Large deviation principle for the Random Walk in the Cooling random Environment introduced by Avena, den Hollander in 2016. For the proof of these two results, we present two auxiliary results. The first, an ergodic theorem for cooling random variables and the second, a concentration result for the cumulant generating function of the static Random Walk in the random environment.
Title: Monotonicity for multi-range percolation on oriented trees
Speaker: Daniel Valesin
Abstract: Percolation theory contains a variety of monotonicity-related conjectures which are easy and natural to state but challenging to prove. In this talk, we will survey a few of these problems. We will then specialize to the setting of Bernoulli percolation on multi-range oriented trees. The trees we consider are oriented regular trees where besides the usual short bonds, all bonds of a certain length are added. Independently, short bonds are open with probability p and long bonds are open with probability q. We study properties of the critical curve which delimits the set of pairs (p,q) for which there is percolation. We also show that this curve decreases with respect to the length of the long bonds. Joint work with Bernardo N. B. de Lima and Leonardo T. Rolla.