Last passage percolation and limit theorems in Barak-Erdős directed random graphs and related models

Abstract

We consider directed random graphs, the prototype of which being the Barak-Erdős graph $\vec{G}(\mathbb{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 $\vec{G}(\mathbb{Z},p)$ the last passage percolation constant $C(p)$ is studied in great detail. It is shown that $C(p)$ is analytic for $p>0$, has an interesting asymptotic expansion at $p=1$ and that $C(p)/p$ converges to $e$ like $1/(\log p{)}^2$ as $p\to 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. We also explain how to approach the problem of estimation of last passage percolation constants by means of perfect simulation.

arXiv comment79 pages, 12 figures

References in corpus (18)

• Shape Fluctuations and Random Matrices
• Shift in the velocity of a front due to a cut-off
• Fredholm Determinants, Differential Equations and Matrix Models
• Convergence in law of the minimum of a branching random walk
• Effect of selection on ancestry: an exactly soluble case and its phenomenological generalization
• The genealogy of branching Brownian motion with absorption
• Minima in branching random walks
• Processes with Long Memory: Regenerative Construction and Perfect Simulation
• Brunet-Derrida particle systems, free boundary problems and Wiener-Hopf equations
• Speed and fluctuations of N-particle branching Brownian motion with spatial selection
• Branching random walk with selection at critical rate
• Poisson-Dirichlet branching random walks
• Coupling any number of balls in the infinite-bin model
• Limiting properties of random graph models with vertex and edge weights
• Two-sided infinite-bin models and analyticity for Barak-Erdős graphs
• Branching-stable point measures and processes
• Estimation of the last passage percolation constant in a charged complete directed acyclic graph via perfect simulation
• Continuum Cascade Model: Branching Random Walk for Traveling Wave

Cited by in corpus (1)

• Freezing in the Infinite-Bin Model