Title: Self-overlapping lattice polygons
Abstract: A fusene is a plane graph in which all bounded faces are hexagons, all vertices are of degree 2 or 3 while all vertices not in the boundary are of degree 3. A self-avoiding polygon in the honeycomb lattice is an example of a fusene, but a general fusene should be thought of as a lattice polygon that is allowed to self-overlap. One may also interpret a fusene as a flat hexagonal tiling of a topological disk and this way equipping it with a flat metric. In this talk I will discuss the problem of enumeration of fusenes, and other classes of self-overlapping lattice polygons, and highlight some properties of the random flat metric on the disk associated to uniform random self-overlapping lattice polygons of fixed large perimeter. This is a problem that arises naturally in the physics context of JT gravity, as pointed out in recent works by F. Ferrari.
Title: Scaling limits of the Luczak-Winkler growth algorithm
Abstract: Since the pioneering work of Aldous in the 1990s, it has been well established that large random trees converge towards a universal object: the Brownian tree. This object, which has become a pillar of modern probability, is a real random compact tree of fractal dimension 2. In this presentation, we will focus on different tree growth algorithms, such as the Rémy algorithm and the Luczak-Winkler algorithm. We will see how, by passing them to the limit, they give rise to diffusions taking values in the space of real trees, of which the Brownian tree constitutes the invariant law.
Title: Integrality Gaps for Random Integer Programs via Discrepancy
Abstract: We prove new bounds on the additive gap between the value of a random integer program max c^T x, Ax≤b, x∈{0,1}^n with m constraints and that of its linear programming relaxation for a wide range of distributions on (A,b,c) . We are motivated by the work of Dey, Dubey, and Molinaro (SODA '21), who gave a framework for relating the size of Branch-and-Bound (B&B) trees to additive integrality gaps.
Dyer and Frieze (MOR '89) and Borst et al. (Mathematical Programming '22), respectively, showed that for certain random packing and Gaussian IPs, where the entries of A,c are independently distributed according to either the uniform distribution on [0,1] or the Gaussian distribution N(0,1), the integrality gap is bounded by O_m(log^2(n)/n) with probability at least 1−1/n−e{-Omega(m)}. In this paper, we generalize these results to the case where the entries of A are uniformly distributed on an integer interval (e.g., entries in {−1,0,1}), and where the columns of A are distributed according to an isotropic logconcave distribution. Second, we substantially improve the success probability to 1−1/poly(n), compared to constant probability in prior works (depending on m). Leveraging the connection to Branch-and-Bound, our gap results imply that for these IPs B&B trees have size n^poly(m) with high probability (i.e., polynomial for fixed m), which significantly extends the class of IPs for which B&B is known to be polynomial.
Our main technical contribution is a new linear discrepancy theorem for random matrices. Our theorem gives general conditions under which a target vector is equal to or very close to a {0,1} combination of the columns of a random matrix A. The proof uses a Fourier analytic approach, building on work of Hoberg and Rothvoss (SODA '19) and Franks and Saks (RSA '20).
Joint work with Sander Borst (CWI) and Dan Mikulincer (University of Washington).
Available at https://arxiv.org/abs/2203.11863.
Title: A Refined Sylvester Problem: Probabilities of Combinatorial Types.
Abstract: Let X_1,...,X_{d+2} be random points in R^d. A d-dimensional version of the classical Sylvester problem asks to determine the probability that the convex hull of these points, denoted by P := [ X_1, ... ,X_{d+2}], is a simplex. If P is not a simplex, it is a simplicial polytope with d+2 vertices. There exist [d/2] different combinatorial types of such polytopes. In this talk we shall review some results on the refined Sylvester problem which asks to determine the probabilities of these combinatorial types. We shall compute these probabilities in the following cases:
(a): X_1,...,X_{d+2} are i.i.d. standard normal in \mathbb R^d;
(b): X_1,...,X_{d+2} are i.i.d. beta or beta'-distributed;
(c): X_1,...,X_{d+2} form a random walk with symmetrically exchangeable increments.
The talk is partially based on joint works with Anna Gusakova and Hugo Panzo: https://arxiv.org/abs/2501.00671 and https://arxiv.org/abs/2501.16166.
Title: Schramm's locality conjecture for long range percolation cluster size decay and the locality conjecture
Abstract: The Schramm's locality conjecture says, in vague words, that if G_n is a sequence of graph converging locally to a limiting infinite, possibly random rooted graph G, then the critical percolation probability p_c of G_n converges to p_c of the limiting graph G. In other words, the critical parameter of Bernoulli percolation is continuous in the local topology. Recently there have been several breakthroughs to prove this conjecture for nearest neighbor Bernoulli percolation on Calyley graphs of groups and vertex-transitive graphs. We show that for long-range percolation similar statements can be made and explain how locality is related to supercritical sharpness, i.e., fast decay of the size of finite clusters.
Joint work with Yago Moreno Alonso.
Title: A decentralised diagnosis method with probabilistic cellular automata
Abstract: The decentralised diagnosis problem consists in the detection of a certain amount of defects in a distributed network. Here, we tackle this problem in the context of two-dimensional cellular automata with three states: neutral, alert and defect. When the density of defects is below a given threshold, we want the alert state to coexist with the neutral state, while when this density is above the threshold, we want the alert state to invade the whole grid. We present two probabilistic rules to answer this problem. The first one is isotropic and is studied with numerical simulations. The second one is defined on Toom’s neighbourhood and is examined with an analytical point of view. These solutions constitute a first step towards a broader study of the decentralised diagnosis problem on more general networks.
This is a joint work with Nazim Fatès and Régine Marchand.
Title: On irreducible CLTs
Abstract: Central limit theorems (CLTs) for homogeneous sums (or, more generally, degenerate U-statistics) of independent random variables are classical results in modern stochastic analysis, that have been recently refined and considerably extended through the use of Malliavin calculus and associated variational tools. The aim of this talk is to address the following question: 'Can one characterize those CLTs for homogeneous sums that cannot be reduced to the classical Lindberg principle?' I will provide several partial answers to this question, based on the use of Laplace spectra for (hyper)graphs, Cheeger inequalities, as well as a certain notion of "combinatorial dimension" introduced in a seminal book by R. Blei (2001).
Based on a joint work with F. Caravenna and F. Cottini.
Title: Fermionic structures in random lattice models
Abstract: The goal of the talk is to explain the (fermionic) discrete Gaussian free field structure that appears in special random lattice models, namely the Abelian sandpile model, and the uniform spanning tree. In particular, we introduce the Abelian sandpile model, an example of a statistical mechanics model that displays self-organized criticality. We show its key properties, and present the burning bijection, a famous algorithm by Majumdar and Dhar which connects the sandpile to uniform spanning trees. To link both models to "fermions" we then introduce Grassmannian calculus. We give a brief presentation of its rules that are needed to work probabilistically, and we apply them to construct Grassmannian Gaussians. A nice application of these techniques is for scaling limits of local fields, like the height-one field of the sandpile or the degree field of the uniform spanning tree, for which we sketch a few proofs.
This is based on the work in arXiv:2309.08349 and in collaboration with L. Chiarini (U Durham), A. Cipriani (UCL) and A. Rapoport (UU).
Title: Detecting geometry in scale free networks
Abstract: Geometric network models formalize the natural idea that similar vertices are likely to connect. Therefore, geometric models capture many common structural properties of real-world networks. However, if one observes only the network connections, the presence of geometry is not always evident. Currently, triangle counts and clustering coefficients are the standard statistics to signal the presence of geometry. We show that triangle counts or clustering coefficients are insufficient because they fail to detect geometry induced by hyperbolic spaces, or in networks with power law degrees. We therefore introduce different statistics, based on weighted subgraph counts that can even detect geometry in the 'weak geometry' regime, where the geometric effects converge to zero.
Title: Local limit of massive spanning forests on the complete graph
Abstract: What does a random spanning forest of a large complete graph look like, seen from a typical vertex?
Grimmett answered this question a long time ago for the uniform spanning tree (which is a spanning forest with a single component): the local limit is a critical Bienaymé-Galton-Watson tree with a Poisson reproduction law, conditioned to survive forever.
In this talk I will first introduce the model of massive spanning forests on any simple graph, motivated mainly by the celebrated Kirchhoff matrix-forest theorem. Then I will show that, for the complete graph, a phase transition separates the masses for which the situation is identical to Grimmett's answer from one where a new limit object appears.
Lastly, I will discuss massive spanning forests on $\mathbb{Z}^d$, which are related to the fermionic Gaussian free field in Wioletta's talk.
Talk based on arxiv:2403.11740 with Nathanaël Enriquez (Orsay and ENS Ulm) and Paul Melotti (Orsay), and on work in progress with Wioletta Ruszel (Utrecht).
Title: Percolation on the Stationary Measures of the Voter Model with Stirring
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.
Joint work with Réka Szabó and Daniel Valesin.
Title: Sharp thresholds for factors in random graphs
Abstract: Let F be a graph on r vertices and let G be a graph on n vertices. An F-factor in G is a subgraph of G composed of n/r vertex-disjoint copies of F, if r divides n. For instance, a K_2-factor is simply a perfect matching. In their 2008 breakthrough paper, Johansson, Kahn and Vu established the threshold -- up to the leading constant -- for the existence of an F-factor in G(n,p) when F is strictly 1-balanced. The sharp thresholds, meaning the leading constants, were obtained only recently by Riordan and Heckel, but only for complete graphs F=Kr and for so-called nice graphs. Their results rely on sophisticated couplings that utilize the recent, celebrated solution of Shamir's problem on hypergraph matchings by Kahn.
In this talk, we review these results, as well as the recent extension of the sharp thresholds to any strictly 1-balanced F, obtained in joint work with A. Heckel, M. Kaufmann, N. Müller and M. Pasch. In particular, this confirms the thirty year old conjecture by Rucínski that the sharp threshold for the emergence of an F-factor indeed coincides with the sharp threshold for the disappearance of the last vertices which are not contained in a copy of F.
Title: High intensity Voronoi percolation on manifolds
Abstract: Hansen and Müller showed that the critical probability $p_c(\lambda, \mathbb{H}^2)$ for Voronoi percolation in the hyperbolic plane tends to $1/2$ as the intensity $\lambda$ of the underlying Poisson process tends to $\infty$.
We extend this result to more general manifolds. More precisely, we determine conditions on a $d$-dimensional manifold $M$ that ensure that the critical probability $p_c(\lambda, M)$ for Voronoi percolation on $M$ with intensity $\lambda$ tends to $p_c(\R^d)$ as $\lambda \to \infty$.
Based on joint work with Barbara Dembin, Ritvik Radhakrishnan and Franco Severo.
Title: The Phase Transition of the Voter Model on Dynamic Scale-Free Networks
Abstract: The voter model is a classical interacting particle system explaining consensus formation on a social network. Real social networks feature not only a heterogeneous degree distribution but also connections changing over time. We study the voter model on a rank one scale-free network evolving in time by each vertex updating (refreshing its edge neighbourhood) at any rate. We find the dynamic giant component phase transition in the consensus time of the voter model through three regimes: including slowdown by the inverse speed of the dynamic and by the number of vertices divided by its logarithm.
Title: Growing conditioned BGW trees with log-concave offspring distributions
Abstract: We will consider the problem of building sequences of random trees ""à la Luczak--Winkler"", that is by adding vertices one at a time, in such a way that at each step, the tree has the correct distribution.
I will present the following result: given a log-concave offspring distribution, the corresponding sequence of Bienaymé--Galton--Watson trees conditioned to have n vertices can be realized as a Markov process (T_n, n≥1) which adds a new ""right-leaning"" leaf at each step. If time permits, I will also discuss an application to increasing couplings in an inhomogeneous model of random subtrees of the Ulam–Harris tree.
This generalizes the original construction of Luczak and Winkler (2004), which in terms of Bienaymé–Galton–Watson trees allows to cover the cases of binomial, Poisson and geometric offspring distributions.
Based on arXiv:2411.03065.
Title: Results on degrees in β- and β'-Delaunay graphs
Abstract: The β-Delaunay and β′-Delaunay triangulations are tessellation models generalizing classical Poisson-Delaunay triangulation on the Euclidean space. Both were introduced recently by Gusakova, Kabluchko, and Thäle in a series of papers. We present various results on the degrees of the vertex-edge graphs of these models, including bounds on the distributions of typical degrees and (in one of those models) a concentration phenomenon for the maximal degree in a growing window.
Title: Poisson-Voronoi percolation in high dimensions
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 present our result 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: Limit Theorems for Projections of Random Geometric Graphs
Abstract: Let $G$ be a random geometric graph where the vertices are determined by a Poisson point process on some compact convex set $W\subset\mathbb{R}^d$. We consider the edge crossings in a random graph drawing generated by projecting $G$ onto a plane. These crossings define a point process on the plane. We show that for some sparse $G$ the point process converges to a Poisson point process as the vertex intensity tends to infinity. The number of crossings and a second quantity called the stress satisfy a multivariate central limit theorem in the thermodynamic regime.
This talk is based on joint work with Hanna Döring.
Title: Lack of persistence of the maximum degree in preferential attachment trees with vertex death
Abstract: Preferential attachment (PA) models are a popular class of random graphs that have received a wealth of attention in the last decades and are often used to model evolving networks. In such models, new vertices are added to the graph sequentially and new vertices are more likely to make connections with existing vertices that have a large degree.
In recent work, we study a general PA model where vertices can both be added but can also be `killed’. Such killed vertices can no longer make new connections, whereas `alive’ vertices continue to make new connections. These models mimic evolving networks that both increase as well as decrease in size.
In this talk, we investigate `persistence of the maximum degree’: One of the oldest vertices in the graph attains the largest degree for all but finitely many steps. Beyond generalizing some existing results for PA models (without death) to the setting with death, we uncover a novel regime in which killing of vertices makes persistence entirely impossible.
Joint work with Markus Heydenreich.
Title: Poisson-Voronoi tessellation as a weak limit of the Poisson-Laguerre tessellation
Abstract: In this talk we consider the weak convergence of the sequence of Poisson-Laguerre tessellations $(\mathcal{L}(\eta_n))_{n\in \mathbb{N}}$ and their duals $(\mathcal{L}^*(\eta_n))_{n\in \mathbb{N}}$ in $\mathbb{R}^d$, which are constructed by Poisson point processes $\eta_n$ in $\mathbb{R}^d \times \mathbb{R}_+$, as $n\to \infty$. The underlying point processes $\eta_n$ have density of the form $(v,h)\mapsto f_n(h)$ with respect to the Lebesgue measure, where $v\in \mathbb{R}^d$ and $h\in \mathbb{R}_+$. We show that for suitable choices of $f_n$, the weak limit of these random tessellations is the classical Poisson-Voronoi and the Poisson-Delaunay tessellation, respectively. In particular, this result implies the weak convergence of the $\beta$-Voronoi and the $\beta$-Delaunay tessellation to the Poisson-Voronoi and the Poisson-Delaunay tessellation, respectively.