10
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ 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$. $\endgroup$ – David Eppstein Jul 30 '15 at 5:29
  • $\begingroup$ @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}))$. $\endgroup$ – Louis Esperet Jul 30 '15 at 9:38
  • 1
    $\begingroup$ @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$. $\endgroup$ – Louis Esperet Jul 30 '15 at 10:14
10
$\begingroup$

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))$.

  • 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 (preprint)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.