Geodesic
On the asymptotics for the minimal distance between extreme vertices in a generalised Barak--Erd\"{o}s graph
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 1556-1565.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider a generalization of the Barak–Erdös random graph, which is a graph with an ordered set of vertices $ \{ 0, 1, \ldots n \} $ and with directed edges from $ i $ to $ j $ for $ i j $ only, where each edge is present with a given probability $ p \in (0, 1) $. In our setting, probabilities $ p=p_{i,j} $ depend on distances $ j - i $ and may tend to $ 0 $ as $ j - i \to \infty $. We study the asymptotics for the distribution of the minimal path length between $ 0 $ and $ n $, when $ n $ becomes large.
Keywords: random graph, Barak–Erdös directed graph, minimal distance, boundary points, graph connectivity, first-passage percolation. 
@article{SEMR_2018_15_a41,
     author = {P. I. Tesemnikov},
     title = {On the asymptotics for the minimal distance between extreme vertices in a generalised {Barak--Erd\"{o}s} graph},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1556--1565},
     publisher = {mathdoc},
     volume = {15},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2018_15_a41/}
}
TY  - JOUR
AU  - P. I. Tesemnikov
TI  - On the asymptotics for the minimal distance between extreme vertices in a generalised Barak--Erd\"{o}s graph
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2018
SP  - 1556
EP  - 1565
VL  - 15
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2018_15_a41/
LA  - ru
ID  - SEMR_2018_15_a41
ER  - 
%0 Journal Article
%A P. I. Tesemnikov
%T On the asymptotics for the minimal distance between extreme vertices in a generalised Barak--Erd\"{o}s graph
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2018
%P 1556-1565
%V 15
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2018_15_a41/
%G ru
%F SEMR_2018_15_a41
P. I. Tesemnikov. On the asymptotics for the minimal distance between extreme vertices in a generalised Barak--Erd\"{o}s graph. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 1556-1565. http://geodesic.mathdoc.fr/item/SEMR_2018_15_a41/

[1] A. Auffinger, M. Damron, J. Hanson, “50 years of first passage percolation”, American Mathematical Society, 68 (2018), 161 | MR

[2] A. Barak, P. Erdös, “On the maximal number of strongly independent vertices in a random acyclic directed graph”, SIAM Journal on Algebraic Discrete Methods, 5:4 (1984), 508–514 | DOI | MR

[3] J. Cohen, C. Newman, “Community area and food chain length: theoretical predictions”, The American Naturalist, 138:6 (1991), 1542–1554 | DOI

[4] D. Denisov, S. Foss, T. Konstantopoulos, “Limit theorems for a random directed slab graph”, The Annals of Applied Probability, 22:2 (2012), 702–733 | DOI | MR

[5] P. Erdös, A. Rényi, “On Random Graphs. I.”, Publicationes Mathematicae Debrecen, 6 (1959), 290–297 | MR

[6] S. Foss, T. Konstantopoulos, “Extended renovation theory and limit theorems for stochastic ordered graphs”, Markov Processes and Related Fields, 9:3 (2003), 413–468 | MR

[7] S. Foss, J. Martin, P. Schmidt, “Long-range last-passage percolation on the line”, The Annals of Applied Probability, 24:1 (2014), 198–234 | DOI | MR

[8] M. Isopi, C. Newman, “Speed of parallel processing for random task graphs”, Communications on Pure and Applied Mathematics, 47:3 (1994), 261–276 | DOI | MR

[9] B. Mallein, S. Ramassamy, Barak-Erdös graphs and the infinite-bin model, 2017, arXiv: 1610.04043 [math.PR]