Subgraphs of random graphs in hereditary families

Abstract

For a graph $G$ and a hereditary property $\mathcal{P}$, let $\text{ex}(G,\mathcal{P})$ denote the maximum number of edges of a subgraph of $G$ that belongs to $\mathcal{P}$. We prove that for every non-trivial hereditary property $\mathcal{P}$ such that $L\notin \mathcal{P}$ for some bipartite graph $L$ and for every fixed $p\in (0,1)$ we have \[\text{ex}(G(n,p),\mathcal{P}) \le n^{2-\varepsilon}\] with high probability, for some constant $\epsilon =\epsilon (\mathcal{P})>0$. This answers a question of Alon, Krivelevich and Samotij.

5 pages