Non-isomorphic subgraphs in random graphs

We establish the asymptotic behaviour of $\mu (G(n,p))$, the number of unlabelled induced subgraphs in the binomial random graph $G(n,p)$, for almost the entire range of the probability parameter $p=p(n)\in [0,1]$. In particular, we show that typically the number of subgraphs becomes exponential when $p$ passes $1\mathrm{/}n$, reaches maximum possible base of exponent (asymptotically) when $p\gg 1\mathrm{/}n$, and reaches the asymptotic value $2^n$ when $p$ passes $2\ln n\mathrm{/}n$. For $p\gg \ln n\mathrm{/}n$, we get the first order term and asymptotics of the second order term of $\mu (G(n,p))$. We also prove that random regular graphs $G_{n,d}$ typically have $\mu (G_{n,d})\ge 2^{c_{d}n}$ for all $d\ge 3$ and some positive constant $c_d$ such that $c_d\to 1$ as $d\to \mathrm{\infty }$.