5
$\begingroup$

ER random graphs in $G(n,m)$ model are known to have a giant component when $m>n/2$ which grows to a value of $\Theta(n)$ very abruptly. Also the size of the second largest component is known to have a maximum value of $n^{2/3}/2$ during the phase transition for a very short period of time, remaining $O(\log n)$ for most time.

Following is the experimental evaluation of varying component sizes for n=1000.

Graph shows Size of components Vs Number of edges (m) in the graph, where number of components for a given size is shown by frequency map. Size of components Vs Number of edges (m) in the graph, where number of components for a given size is shown by frequency map.

Is there any literature available about the fraction of vertices in components of size $\Omega(f(n))$ excluding the giant component. From what I understand it should be very small fraction (~$O(n^{2/3})$) even if $f(n)=\log n$ but I couldn't find any concrete literature.

Please guide me to any concrete results available regarding the number of such vertices.

$\endgroup$
3
  • $\begingroup$ You can get what you want from the discrete duality principle, which was proven for the more complex model of random graphs with a fixed degree sequence. See the answer there: mathoverflow.net/questions/127821/… $\endgroup$
    – logicute
    Commented Jul 6, 2016 at 10:36
  • $\begingroup$ Take $p=c/n, c>1$ and consider the $G_n(p)$ model ; a.a.s., you have NO vertex in components with size in between $D \log n$ and $D' n$, where $D$ and $D'$ are two appropriately chosen constants: if $\phi$ is the rate function for the Poisson(c) random variable, $\phi(c)=c-1-\log(c)$, and $\theta(c)= \exp{-c(1-\theta(c))}$ is the extinction probability of the Poisson(c) Galton Watson tree, these constants should satisfy $D \phi(c) >1$ and $D' < 1- \theta(c)$. $\endgroup$
    – Olivier
    Commented Oct 25, 2016 at 9:21
  • $\begingroup$ This is in strong contrast with the critical case $c=1$ where you have many vertices (about $n/(\log n)^{1/2}$) in components with size in between $\log(n)$ and $\log(n) \omega(n)$ for any diverging $\omega(n)$. All these intermediate components a.a.s. have merged in the giant in the supercritical phase $c>1$. For this and much more, have a look at the first chapter of link.springer.com/book/10.1007%2F978-3-540-69395-6 $\endgroup$
    – Olivier
    Commented Oct 25, 2016 at 9:30

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.