Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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))$.
