Barak-Erdős graphs and the infinite-bin model

Abstract

A Barak-Erdős graph is a directed acyclic version of the Erdős-Rényi random graph. It is obtained by performing independent bond percolation with parameter $p$ on the complete graph with vertices $\{1,...,n\}$, in which the edge between two vertices $i<j$ is directed from $i$ to $j$. The length of the longest path in this graph grows linearly with the number of vertices, at rate $C(p)$. In this article, we use a coupling between Barak-Erdős graphs and infinite-bin models to provide explicit estimates on $C(p)$. More precisely, we prove that the front of an infinite-bin model grows at linear speed, and that this speed can be obtained as the sum of a series. Using these results, we prove the analyticity of $C$ for $p>1/2$, and compute its power series expansion. We also obtain the first two terms of the asymptotic expansion of $C$ as $p\to 0$, using a coupling with branching random walks.

36 pages, 5 figures

References in corpus (4)

• Branching random walk with selection at critical rate
• Coupling any number of balls in the infinite-bin model
• $N$-Branching random walk with $\alpha$-stable spine
• Continuum Cascade Model: Branching Random Walk for Traveling Wave

Cited by in corpus (4)

• Coupling any number of balls in the infinite-bin model
• The Hilbert-Galton board
• 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