How to determine if a random graph with a fixed degree sequence has a giant component
Visualitza/Obre
Cita com:
hdl:2117/133718
Tipus de documentArticle
Data publicació2017-01-26
Condicions d'accésAccés obert
Llevat que s'hi indiqui el contrari, els
continguts d'aquesta obra estan subjectes a la llicència de Creative Commons
:
Reconeixement-NoComercial-SenseObraDerivada 3.0 Espanya
Abstract
For a fixed degree sequence D=(d1,…,dn) , let G(D) be a uniformly chosen (simple) graph on {1,…,n} where the vertex i has degree di . In this paper we determine whether G(D) has a giant component with high probability, essentially imposing no conditions on D . We simply insist that the sum of the degrees in D which are not 2 is at least ¿(n) for some function ¿ going to infinity with n. This is a relatively minor technical condition, and when D does not satisfy it, both the probability that G(D) has a giant component and the probability that G(D) has no giant component are bounded away from 1
CitacióJoos, F. [et al.]. How to determine if a random graph with a fixed degree sequence has a giant component. "Probability theory and related fields", 26 Gener 2017, vol. 170, núm. 1-2, p. 263-310.
ISSN0178-8051
Altres identificadorshttps://arxiv.org/abs/1601.03714
Fitxers | Descripció | Mida | Format | Visualitza |
---|---|---|---|---|
PTRF_submission_final.pdf | 497,9Kb | Visualitza/Obre |