Skip to Main content Skip to Navigation
New interface
Journal articles

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 → 0, using a coupling with branching random walks with selection.
Complete list of metadata
Contributor : Sanjay Ramassamy Connect in order to contact the contributor
Submitted on : Thursday, October 27, 2022 - 9:16:38 AM
Last modification on : Saturday, October 29, 2022 - 3:58:45 AM


Files produced by the author(s)



Bastien Mallein, Sanjay Ramassamy. Barak-Erdös graphs and the infinite-bin model. Annales de l'Institut Henri Poincaré (B) Probabilités et Statistiques, 2021, 57 (4), pp.1940-1967. ⟨10.1214/20-AIHP1141⟩. ⟨ensl-01651022v2⟩



Record views


Files downloads