Asymptotic enumeration of graphs with given degree sequence

Nicholas Wormald

doi:10.1142/9789813272880_0180

Asymptotic enumeration of graphs with given degree sequence

Nicholas Wormald

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research

Abstract

We survey results on counting graphs with given degree sequence, focusing on asymptotic results, and mentioning some of the applications of these results. The main recent development is the proof of a conjecture that facilitates access to the degree sequence of a random graph via a model incorporating independent binomial random variables. The basic method used in the proof was to examine the changes in the counting function when the degrees are perturbed. We compare with several previous uses of this type of method.

Original language	English
Title of host publication	Proceedings of the International Congress of Mathematicians, ICM 2018
Subtitle of host publication	2018 International Congress of Mathematicians, ICM 2018; Rio de Janeiro; Brazil; 1 August 2018 through 9 August 2018
Editors	Boyan Sirakov, Paulo Ney de Souza, Marcelo Viana
Place of Publication	Singapore
Publisher	World Scientific Publishing
Pages	3263-3284
Number of pages	22
Volume	4
ISBN (Electronic)	9789813272934
DOIs	https://doi.org/10.1142/9789813272880_0180
Publication status	Published - 1 Jan 2018
Event	International Congress of Mathematicians 2018 - Barra da Tijuca, Rio de Janeiro, Brazil Duration: 1 Aug 2018 → 9 Aug 2018 https://icm2018.impa.br/portal/main.html

Publication series

Name	Proceedings of the International Congress of Mathematicians, ICM 2018
Volume	4

Conference

Conference	International Congress of Mathematicians 2018
Abbreviated title	ICM 2018
Country/Territory	Brazil
City	Rio de Janeiro
Period	1/08/18 → 9/08/18
Internet address	https://icm2018.impa.br/portal/main.html

Access to Document

10.1142/9789813272880_0180

Cite this

Wormald, N. (2018). Asymptotic enumeration of graphs with given degree sequence. In B. Sirakov, P. N. de Souza, & M. Viana (Eds.), Proceedings of the International Congress of Mathematicians, ICM 2018: 2018 International Congress of Mathematicians, ICM 2018; Rio de Janeiro; Brazil; 1 August 2018 through 9 August 2018 (Vol. 4, pp. 3263-3284). (Proceedings of the International Congress of Mathematicians, ICM 2018; Vol. 4). World Scientific Publishing. https://doi.org/10.1142/9789813272880_0180

Wormald, Nicholas. / Asymptotic enumeration of graphs with given degree sequence. Proceedings of the International Congress of Mathematicians, ICM 2018: 2018 International Congress of Mathematicians, ICM 2018; Rio de Janeiro; Brazil; 1 August 2018 through 9 August 2018. editor / Boyan Sirakov ; Paulo Ney de Souza ; Marcelo Viana. Vol. 4 Singapore : World Scientific Publishing, 2018. pp. 3263-3284 (Proceedings of the International Congress of Mathematicians, ICM 2018).

@inproceedings{148e7f1aae4a41c2bfceb44a3a4c2515,

title = "Asymptotic enumeration of graphs with given degree sequence",

abstract = "We survey results on counting graphs with given degree sequence, focusing on asymptotic results, and mentioning some of the applications of these results. The main recent development is the proof of a conjecture that facilitates access to the degree sequence of a random graph via a model incorporating independent binomial random variables. The basic method used in the proof was to examine the changes in the counting function when the degrees are perturbed. We compare with several previous uses of this type of method.",

author = "Nicholas Wormald",

year = "2018",

month = jan,

day = "1",

doi = "10.1142/9789813272880_0180",

language = "English",

volume = "4",

series = "Proceedings of the International Congress of Mathematicians, ICM 2018",

publisher = "World Scientific Publishing",

pages = "3263--3284",

editor = "Boyan Sirakov and {de Souza}, {Paulo Ney} and Marcelo Viana",

booktitle = "Proceedings of the International Congress of Mathematicians, ICM 2018",

address = "Singapore",

note = "International Congress of Mathematicians 2018, ICM 2018 ; Conference date: 01-08-2018 Through 09-08-2018",

url = "https://icm2018.impa.br/portal/main.html",

}

Wormald, N 2018, Asymptotic enumeration of graphs with given degree sequence. in B Sirakov, PN de Souza & M Viana (eds), Proceedings of the International Congress of Mathematicians, ICM 2018: 2018 International Congress of Mathematicians, ICM 2018; Rio de Janeiro; Brazil; 1 August 2018 through 9 August 2018. vol. 4, Proceedings of the International Congress of Mathematicians, ICM 2018, vol. 4, World Scientific Publishing, Singapore, pp. 3263-3284, International Congress of Mathematicians 2018, Rio de Janeiro, Brazil, 1/08/18. https://doi.org/10.1142/9789813272880_0180

Asymptotic enumeration of graphs with given degree sequence. / Wormald, Nicholas.

Proceedings of the International Congress of Mathematicians, ICM 2018: 2018 International Congress of Mathematicians, ICM 2018; Rio de Janeiro; Brazil; 1 August 2018 through 9 August 2018. ed. / Boyan Sirakov; Paulo Ney de Souza; Marcelo Viana. Vol. 4 Singapore : World Scientific Publishing, 2018. p. 3263-3284 (Proceedings of the International Congress of Mathematicians, ICM 2018; Vol. 4).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research

TY - GEN

T1 - Asymptotic enumeration of graphs with given degree sequence

AU - Wormald, Nicholas

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We survey results on counting graphs with given degree sequence, focusing on asymptotic results, and mentioning some of the applications of these results. The main recent development is the proof of a conjecture that facilitates access to the degree sequence of a random graph via a model incorporating independent binomial random variables. The basic method used in the proof was to examine the changes in the counting function when the degrees are perturbed. We compare with several previous uses of this type of method.

AB - We survey results on counting graphs with given degree sequence, focusing on asymptotic results, and mentioning some of the applications of these results. The main recent development is the proof of a conjecture that facilitates access to the degree sequence of a random graph via a model incorporating independent binomial random variables. The basic method used in the proof was to examine the changes in the counting function when the degrees are perturbed. We compare with several previous uses of this type of method.

UR - http://www.scopus.com/inward/record.url?scp=85086389945&partnerID=8YFLogxK

U2 - 10.1142/9789813272880_0180

DO - 10.1142/9789813272880_0180

M3 - Conference Paper

AN - SCOPUS:85086389945

VL - 4

T3 - Proceedings of the International Congress of Mathematicians, ICM 2018

SP - 3263

EP - 3284

BT - Proceedings of the International Congress of Mathematicians, ICM 2018

A2 - Sirakov, Boyan

A2 - de Souza, Paulo Ney

A2 - Viana, Marcelo

PB - World Scientific Publishing

CY - Singapore

T2 - International Congress of Mathematicians 2018

Y2 - 1 August 2018 through 9 August 2018

ER -

Wormald N. Asymptotic enumeration of graphs with given degree sequence. In Sirakov B, de Souza PN, Viana M, editors, Proceedings of the International Congress of Mathematicians, ICM 2018: 2018 International Congress of Mathematicians, ICM 2018; Rio de Janeiro; Brazil; 1 August 2018 through 9 August 2018. Vol. 4. Singapore: World Scientific Publishing. 2018. p. 3263-3284. (Proceedings of the International Congress of Mathematicians, ICM 2018). https://doi.org/10.1142/9789813272880_0180

Asymptotic enumeration of graphs with given degree sequence

Abstract

Publication series

Conference

Access to Document

Other files and links

Advances in the analysis of random structures and their applications: relationships among models

Cite this

Asymptotic enumeration of graphs with given degree sequence

Abstract

Publication series

Conference

Access to Document

Other files and links

Projects

Advances in the analysis of random structures and their applications: relationships among models

Cite this