Typical structure of hereditary graph families. I. Apex-free families

Abstract

A family of graphs $\mathcal{F}$ is hereditary if $\mathcal{F}$ is closed under isomorphism and taking induced subgraphs. The speed of $\mathcal{F}$ is the sequence $\{|{\mathcal{F}}^n|{\}}_{n\in \mathbb{N}}$, where ${\mathcal{F}}^n$ denotes the set of graphs in $\mathcal{F}$ with the vertex set $[n]$. Alon, Balogh, Bollobás and Morris [The structure of almost all graphs in a hereditary property, JCTB 2011] gave a rough description of typical graphs in a hereditary family and used it to show for every proper hereditary family $\mathcal{F}$ there exist $\epsilon >0$ and an integer $l\ge 1$ such that $$|{\mathcal{F}}^n|=2^{(1-1/l)n^2/2+o(n^{2-\epsilon })}.$$ The main result of this paper gives a more precise description of typical structure for a restricted class of hereditary families. As a consequence we characterize hereditary families with the speed just above the threshold $2^{(1-1/l)n^2/2}$, generalizing a result of Balogh and Butterfield [Excluding induced subgraphs: Critical graphs, RSA 2011].