How to determine if a random graph with a fixed degree sequence has a giant component

Felix Joos; Guillem Perarnau; Dieter Rautenbach; Bruce Reed

doi:10.1007/s00440-017-0757-1

How to determine if a random graph with a fixed degree sequence has a giant component

Felix Joos
, Guillem Perarnau
, Dieter Rautenbach
, Bruce Reed

Mathematics

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

441 Downloads (Pure)

Abstract

For a fixed degree sequence D = (d₁, ..., d_n), let G(D) be a uniformly chosen (simple) graph on {1, ..., n} where the vertex i has degree d_i. 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.

Original language	English
Pages (from-to)	263-310
Number of pages	48
Journal	Probability Theory and Related Fields
Volume	170
Issue number	1-2
Early online date	26 Jan 2017
DOIs	https://doi.org/10.1007/s00440-017-0757-1
Publication status	Published - Feb 2018

Access to Document

10.1007/s00440-017-0757-1Licence: None: All rights reserved

Joos_How_to_determine_Probability_Theory_Related_Fields_2016
This is a post-peer-review, pre-copyedit version of an article published in Probability Theory and Related Fields. The final authenticated version is available online at: https://doi.org/10.1007/s00440-017-0757-1
Accepted author manuscript, 498 KBLicence: None: All rights reserved

Randomized approaches to combinatorIal packing and covering problems
Kuhn, D. (Principal Investigator) & Osthus, D. (Co-Investigator)
Engineering & Physical Science Research Council
1/03/15 → 28/02/18
Project: Research Councils

Cite this

@article{f39fdb6feac3426286f747f939a3ec94,

title = "How to determine if a random graph with a fixed degree sequence has a giant component",

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. ",

author = "Felix Joos and Guillem Perarnau and Dieter Rautenbach and Bruce Reed",

year = "2018",

month = feb,

doi = "10.1007/s00440-017-0757-1",

language = "English",

volume = "170",

pages = "263--310",

journal = "Probability Theory and Related Fields",

issn = "0178-8051",

publisher = "Springer",

number = "1-2",

}

TY - JOUR

T1 - How to determine if a random graph with a fixed degree sequence has a giant component

AU - Joos, Felix

AU - Perarnau, Guillem

AU - Rautenbach, Dieter

AU - Reed, Bruce

PY - 2018/2

Y1 - 2018/2

N2 - 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.

AB - 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.

U2 - 10.1007/s00440-017-0757-1

DO - 10.1007/s00440-017-0757-1

M3 - Article

SN - 0178-8051

VL - 170

SP - 263

EP - 310

JO - Probability Theory and Related Fields

JF - Probability Theory and Related Fields

IS - 1-2

ER -

How to determine if a random graph with a fixed degree sequence has a giant component

Abstract

Access to Document

Fingerprint

Projects

Randomized approaches to combinatorIal packing and covering problems

Cite this