The structure of almost all graphs in a hereditary property

A hereditary property of graphs is a collection of graphs which is closed under taking induced subgraphs. The speed of PP is the function n↦|Pn|n↦|Pn|, where PnPn denotes the graphs of order n   in PP. It was shown by Alekseev, and by Bollobás and Thomason, that if PP is a hereditary property of graphs then|Pn|=2(1−1/r+o(1))(n2), where r=r(P)∈Nr=r(P)∈N is the so-called ‘colouring number’ of PP. However, their results tell us very little about the structure of a typical graph G∈PG∈P.In this paper we describe the structure of almost every graph in a hereditary property of graphs, PP. As a consequence, we derive essentially optimal bounds on the speed of PP, improving the Alekseev–Bollobás–Thomason Theorem, and also generalising results of Balogh, Bollobás and Simonovits.