= Enumeration of subgraph-closed graph properties
{title2=$\log_2|\mathcal Q_n|=(1-1/r+o(1))\binom n2$}
Here $r+1$ is the least chromatic number of an excluded <graph>, for a proper unbounded subgraph-closed property. All subgraphs of a balanced <Turan graph> give the lower bound. For the upper bound, a regularity reduced <graph> is clique-free, so its dense pairs have the <Turan theorem> <edge> bound; sparse pairs contribute only small binary entropy and the bounded partition description costs only a linear number of bits.
Back to article page
