Maximum sparse induced subgraphs of the binomial random graph with given number of edges

Dmitry Kamaldinov, Arkadiy Skorkin, Maksim Zhukovskii

We prove that a.a.s. the maximum size of an induced subtree of the binomial random graph $G(n,p)$ is concentrated in 2 consecutive points. We also prove that, given a non-negative…