Diameter of the stochastic mean-field model of distance

Onderzoeksoutput: Boek/rapportRapportAcademic

57 Downloads (Pure)

Uittreksel

We consider the complete graph K_n on n vertices with exponential mean n edge lengths. Writing C_{ij} for the weight of the smallest-weight path between vertex i,j \in [n], Janson [17] showed that max_{i,j \in [n]} C_{ij} / log n converges in probability to 3. We extend this results by showing that max_{i,j \in [n]} C_{ij} - 3 log n converges in distribution to some limiting random variable that can be identified via a maximization procedure on a limiting infinite random structure. Interestingly, this limiting random variable has also appeared as the weak limit of the re-centered graph diameter of the barely supercritical Erdös-Rényi random graph in [21].
Originele taal-2Engels
Plaats van productieEindhoven
UitgeverijEurandom
Aantal pagina's27
StatusGepubliceerd - 2013

Publicatie series

NaamReport Eurandom
Volume2013013
ISSN van geprinte versie1389-2355

Vingerafdruk

Mean-field Model
Stochastic Model
Limiting
Random variable
Converge
Random Structure
Weak Limit
Random Graphs
Complete Graph
Path
Graph in graph theory
Vertex of a graph

Citeer dit

Bhamidi, S., & Hofstad, van der, R. W. (2013). Diameter of the stochastic mean-field model of distance. (Report Eurandom; Vol. 2013013). Eindhoven: Eurandom.
Bhamidi, S. ; Hofstad, van der, R.W. / Diameter of the stochastic mean-field model of distance. Eindhoven : Eurandom, 2013. 27 blz. (Report Eurandom).
@book{4142ea3ff5784039a8a5301f481cd328,
title = "Diameter of the stochastic mean-field model of distance",
abstract = "We consider the complete graph K_n on n vertices with exponential mean n edge lengths. Writing C_{ij} for the weight of the smallest-weight path between vertex i,j \in [n], Janson [17] showed that max_{i,j \in [n]} C_{ij} / log n converges in probability to 3. We extend this results by showing that max_{i,j \in [n]} C_{ij} - 3 log n converges in distribution to some limiting random variable that can be identified via a maximization procedure on a limiting infinite random structure. Interestingly, this limiting random variable has also appeared as the weak limit of the re-centered graph diameter of the barely supercritical Erd{\"o}s-R{\'e}nyi random graph in [21].",
author = "S. Bhamidi and {Hofstad, van der}, R.W.",
year = "2013",
language = "English",
series = "Report Eurandom",
publisher = "Eurandom",

}

Bhamidi, S & Hofstad, van der, RW 2013, Diameter of the stochastic mean-field model of distance. Report Eurandom, vol. 2013013, Eurandom, Eindhoven.

Diameter of the stochastic mean-field model of distance. / Bhamidi, S.; Hofstad, van der, R.W.

Eindhoven : Eurandom, 2013. 27 blz. (Report Eurandom; Vol. 2013013).

Onderzoeksoutput: Boek/rapportRapportAcademic

TY - BOOK

T1 - Diameter of the stochastic mean-field model of distance

AU - Bhamidi, S.

AU - Hofstad, van der, R.W.

PY - 2013

Y1 - 2013

N2 - We consider the complete graph K_n on n vertices with exponential mean n edge lengths. Writing C_{ij} for the weight of the smallest-weight path between vertex i,j \in [n], Janson [17] showed that max_{i,j \in [n]} C_{ij} / log n converges in probability to 3. We extend this results by showing that max_{i,j \in [n]} C_{ij} - 3 log n converges in distribution to some limiting random variable that can be identified via a maximization procedure on a limiting infinite random structure. Interestingly, this limiting random variable has also appeared as the weak limit of the re-centered graph diameter of the barely supercritical Erdös-Rényi random graph in [21].

AB - We consider the complete graph K_n on n vertices with exponential mean n edge lengths. Writing C_{ij} for the weight of the smallest-weight path between vertex i,j \in [n], Janson [17] showed that max_{i,j \in [n]} C_{ij} / log n converges in probability to 3. We extend this results by showing that max_{i,j \in [n]} C_{ij} - 3 log n converges in distribution to some limiting random variable that can be identified via a maximization procedure on a limiting infinite random structure. Interestingly, this limiting random variable has also appeared as the weak limit of the re-centered graph diameter of the barely supercritical Erdös-Rényi random graph in [21].

M3 - Report

T3 - Report Eurandom

BT - Diameter of the stochastic mean-field model of distance

PB - Eurandom

CY - Eindhoven

ER -

Bhamidi S, Hofstad, van der RW. Diameter of the stochastic mean-field model of distance. Eindhoven: Eurandom, 2013. 27 blz. (Report Eurandom).