First passage percolation on random graphs with infinite variance degrees

Onderzoeksoutput: Boek/rapportRapportAcademic

1 Downloads (Pure)

Uittreksel

We prove non-universality results for first-passage percolation on the configuration model with i.i.d. degrees having infinite variance. We focus on the weight of the optimal path between two uniform vertices. Depending on the properties of the weight distribution, we use an example-based approach and show that rather different behaviors are possible. When the weights are a.s. larger than a constant, the weight and number of edges in the graph grow proportionally to loglog(n), as for the graph distances. On the other hand, when the continuous-time branching process describing the first passage percolation exploration through the graph reaches infinitely many vertices in finite time, the weight converges to the sum of two i.i.d. random variables representing the explosion times of the processes started from the two sources. This non-universality is in sharp contrast to the setting where the degree sequence has a finite variance (see Bhamidi, Hofstad and Hooghiemstra arXiv: 1210.6839).
Originele taal-2Engels
Uitgeverijs.n.
Aantal pagina's18
StatusGepubliceerd - 2015

Publicatie series

NaamarXiv
Volume1506.01255 [math.PR]

Vingerafdruk

First-passage Percolation
Infinite Variance
Random Graphs
Graph Distance
Weight Distribution
Degree Sequence
I.i.d. Random Variables
Optimal Path
Branching process
Graph in graph theory
Explosion
Continuous Time
Converge
Configuration

Citeer dit

@book{f4ceadae48e846b9a068db1eeacc77b3,
title = "First passage percolation on random graphs with infinite variance degrees",
abstract = "We prove non-universality results for first-passage percolation on the configuration model with i.i.d. degrees having infinite variance. We focus on the weight of the optimal path between two uniform vertices. Depending on the properties of the weight distribution, we use an example-based approach and show that rather different behaviors are possible. When the weights are a.s. larger than a constant, the weight and number of edges in the graph grow proportionally to loglog(n), as for the graph distances. On the other hand, when the continuous-time branching process describing the first passage percolation exploration through the graph reaches infinitely many vertices in finite time, the weight converges to the sum of two i.i.d. random variables representing the explosion times of the processes started from the two sources. This non-universality is in sharp contrast to the setting where the degree sequence has a finite variance (see Bhamidi, Hofstad and Hooghiemstra arXiv: 1210.6839).",
author = "E. Baroni and {Hofstad, van der}, R.W. and J. Komjathy",
year = "2015",
language = "English",
series = "arXiv",
publisher = "s.n.",

}

First passage percolation on random graphs with infinite variance degrees. / Baroni, E.; Hofstad, van der, R.W.; Komjathy, J.

s.n., 2015. 18 blz. (arXiv; Vol. 1506.01255 [math.PR]).

Onderzoeksoutput: Boek/rapportRapportAcademic

TY - BOOK

T1 - First passage percolation on random graphs with infinite variance degrees

AU - Baroni, E.

AU - Hofstad, van der, R.W.

AU - Komjathy, J.

PY - 2015

Y1 - 2015

N2 - We prove non-universality results for first-passage percolation on the configuration model with i.i.d. degrees having infinite variance. We focus on the weight of the optimal path between two uniform vertices. Depending on the properties of the weight distribution, we use an example-based approach and show that rather different behaviors are possible. When the weights are a.s. larger than a constant, the weight and number of edges in the graph grow proportionally to loglog(n), as for the graph distances. On the other hand, when the continuous-time branching process describing the first passage percolation exploration through the graph reaches infinitely many vertices in finite time, the weight converges to the sum of two i.i.d. random variables representing the explosion times of the processes started from the two sources. This non-universality is in sharp contrast to the setting where the degree sequence has a finite variance (see Bhamidi, Hofstad and Hooghiemstra arXiv: 1210.6839).

AB - We prove non-universality results for first-passage percolation on the configuration model with i.i.d. degrees having infinite variance. We focus on the weight of the optimal path between two uniform vertices. Depending on the properties of the weight distribution, we use an example-based approach and show that rather different behaviors are possible. When the weights are a.s. larger than a constant, the weight and number of edges in the graph grow proportionally to loglog(n), as for the graph distances. On the other hand, when the continuous-time branching process describing the first passage percolation exploration through the graph reaches infinitely many vertices in finite time, the weight converges to the sum of two i.i.d. random variables representing the explosion times of the processes started from the two sources. This non-universality is in sharp contrast to the setting where the degree sequence has a finite variance (see Bhamidi, Hofstad and Hooghiemstra arXiv: 1210.6839).

M3 - Report

T3 - arXiv

BT - First passage percolation on random graphs with infinite variance degrees

PB - s.n.

ER -