For a graph G and a hereditary property P, let ex(G,P) denote the maximum number of edges of a subgraph of G that belongs to P. We prove that for every non-trivial hereditary property P such that L ∉ P for some bipartite graph L and for every fixed p ∈ (0,1) we have \[ex(G(n,p),P) ≤ n2-ε\] with high probability, for some constant ε = ε(P)>0. This answers a question of Alon, Krivelevich and Samotij.
No takes yet. Share an insight, caveat, or question.
Clifton et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: