Bastien Mallein

Un graphe de Barak-Erdos est un graphe d'Erdos-Renyi orienté. Pour $i<j \le n$, on place une arête de $i$ vers $j$ avec probabilité $p$, indépendamment des autres arêtes. La longueur du plus court chemin dans ce graphe croît linéairement avec la taille du graphe, à une vitesse $C(p)$. Grâce à un couplage introduit par Foss et Konstantopoulos entre ce modèle et un modèle infini d'urne, on calcule le développement en série entière de $C$ au voisinage de $p=1$. On peut également obtenir les deux premiers termes du développement asymtotique de $C$ lorsque $p \to 0$ en comparant le modèle infini d'urne avec une marche branchante avec sélection.