= Hereditary graph enumeration theorem
{title2=$|\mathcal P_n|=2^{(1-1/r(\mathcal P)+o(1))\binom n2}$}
= Alekseev-Bollobás-Thomason theorem
{c}
{synonym}
For a proper hereditary <graph> property with unbounded orders, the colouring number determines the leading labelled speed. The lower bound comes from one contained <clique-independent partition class>. For the upper bound, forbid one induced <graph> from each next-size partition type and use the <induced regularity template lemma>. Its intermediate-pair <graph> is clique-free, and sparse or almost-complete pairs have negligible entropy. Bounded-order properties have colouring number zero and are outside this formula.
Back to article page
