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$
  • $\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 Jul 6 '16 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 Oct 25 '16 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 Oct 25 '16 at 9:30

Your Answer

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

Browse other questions tagged or ask your own question.