On the largest component of a random graph with a subpower-law degree sequence in a subcritical phase

Pittel, B. G.

Pittel, B. G.

Ann. Appl. Probab., Tome 18 (2008) no. 1, p. 1636-1650 / Harvested from Project Euclid

Résumé

A uniformly random graph on n vertices with a fixed degree sequence, obeying a γ subpower law, is studied. It is shown that, for γ>3, in a subcritical phase with high probability the largest component size does not exceed n^1/γ+ɛ_n, ɛ_n=O(ln ln n/ln n), 1/γ being the best power for this random graph. This is similar to the best possible n^1/(γ−1) bound for a different model of the random graph, one with independent vertex degrees, conjectured by Durrett, and proved recently by Janson.

Publié le : 2008-08-15
Classification: Random graph, degree sequence, power law, largest cluster, pairing process, martingale, asymptotic, bounds, 60C05, 60K35, 60J10

@article{1216677135,
     author = {Pittel, B. G.},
     title = {On the largest component of a random graph with a subpower-law degree sequence in a subcritical phase},
     journal = {Ann. Appl. Probab.},
     volume = {18},
     number = {1},
     year = {2008},
     pages = { 1636-1650},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1216677135}
}

Pittel, B. G. On the largest component of a random graph with a subpower-law degree sequence in a subcritical phase. Ann. Appl. Probab., Tome 18 (2008) no. 1, pp.  1636-1650. http://gdmltest.u-ga.fr/item/1216677135/