Giant components in biased graph processes

Gideon Amir, Ori Gurel-Gurevich, Eyal Lubetzky, Amit Singer

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

A random graph process, G1(n), is a sequence of graphs on n vertices which begins with the edgeless graph, and where at each step a single edge is added according to a uniform distribution on the missing edges. It is well known that in such a process a giant component (of linear size) typically emerges after (1+o(1))n=2 edges (a phenomenon known as "the double jump"), i.e., at time t = 1 when using a timescale of n/2 edges in each step.

Original languageEnglish (US)
Pages (from-to)1853-1888
Number of pages36
JournalIndiana University Mathematics Journal
Volume59
Issue number6
DOIs
StatePublished - Dec 1 2010

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Giant component
  • Random graphs
  • Wormald's differential equation method

Fingerprint Dive into the research topics of 'Giant components in biased graph processes'. Together they form a unique fingerprint.

  • Cite this