On the sizes of large subgraphs of the binomial random graph

Jozsef Balogh, Maksim Zhukovskii

Published 2019-04-10Version 1

In the paper, we answer the following two questions. Given $e(k)=p{k\choose 2}+O(k)$, what is the maximum $k$ such that $G(n,p)$ has an induced subgraph with $k$ vertices and $e(k)$ edges? Given $k>\varepsilon n$, what is the maximum $\mu$ such that a.a.s.~the set of sizes of $k$-vertex subgraphs of $G(n,p)$ contains a full interval of length $\mu$? We prove that the value $\mathcal{X}_n$ from the first question is not concentrated in any finite set (in contrast to the case of a small $e=e(k)$). 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}$. Our answer on the second question is the following: $\mu=\Theta(\sqrt{(n-k)n\ln{n\choose k}})$.