Maximum induced subgraphs of the binomial random graph

We prove that a.a.s. the maximum size of an induced tree in the bi- nomial 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 (Formula presented), we prove that a.a.s. this maximum size is concentrated in two consecutive points. In contrast, for e(k) = p(k/2)+O(k), we prove that this size is not concentrated in any finite set. Moreover, we prove that for an ω_n→ ∞, a.a.s. the size of the concentration set is smaller than (Formula presented). Otherwise, for an arbitrary constant C > 0, a.a.s. it is bigger than (Formula presented).