The structure of almost all graphs in a hereditary property (Q631643)

A hereditary property of graphs is a set of graphs which is closed under taking induced subgraphs. Given a hereditary property \(\mathcal{P}\), let \(\mathcal{P}_n\) denote the set of the graphs from \(\mathcal{P}\) with vertex set \([n]\). The \textit{speed} of \(\mathcal{P}\) is the function \(n \mapsto |\mathcal{P}_n|\), and it was shown by \textit{V. E. Alekseev} [Discrete Math. Appl. 3, No.\,2, 191--199 (1993; Zbl 0797.05077)], and by \textit{B. Bollobás} and \textit{A. Thomason} [Algorithms Comb. 14, 70--78 (1997; Zbl 0866.05030)] that if \(\mathcal{P}\) is a hereditary property, then \[ |\mathcal{P}_n| = 2^{(1 - 1/ \chi_c(\mathcal{P}) + o(1)){n \choose 2}} \] where \(\chi_c(\mathcal{P})\) is the `colouring number' of \(\mathcal{P}\). The main result of the paper describes the structure of almost all graphs in a hereditary property as follows as. If \(\mathcal{P}\) is a hereditary property with \(r := \chi_c(\mathcal{P})\), then there are constants \(k = k(\mathcal{P}) \in \mathbb{N}\) and \(\epsilon = \epsilon(\mathcal{P}) > 0\) such that the following holds. For almost all graphs \(G \in \mathcal{P}\), there is a partition \((A, S_1, \dots, S_r)\) of the vertex set of \(G\) such that (i) \(|A| \leq n^{1 - \epsilon}\) and (ii) the induced graph \(G[S_j]\) is \(U(k)\)-free for every \(j \in [r]\). Moreover, \[ 2^{(1 - 1/r){n \choose 2}} \leq |\mathcal{P}_n| \leq 2^{(1 - 1/r){n \choose 2} + n^{2 - \epsilon} } \] for all sufficiently large integers \(n\). In the above, \(U(k)\) denotes the \textit{universal graph} which is the bipartite graph with parts \(A = \{0,1 \}^k\) (the set of all \(k\)-dimensional binary vectors) and \(B = [k]\), and \(a = (a_i) \in A\) and \(b \in B\) are adjacent in \(U(k)\) if \(b \subseteq \{ i \mid a_i = 1 \}\).