Global properties of hereditary classes?

Question

A hereditary class of structures (e.g. graphs) is one that is closed under induced substructures, or equivalently, is closed under vertex removal.

Classes of graphs that exclude a minor have nice properties that do not depend on the specific excluded minor. Martin Grohe showed that for graph classes excluding a minor there is a polynomial algorithm for isomorphism, and fixed-point logic with counting captures polynomial time for these graph classes. (Grohe, Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors, LICS, 2010.) These can be thought of as "global" properties.

Are there similar "global" properties known for hereditary classes (either graphs or more general structures)?

It would be good to see each answer focus on just one specific property.

Answer 1

Hereditary properties are very "robust" in the following sense.

Noga Alon and Asaf Shapira showed that for any hereditary property ${\cal P}$, if a graph $G$ needs more than $\epsilon n^2$ edges to be added or removed in order to satisfy ${\cal P}$, then there is a subgraph in $G$, of size at most $f_{\cal P}(\epsilon)$, which does not satisfy ${\cal P}$. Here, the function $f$ only depends on the property ${\cal P}$ (and not on the size of the graph $G$, for instance). Erdős had made such a conjecture only about the property of $k$-colorability.

Indeed, Alon and Shapira prove the following stronger fact: given ${\cal P}$, for any $\epsilon$ in $(0,1)$, there are $N(\epsilon)$, $h(\epsilon)$ and $\delta(\epsilon)$ such that if a graph $G$ has at least $N$ vertices and needs at least $\epsilon n^2$ edges added/removed in order to satisfy ${\cal P}$, then for at least $\delta$ fraction of induced subgraphs on $h$ vertices, the induced subgraph violates ${\cal P}$. Thus, if $\epsilon$ and the property ${\cal P}$ are fixed, in order to test if an input graph satisfies ${\cal P}$ or is $\epsilon$-far from satisfying ${\cal P}$, then one only needs to query the edges of a random induced subgraph of constant size from the graph and check if it satisfies the property or not. Such a tester would always accept graphs satisfying ${\cal P}$ and would reject graphs $\epsilon$-far from satisfying it with constant probability. Furthermore, any property that is one-sided testable in this sense is a hereditary property! See the paper by Alon and Shapira for details.

Answer 2

This may not be quite what you had in mind, but there are known restrictions on how many graphs on $n$ vertices there can be in a hereditary class of graphs. For example, there is no hereditary class of graphs that has between $2^{\Omega(n)}$ and $2^{o(n\log{n})}$ graphs on $n$ vertices.

Reference: E. Scheinerman, J. Zito, On the Size of Hereditary Classes of Graphs, Journal of Combinatorial Theory Series B

Answer 3

This is related to Travis's answer. In fact, it could be considered a stronger version.

A paper by Bollob\'as and Thomason (Combinatorica, 2000) shows that in Erd\H{o}s-R\'enyi random graphs $G_{n,p}$ (with $p$ some fixed constant), every hereditary property can be approximated by what they call a basic property. Basic almost means graphs whose vertex sets are unions of $r$ classes, $s$ of which span cliques and $r-s$ of which span independent sets, but not quite. This approximation is used to characterise the size of a largest $\mathcal{P}$-set as well as the $\mathcal{P}$-chromatic number of $G_{n,p}$, where $\mathcal{P}$ is some fixed hereditary property. If $p$ permitted to vary, the behaviour is not well-understood.

For more background to this and related work, there is a survey by Bollob\'as (Proceedings of the ICM 1998) which also gives an enticing conjecture along these lines but for hypergraphs.

I find the deep connection between hereditary properties and Szem\'eredi's Regularity Lemma very intriguing, as it was used both here and in the Alon and Shapira result.

Answer 4

Suresh's answer about the AKR conjecture got me thinking about the same conjecture for hereditary properties. I think (unless I've made a mistake) I can show that all non-trivial hereditary properties have (randomized and deterministic) decision tree complexity $\Theta(n^2)$, which settles the AKR conjecture for such properties (up to constants).

I tried to search the literature to see if this has been shown somewhere, but I couldn't find a reference. So either I couldn't find it but it exists, or the theorem is uninteresting, or I've made an error.

So, this is another example of a global property of all hereditary graph properties.

Answer 5

According to the Erdős–Hajnal conjecture, every hereditary family has the property that the graphs in it either have cliques or independent sets of polynomial size (that is, $\Omega(n^c)$ for some $c>0$ that depends on the family but not on the graph). This is in contrast to random graphs, where the largest clique and the largest independent set are both logarithmic.

Answer 6

This is the "reverse" direction, but the well known Aanderaa-Rosenberg-Karp conjecture applies to graph properties that are monotone upwards (i.e if G satisfies the property, then so does any graph on the same nodes whose edge set contains E(G)).