# Can a hereditary graph class contain almost all, but not all, n-vertex graphs?

Let $Q$ be a hereditary class of graphs. (Hereditary = closed with respect to taking induced subgraphs.) Let $Q_n$ denote the set of $n$-vertex graphs in $Q$. Let us say that $Q$ contains almost all graphs, if the fraction of all $n$-vertex graphs falling in $Q_n$ approaches 1, as $n\rightarrow\infty$.

Question: Is it possible that a hereditary graph class $Q$ contains almost all graphs, but for every $n$ there is at least one graph that is not in $Q_n$?

The answer is no - for a fixed $Q$ let $t$ be the number of vertices in the smallest graph $H$ not in $Q$. Now, consider $n$ much bigger than $t$. For a random graph on $n$ vertices, the probability that the $t$ first vertices induce $H$ depends only on $t$. Partitioning the vertex set into $n/t$ disjoint sets of size $t$ and considering the probability that none of the sets are equal to $H$ shows that the probability of being in $Q$ tends to $0$ as $n$ increases.
• This proves more strongly that any nontrivial hereditary class contains a fraction of all graphs that shrinks as $\exp -cn$. By partitioning $K_n$ into many edge-disjoint $K_t$'s and using the same argument it should be possible to strengthen this into something more like $\exp -cn^2$. Jul 30 '15 at 5:29
• @Andras Farago: A no-answer can also be directly deduced from known results on the Erdos-Hajnal conjecture [en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Hajnal_conjecture]. The bound obtained is not as good (it seems that you only get a fraction of $\exp(-\exp(c \sqrt{\log n}))$. Jul 30 '15 at 9:38
• @David Eppstein: I think $\exp -cn^2$ is precisely what you get by recursively applying ($\log \log n$ times) the following classical result. If there is a projective plane of order $q$ then the edge-set of $K_{q^2}$ can be partitioned into $q(q+1)$ edge-disjoint copies of $K_q$. Jul 30 '15 at 10:14
To add to Daniel's answer, the precise density of hereditary classes has been extensively investigated in combinatorics. For a class $C$ of structures, the unlabelled slice $C_n$ is the set of isomorphism classes of structures in $C$ that have $n$ vertices. The (unlabelled) speed of a class $C$ of structures is $|C_n|$. Denote the class of graphs by $G$. The question is asking whether $\lim_{n\to \infty} |Q_n|/|G_n| = 1$ for any hereditary class of graphs $Q$.
Since the limit is always 0 for hereditary $Q$, a fundamental question is then how the function $|Q_n|$ itself behaves. Let $p(n)$ denote the number of integer partitions, where $p(n) = 2^{\Theta(\sqrt{n})}$. It turns out that the unlabelled speed "jumps": either $|Q_n|$ is polynomially bounded, or otherwise $|Q_n| = \Omega(p(n))$.