Universality for first passage percolation on sparse random graphs

S. Bhamidi, R.W. Hofstad, van der, G. Hooghiemstra

Onderzoeksoutput: Boek/rapportRapportAcademic

59 Downloads (Pure)

Uittreksel

We consider first passage percolation on the conguration model with n vertices, and general independent and identically distributed edge weights assumed to have a density. Assuming that the degree distribution satisfies a uniform X2 logX-condition, we analyze the asymptotic distribution for the minimal weight path between a pair of typical vertices, as well the number of edges on this path namely the hopcount. The hopcount satisfies a central limit theorem (CLT). Furthermore, writing Ln for the weight of this optimal path, then we shown that Ln(log n)= n converges to a limiting random variable, for some sequence n. This sequence n and the norming constants for the CLT are expressible in terms of the parameters of an associated continuous-time branching process that describes the growth of neighborhoods around a uniformly chosen vertex in the random graph. The limit of Ln(log n)= n equals the sum of the logarithm of the product of two independent martingale limits, and a Gumbel random variable. Till date, for sparse random graph models, such results have been shown only for the special case where the edge weights have an exponential distribution, wherein the Markov property of this distribution plays a crucial role in the technical analysis of the problem. The proofs in the paper rely on a refined coupling between shortest path trees and continuous- time branching processes, and on a Poisson point process limit for the potential closing edges of shortest-weight paths between the source and destination.
Originele taal-2Engels
Plaats van productieEindhoven
UitgeverijEurandom
Aantal pagina's40
StatusGepubliceerd - 2014

Publicatie series

NaamReport Eurandom
Volume2014013
ISSN van geprinte versie1389-2355

Vingerafdruk

First-passage Percolation
Sparse Graphs
Random Graphs
Universality
Branching process
Central limit theorem
Path
Continuous Time
Random variable
Shortest Path Tree
Technical Analysis
Poisson Point Process
Markov Property
Optimal Path
Degree Distribution
Graph Model
Exponential distribution
Date
Logarithm
Identically distributed

Citeer dit

Bhamidi, S., Hofstad, van der, R. W., & Hooghiemstra, G. (2014). Universality for first passage percolation on sparse random graphs. (Report Eurandom; Vol. 2014013). Eindhoven: Eurandom.
Bhamidi, S. ; Hofstad, van der, R.W. ; Hooghiemstra, G. / Universality for first passage percolation on sparse random graphs. Eindhoven : Eurandom, 2014. 40 blz. (Report Eurandom).
@book{622318b9c438490d93aee67b3de7494c,
title = "Universality for first passage percolation on sparse random graphs",
abstract = "We consider first passage percolation on the conguration model with n vertices, and general independent and identically distributed edge weights assumed to have a density. Assuming that the degree distribution satisfies a uniform X2 logX-condition, we analyze the asymptotic distribution for the minimal weight path between a pair of typical vertices, as well the number of edges on this path namely the hopcount. The hopcount satisfies a central limit theorem (CLT). Furthermore, writing Ln for the weight of this optimal path, then we shown that Ln(log n)= n converges to a limiting random variable, for some sequence n. This sequence n and the norming constants for the CLT are expressible in terms of the parameters of an associated continuous-time branching process that describes the growth of neighborhoods around a uniformly chosen vertex in the random graph. The limit of Ln(log n)= n equals the sum of the logarithm of the product of two independent martingale limits, and a Gumbel random variable. Till date, for sparse random graph models, such results have been shown only for the special case where the edge weights have an exponential distribution, wherein the Markov property of this distribution plays a crucial role in the technical analysis of the problem. The proofs in the paper rely on a refined coupling between shortest path trees and continuous- time branching processes, and on a Poisson point process limit for the potential closing edges of shortest-weight paths between the source and destination.",
author = "S. Bhamidi and {Hofstad, van der}, R.W. and G. Hooghiemstra",
year = "2014",
language = "English",
series = "Report Eurandom",
publisher = "Eurandom",

}

Bhamidi, S, Hofstad, van der, RW & Hooghiemstra, G 2014, Universality for first passage percolation on sparse random graphs. Report Eurandom, vol. 2014013, Eurandom, Eindhoven.

Universality for first passage percolation on sparse random graphs. / Bhamidi, S.; Hofstad, van der, R.W.; Hooghiemstra, G.

Eindhoven : Eurandom, 2014. 40 blz. (Report Eurandom; Vol. 2014013).

Onderzoeksoutput: Boek/rapportRapportAcademic

TY - BOOK

T1 - Universality for first passage percolation on sparse random graphs

AU - Bhamidi, S.

AU - Hofstad, van der, R.W.

AU - Hooghiemstra, G.

PY - 2014

Y1 - 2014

N2 - We consider first passage percolation on the conguration model with n vertices, and general independent and identically distributed edge weights assumed to have a density. Assuming that the degree distribution satisfies a uniform X2 logX-condition, we analyze the asymptotic distribution for the minimal weight path between a pair of typical vertices, as well the number of edges on this path namely the hopcount. The hopcount satisfies a central limit theorem (CLT). Furthermore, writing Ln for the weight of this optimal path, then we shown that Ln(log n)= n converges to a limiting random variable, for some sequence n. This sequence n and the norming constants for the CLT are expressible in terms of the parameters of an associated continuous-time branching process that describes the growth of neighborhoods around a uniformly chosen vertex in the random graph. The limit of Ln(log n)= n equals the sum of the logarithm of the product of two independent martingale limits, and a Gumbel random variable. Till date, for sparse random graph models, such results have been shown only for the special case where the edge weights have an exponential distribution, wherein the Markov property of this distribution plays a crucial role in the technical analysis of the problem. The proofs in the paper rely on a refined coupling between shortest path trees and continuous- time branching processes, and on a Poisson point process limit for the potential closing edges of shortest-weight paths between the source and destination.

AB - We consider first passage percolation on the conguration model with n vertices, and general independent and identically distributed edge weights assumed to have a density. Assuming that the degree distribution satisfies a uniform X2 logX-condition, we analyze the asymptotic distribution for the minimal weight path between a pair of typical vertices, as well the number of edges on this path namely the hopcount. The hopcount satisfies a central limit theorem (CLT). Furthermore, writing Ln for the weight of this optimal path, then we shown that Ln(log n)= n converges to a limiting random variable, for some sequence n. This sequence n and the norming constants for the CLT are expressible in terms of the parameters of an associated continuous-time branching process that describes the growth of neighborhoods around a uniformly chosen vertex in the random graph. The limit of Ln(log n)= n equals the sum of the logarithm of the product of two independent martingale limits, and a Gumbel random variable. Till date, for sparse random graph models, such results have been shown only for the special case where the edge weights have an exponential distribution, wherein the Markov property of this distribution plays a crucial role in the technical analysis of the problem. The proofs in the paper rely on a refined coupling between shortest path trees and continuous- time branching processes, and on a Poisson point process limit for the potential closing edges of shortest-weight paths between the source and destination.

M3 - Report

T3 - Report Eurandom

BT - Universality for first passage percolation on sparse random graphs

PB - Eurandom

CY - Eindhoven

ER -

Bhamidi S, Hofstad, van der RW, Hooghiemstra G. Universality for first passage percolation on sparse random graphs. Eindhoven: Eurandom, 2014. 40 blz. (Report Eurandom).