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

Abstract : A Barak-Erd˝ os graph is a directed acyclic version of an Erd˝ os-Rényi 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˝ os 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.
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01651022
Contributeur : Sanjay Ramassamy <>
Soumis le : mardi 28 novembre 2017 - 15:49:40
Dernière modification le : mardi 24 avril 2018 - 17:20:06

Fichier

infinitebinmodel.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-01651022, version 1

Collections

Citation

Bastien Mallein, Sanjay Ramassamy. Barak-Erdös graphs and the infinite-bin model. 2017. 〈ensl-01651022〉

Partager

Métriques

Consultations de la notice

64

Téléchargements de fichiers

15