<p>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) <em>speed</em> 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$.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Partition_%28number_theory%29">integer partitions</a>, 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))$.</p>

<ul>
<li>József Balogh, Béla Bollobás, Michael Saks and Vera T. Sós, <em>The unlabelled speed of a hereditary graph property</em>, Journal of Combinatorial Theory, Series B, <strong>99</strong> 9–19, 2009.
doi:<a href="http://dx.doi.org/10.1016/j.jctb.2008.03.004">10.1016/j.jctb.2008.03.004</a> (<a href="http://www.math.uiuc.edu/~jobal/cikk/divsub.ps">preprint</a>)</li>
</ul>

CC BY-SA 3.0
2015-07-30T13:46:29.490Z
2015-07-30T13:46:29.490Z
András Salamon
<p>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.</p>

CC BY-SA 3.0
2015-07-30T05:29:31.727Z
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$.
David Eppstein
CC BY-SA 3.0
2015-07-30T09:38:52.910Z
@Andras Farago: A no-answer can also be directly deduced from known results on the Erdos-Hajnal conjecture [https://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}))$.
Louis Esperet
CC BY-SA 3.0
2015-07-30T10:14:04.220Z
@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$.
Louis Esperet
CC BY-SA 3.0
2015-07-30T05:15:48.427Z
2015-07-30T05:15:48.427Z
daniello
<p>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 <em>almost all</em> graphs, if the fraction of all $n$-vertex graphs falling in $Q_n$ approaches 1, as $n\rightarrow\infty$. </p>

<p><strong>Question:</strong> 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$? </p>

<graph-theory>
Can a hereditary graph class contain almost all, but not all, n-vertex graphs?
Andras Farago
# Can a hereditary graph class contain almost all, but not all, n-vertex graphs?

(Asked by: username_0 on 2015-07-29)

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$?

**Tags:** graph-theory


---

## 2 answers

### Answer by username_2 on 2015-07-30. Score: 10 | Accepted answer

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.

> **Comments:**
> **username_3**: 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$.  
> **username_4**: @username_0: A no-answer can also be directly deduced from known results on the Erdos-Hajnal conjecture [https://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}))$.  
> **username_4**: @username_3: 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$.  

---

### Answer by username_1 on 2015-07-30. Score: 10

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](http://en.wikipedia.org/wiki/Partition_%28number_theory%29), 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))$.

* József Balogh, Béla Bollobás, Michael Saks and Vera T. Sós, *The unlabelled speed of a hereditary graph property*, Journal of Combinatorial Theory, Series B, **99** 9–19, 2009.
  doi:[10.1016/j.jctb.2008.03.004](http://dx.doi.org/10.1016/j.jctb.2008.03.004) ([preprint](http://www.math.uiuc.edu/~jobal/cikk/divsub.ps))


---

