On the connectivity threshold of Achlioptas processes (Q482273)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the connectivity threshold of Achlioptas processes
scientific article

    Statements

    On the connectivity threshold of Achlioptas processes (English)
    0 references
    0 references
    22 December 2014
    0 references
    This paper studies the connectivity threshold of Achlioptas processes. The random graph in question becomes connected with high probability as the number of vertices \(n\) tends to infinity when the number of edges is asymptotically \(\frac14n\ln n\). This is shown via examining the emergence of giant components and the differential equations method for the phase transition in bounded-size Achlioptas processes. Moreover, the connectivity threshold of the Bohman-Frieze processes is also discussed with similar line of reasoning.
    0 references
    0 references
    connectivity
    0 references
    threshold
    0 references
    Achlioptas process
    0 references

    Identifiers