8
$\begingroup$

Suppose we have an instance of Erdős-Renyi $G(n,p)$ graph with $p = d/n$. Thus the expected node degree is $d$ which we will fix, while letting $n \to \infty$. Then, there will be more than one connected component (CC) for large $n$.

Suppose that we pick the largest CC and relabel the nodes randomly from $1,\dots,s$ where $s$ is the size of the component. Is there a way to describe the distribution of these connected graphs as $n \to \infty$? The edges are no longer independent, but can we approximate the whole distribution with another Erdős-Renyi graph with modified parameters (say increased $p$)?

$\endgroup$

1 Answer 1

5
$\begingroup$

If $d>1$, the paper Anatomy of the giant component: the strictly supercritical regime by Ding, Lubetzky and Peres might be what you are looking for. The paper also has references for the cases $d<1$ and $d=1$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .