A critical point for random graphs with a given degree sequence

TLDR

Random graphs are studied with a given degree sequence defined by nonnegative real numbers λ_i summing to one, yielding approximately λ_i n vertices of degree i. The paper investigates the emergence of a giant component in such random graphs based on the sign of Σ i(i−2)λ_i. The authors apply their results to classic models such as G(n,p) and G(n,m), and explore implications for the chromatic number of sparse random graphs. They prove that if Σ i(i−2)λ_i > 0, a giant component almost surely exists, whereas if Σ i(i−2)λ_i < 0, all components remain small.

Abstract

Abstract Given a sequence of nonnegative real numbers λ 0 , λ 1 … which sum to 1, we consider random graphs having approximately λ i n vertices of degree i. Essentially, we show that if Σ i(i ‐ 2)λ i &gt; 0, then such graphs almost surely have a giant component, while if Σ i ( i ‐ 2)λ. &lt; 0, then almost surely all components in such graphs are small. We can apply these results to G n,p ,G n.M , and other well‐known models of random graphs. There are also applications related to the chromatic number of sparse random graphs.