NDLI: Birth control for giants

Please wait, while we are loading the content...

Birth control for giants

Content Provider	Springer Nature Link
Author	Spencer, Joel Wormald, Nicholas
Copyright Year	2007
Abstract	The standard Erdős-Rényi model of random graphs begins with n isolated vertices, and at each round a random edge is added. Parametrizing n/2 rounds as one time unit, a phase transition occurs at time t = 1 when a giant component (one of size constant times n) first appears. Under the influence of statistical mechanics, the investigation of related phase transitions has become an important topic in random graph theory.We define a broad class of graph evolutions in which at each round one chooses one of two random edges {v 1, v 2}, {v 3, v 4} to add to the graph. The selection is made by examining the sizes of the components of the four vertices. We consider the susceptibility S(t) at time t, being the expected component size of a uniformly chosen vertex. The expected change in S(t) is found which produces in the limit a differential equation for S(t). There is a critical time t c so that S(t) → ∞ as t approaches t c from below. We show that the discrete random process asymptotically follows the differential equation for all subcritical t < t c . Employing classic results of Cramér on branching processes we show that the component sizes of the graph in the subcritical regime have an exponential tail. In particular, the largest component is only logarithmic in size. In the supercritical regime t > t c we show the existence of a giant component, so that t = t c may be fairly considered a phase transition.Computer aided solutions to the possible differential equations for susceptibility allow us to establish lower and upper bounds on the extent to which we can either delay or accelerate the birth of the giant component.
Ending Page	628
Page Count	42
Starting Page	587
File Format	PDF
ISSN	02099683
e-ISSN	14396912
Journal	Combinatorica
Issue Number	5
Volume Number	27
Language	English
Publisher	Springer-Verlag
Publisher Date	2008-05-29
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Random graphs Mathematics Combinatorics
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Generating Random Regular Graphs

OnK 4-free subgraphs of random graphs

Online vertex-coloring games in random graphs

Note on limits of finite graphs

K 4-free subgraphs of random graphs revisited

Random Subgraphs Of Finite Graphs: III. The Phase Transition For The n-Cube

Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs

The concentration of the chromatic number of random graphs

Random Lifts Of Graphs: Perfect Matchings

Birth control for giants

Similar Documents

Generating Random Regular Graphs

OnK 4-free subgraphs of random graphs

Online vertex-coloring games in random graphs

Note on limits of finite graphs

K 4-free subgraphs of random graphs revisited

Random Subgraphs Of Finite Graphs: III. The Phase Transition For The n-Cube

Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs

The concentration of the chromatic number of random graphs

Random Lifts Of Graphs: Perfect Matchings

Birth control for giants