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$
4
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.