Critical random graphs and the differential equations technique

Shankar Bhamidi (), Amarjit Budhiraja () and Sanchayan Sen ()
Additional contact information
Shankar Bhamidi: University of North Carolina
Amarjit Budhiraja: University of North Carolina
Sanchayan Sen: McGill University

Indian Journal of Pure and Applied Mathematics, 2017, vol. 48, issue 4, 633-669

Abstract: Abstract Over the last few years a wide array of random graph models have been postulated to understand properties of empirically observed networks. Most of these models come with a parameter t (usually related to edge density) and a (model dependent) critical time t c that specifies when a giant component emerges. There is evidence to support that for a wide class of models, under moment conditions, the nature of this emergence is universal and looks like the classical Erdős-Rényi random graph, in the sense of the critical scaling window and (a) the sizes of the components in this window (all maximal component sizes scaling like n2/3) and (b) the structure of components (rescaled by n−1/3) converge to random fractals related to the continuum random tree. The aim of this note is to give a non-technical overview of recent breakthroughs in this area, emphasizing a particular tool in proving such results called the differential equations technique first developed and used extensively in probabilistic combinatorics in the work of Wormald [52, 53] and developed in the context of critical random graphs by the authors and their collaborators in [10–12].

Keywords: Multiplicative coalescent; continuum random tree; critical random graphs; branching processes; inhomogeneous random graphs; configuration model; bounded-size rules (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13226-017-0249-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:indpam:v:48:y:2017:i:4:d:10.1007_s13226-017-0249-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/13226

DOI: 10.1007/s13226-017-0249-0

Access Statistics for this article

Indian Journal of Pure and Applied Mathematics is currently edited by Nidhi Chandhoke

More articles in Indian Journal of Pure and Applied Mathematics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().