Last passage percolation and limit theorems in Barak-Erdos directed random graphs and related models

Last passage percolation and limit theorems in Barak-Erdos directed random graphs and related models Full article

Journal

Probability Surveys
ISSN: 1549-5787

Output data

Year: 2024, Volume: 24, Pages: 67--170 Pages count : 104 DOI: 10.1214/24-PS28

Tags

Random graph, random tree, branching random walk, Barak-Erdős graph, stochastic ordered graph, Tracy-Widom distribution, last passage percolation, Brownian percolation, infinite bin model, perfect simulation, Poisson-weighted infinite tree, selection, coupling.

Authors

Foss S ^1,2 , Konstantopoulos T ³ , Mallein B ⁴ , Ramassami S ⁵

Affiliations

1	School of Mathematical and Computer Sciences, Heriot-Watt University, UK
2	Sobolev Institute of Mathematics, Russia
3	Department of Mathematical Sciences, University of Liverpool, UK,
4	Institut de Mathématiques de Toulouse, UMR 5219, Université de Toulouse, UPS, F-31062 Toulouse Cedex 9, France,
5	Université Paris-Saclay, CNRS, CEA, Institut de Physique Théorique, 91191 Gif-sur-Yvette, France,

We consider directed random graphs, the prototype of which being the Barak-Erdős graph G(Z,p), and study the way that long (or heavy, if weights are present) paths grow. This is done by relating the graphs to certain particle systems that we call Infinite Bin Models (IBM). A number of limit theorems are shown. The goal of this paper is to present results along with techniques that have been used in this area. In the case of G(Z,p) the last passage percolation constant C(p) is studied in great detail. It is shown that C(p)isanalyticforp>0, has an interesting asymptotic expansion at p =1andthatC(p)/p converges to e like 1/(logp)2 as p → 0. The paper includes the study of IBMs as models on their own as well as their connections to stochastic models of branching processes in continuous or discrete time with selection. Several proofs herein are new or simplified versions of published ones. Regenerative techniques are used where possible, exhibiting random sets of vertices over which the graphs regenerate. When edges have random weights we show how the last passage percolation constants behave and when central limit theorems exist. When the underlying vertex set is partially ordered, new phenomena occur, e.g., there are relations with last passage Brownian percolation. We also look at weights that may possibly take negative values and study in detail some special cases that require combinatorial/graph theoretic techniques that exhibit some interesting non-differentiability properties of the last passage percolation constant. In addition, we explain how to approach the problem of estimation of last passage percolation constants by means of perfect simulation.

Foss S. , Konstantopoulos T. , Mallein B. , Ramassami S.
Last passage percolation and limit theorems in Barak-Erdos directed random graphs and related models
Probability Surveys. 2024. V.24. P.67--170. DOI: 10.1214/24-PS28 WOS Scopus РИНЦ OpenAlex

Submitted:	Dec 5, 2023
Published print:	Sep 3, 2024
Published online:	Sep 3, 2024

Web of science:	WOS:001307765200001
Scopus:	2-s2.0-85212682635
Elibrary:	73628130
OpenAlex:	W4389404542

Пока нет цитирований