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).
|Original language||English (US)|
|Number of pages||5|
|Journal||Acta Mathematica Universitatis Comenianae|
|State||Published - Sep 2 2019|
ASJC Scopus subject areas