Largest subgraph from a hereditary property in a random graph.

Let P be a non-trivial hereditary property of graphs and let k be the minimum chromatic number of a graph that does not belong to P. We prove that, for every fixed p ∈ (0 , 1) , the maximum possible number of edges in a subgraph of the random graph G (n , p) which belongs to P is, with high probability, (1 − 1 k − 1 + o (1)) p ( n 2 ). [ABSTRACT FROM AUTHOR]