Largest subgraph from a hereditary property in a random graph

Abstract

We prove that for every non-trivial hereditary family of graphs $\mathcal{P}$ and for every fixed $p\in (0,1)$, the maximum possible number of edges in a subgraph of the random graph $G(n,p)$ which belongs to $\mathcal{P}$ is, with high probability, $$\left(1-\frac{1}{k-1}+o(1)\right)p\left(\genfrac{}{}{0ex}{}{n}{2}\right),$$ where $k$ is the minimum chromatic number of a graph that does not belong to $\mathcal{P}$.