Barak-Erdös graphs and the infinite-bin model - Archive ouverte HAL Access content directly
Journal Articles Annales de l'Institut Henri Poincaré (B) Probabilités et Statistiques Year : 2021

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

(1, 2) , (3)
1
2
3

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.
Fichier principal
Vignette du fichier
infinitebinmodel.pdf (1.51 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

ensl-01651022 , version 1 (28-11-2017)
ensl-01651022 , version 2 (27-10-2022)

Identifiers

Cite

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⟩
129 View
57 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More