%A Balogh, Jozsef
%A Zhukovskii, Maksim
%D 2019
%T Maximum induced subgraphs of the binomial random graph
%K
%X 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}$.
%U http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1217
%J Acta Mathematica Universitatis Comenianae
%0 Journal Article
%P 423-427%V 88
%N 3
%@ 0862-9544
%8 2019-07-25