publication . Article . Preprint . 2005

Giant components in biased graph processes

Amir, Gideon; Gurel-Gurevich, Ori; Lubetzky, Eyal; Singer, Amit;
Open Access
  • Published: 21 Nov 2005 Journal: Indiana University Mathematics Journal, volume 59, pages 1,893-1,930 (issn: 0022-2518, Copyright policy)
  • Publisher: Indiana University Mathematics Journal
Abstract
A random graph process, $\Gorg[1](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))\frac{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. We consider a generalization of this process, $\Gorg[K](n)$, which gives a weight of size 1 to missing edges between pairs of isolated vertices, and a weight of size $K \in [0,\infty)$ otherwise. This corr...
Subjects
free text keywords: General Mathematics, Giant component, Differential equation, Approximations of π, Biased graph, Random graph, Uniform distribution (continuous), Mathematics, Singularity, Mathematical analysis, Combinatorics, Discrete mathematics, Topology, Vertex (geometry), Mathematics - Probability, Mathematics - Analysis of PDEs, Mathematics - Combinatorics, 05C80,60C05

[7] A. Flaxman, D. Gamarnik and G. Sorkin, Embracing the giant component, Random Structures and Algorithms, 27 (2005), 277-289.

[8] T. H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, The MIT Press/McGraw-Hill (1990).

[9] P. Erd˝os and A. R´enyi, On the evolution of random graphs, Publ. math. Inst. Hungar. Acad. Sci., 5 (1960), 17-61.

[10] L. Lov´asz and M.D. Plummer, Matching Theory, North-Holland, Amsterdam (1986).

[11] G.M. Murphy, Ordinary Differential Equations and Their Solutions, D. van Nostrand Comp., Inc. Princeton, New Jersey (1960).

[12] C.J. Preston, A generalization of the FKG inequalities. Communications in Mathematical Physics, 36 (1974), 233-241.

[13] J. Spencer and N. Wormald, Birth control for giants, Combinatorica, 27 (2007), 587-628.

[14] V. Strassen, The existence of probability measures with given marginals, Annals of Mathematical Statistics, 36 (1965), 423-439. [OpenAIRE]

[15] N.C. Wormald, Analysis of greedy algorithms on graphs with bounded degrees, Discrete Mathematics, 273 (2003), 235-260. [OpenAIRE]

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Article . Preprint . 2005

Giant components in biased graph processes

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