Maximum induced subgraphs of the binomial random graph

Abstract

We prove that a.a.s. the maximum size of an induced tree in the binomial random graph $G(n,p)$ is concentrated in four consecutive points. We also consider the following problem. Given $e(k)$, what is the maximum $k$ such that $G(n,p)$ has an induced subgraph with $k$ vertices and $e(k)$ edges? For $e=o(\frac{k\ln k}{\ln\ln k})$, we prove that a.a.s. this maximum size is concentrated in two consecutive points. In contrast, for $e(k)=p{k\choose 2}+O(k)$, we prove that this size is not concentrated in any finite set. Moreover, we prove that for an $\omega_n\to\infty$, a.a.s.~the size of the concentration set is smaller than $\omega_n\sqrt{n/\ln n}$. Otherwise, for an arbitrary constant $C>0$, a.a.s.~it is bigger than $C\sqrt{n/\ln n}$.