Giant Components in Biased Graph Processes

Preprint English OPEN
Amir, Gideon; Gurel-Gurevich, Ori; Lubetzky, Eyal; Singer, Amit;
  • Subject: Mathematics - Combinatorics | Mathematics - Probability | 05C80,60C05 | Mathematics - Analysis of PDEs

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 c... View more
  • References (9)

    [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.

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

  • Metrics
Share - Bookmark