<p>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.</p>

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

CC BY-SA 2.5
2010-09-06T12:29:25.827Z
These properties certainly qualify: I think the quantity you refer to is called "speed".
András Salamon
CC BY-SA 2.5
2010-09-05T22:26:36.697Z
2010-09-05T22:26:36.697Z
Travis Service
<p>This is related to Travis's answer.  In fact, it could be considered a stronger version.</p>

<p>A <a href="http://dx.doi.org/10.1007/s004930070019" rel="nofollow">paper by Bollob\'as and Thomason</a> (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 <em>basic</em> property.  Basic <em>almost</em> 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.</p>

<p>For more background to this and related work, there is a <a href="http://www.emis.de/journals/DMJDMV/xvol-icm/13/Bollobas.MAN.html" rel="nofollow">survey by Bollob\'as</a> (Proceedings of the ICM 1998) which also gives an enticing conjecture along these lines but for hypergraphs.</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-27T19:08:24.413Z
Thanks Ross.  The link you highlight between hereditary properties and the Regularity Lemma would make for some interesting questions.
András Salamon
CC BY-SA 2.5
2010-10-27T14:07:36.600Z
2010-10-27T23:08:48.743Z
2010-10-27T23:08:48.743Z
RJK
<p>According to the <a href="http://garden.irmacs.sfu.ca/?q=op/the_erdos_hajnal_conjecture" rel="nofollow">Erdős–Hajnal conjecture</a>, 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.</p>

CC BY-SA 2.5
2010-10-28T11:53:26.397Z
This is potentially a very interesting example, but some excellent structural graph theorists I know believe it is false!
RJK
CC BY-SA 2.5
2010-10-28T04:42:54.003Z
2010-10-28T04:42:54.003Z
David Eppstein
<p>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).</p>

<p>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.</p>

<p>So, this is another example of a global property of all hereditary graph properties.</p>

CC BY-SA 2.5
2010-09-17T13:19:47.453Z
I would be very interested in reading a draft with your results.
András Salamon
CC BY-SA 2.5
2010-09-18T03:30:39.380Z
I'll let you know when I get around to writing it up. I'm also reasonably confident that this should follow from some well-known lower bounds in this area. Unfortunately I don't know any expert in this area who I can ask.
Robin Kothari
CC BY-SA 2.5
2010-09-16T17:54:48.467Z
2010-09-16T17:54:48.467Z
Robin Kothari
<p>This is the "reverse" direction, but the well known <a href="http://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture" rel="nofollow">Aanderaa-Rosenberg-Karp conjecture</a> 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)). </p>

CC BY-SA 2.5
2010-09-05T23:15:51.153Z
The AKR conjecture equally applies to properties that are monotone downwards, because the complement of an upward-monotone property is a downward-monotone property, and the decision tree complexity of a property and its complement is the same. However, the notion of monotonicity in the AKR conjecture is with respect to edge removal, whereas the OP's question is about monotonicity with respect to vertex removal. These define two different classes of properties.
Robin Kothari
CC BY-SA 2.5
2010-09-06T20:37:02.250Z
It might be interesting to do a new question for substructure-closed classes.
András Salamon
CC BY-SA 2.5
2010-09-05T23:01:57.880Z
2010-09-05T23:01:57.880Z
Suresh Venkat
<p>Hereditary properties are very "robust" in the following sense.</p>

<p>Noga Alon and Asaf Shapira <a href="http://people.math.gatech.edu/~asafico/heredit.pdf">showed</a> 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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-10T07:54:31.360Z
There was a nice plenary talk by Czumaj (http://www.springerlink.com/content/9rw586wx50656412/) on property testing two days ago. For yet more on the topic, there is a post by Terry Tao (http://terrytao.wordpress.com/2007/10/31/on-the-property-testing-of-hereditary-graph-and-hypergraph-properties/) or a survey by Goldreich (http://www.eccc.uni-trier.de/report/2010/082/).
RJK
CC BY-SA 2.5
2010-09-17T13:20:05.940Z
Testability is a great global property.  Thanks for the nice summary.
András Salamon
CC BY-SA 2.5
2010-09-06T02:03:49.490Z
2010-09-06T02:12:06.663Z
2010-09-06T02:12:06.663Z
arnab
<p>A hereditary class of structures (e.g. graphs) is one that is closed under induced substructures, or equivalently, is closed under vertex removal.</p>

<p>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,   <a href="http://www2.informatik.hu-berlin.de/~grohe/pub/gro10.pdf"><em>Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors</em></a>, LICS, 2010.)  These can be thought of as "global" properties.</p>

<blockquote>
  <p>Are there similar "global" properties known for hereditary classes (either graphs or more general structures)?</p>
</blockquote>

<p>It would be good to see each answer focus on just one specific property.</p>

<cc.complexity-theory><graph-theory><relational-structures>
Global properties of hereditary classes?
András Salamon
# Global properties of hereditary classes?

(Asked by: username_0 on 2010-09-05)

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*](http://www2.informatik.hu-berlin.de/~grohe/pub/gro10.pdf), 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.

**Tags:** cc.complexity-theory, graph-theory, relational-structures


---

## 6 answers

### Answer by username_6 on 2010-09-06. Score: 13 | Accepted answer

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

Noga Alon and Asaf Shapira [showed](http://people.math.gatech.edu/~asafico/heredit.pdf) 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.

> **Comments:**
> **username_2**: There was a nice plenary talk by Czumaj (http://www.springerlink.com/content/9rw586wx50656412/) on property testing two days ago. For yet more on the topic, there is a post by Terry Tao (http://terrytao.wordpress.com/2007/10/31/on-the-property-testing-of-hereditary-graph-and-hypergraph-properties/) or a survey by Goldreich (http://www.eccc.uni-trier.de/report/2010/082/).  
> **username_0**: Testability is a great global property.  Thanks for the nice summary.  

---

### Answer by username_1 on 2010-09-05. Score: 8

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

> **Comments:**
> **username_0**: These properties certainly qualify: I think the quantity you refer to is called "speed".  

---

### Answer by username_2 on 2010-10-27. Score: 8

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

A [paper by Bollob\'as and Thomason](http://dx.doi.org/10.1007/s004930070019) (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](http://www.emis.de/journals/DMJDMV/xvol-icm/13/Bollobas.MAN.html) (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.

> **Comments:**
> **username_0**: Thanks Ross.  The link you highlight between hereditary properties and the Regularity Lemma would make for some interesting questions.  

---

### Answer by username_4 on 2010-09-16. Score: 7

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.

> **Comments:**
> **username_0**: I would be very interested in reading a draft with your results.  
> **username_4**: I'll let you know when I get around to writing it up. I'm also reasonably confident that this should follow from some well-known lower bounds in this area. Unfortunately I don't know any expert in this area who I can ask.  

---

### Answer by username_3 on 2010-10-28. Score: 6

According to the [Erdős–Hajnal conjecture](http://garden.irmacs.sfu.ca/?q=op/the_erdos_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.

> **Comments:**
> **username_2**: This is potentially a very interesting example, but some excellent structural graph theorists I know believe it is false!  

---

### Answer by username_5 on 2010-09-05. Score: 4

This is the "reverse" direction, but the well known [Aanderaa-Rosenberg-Karp conjecture](http://en.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_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)).

> **Comments:**
> **username_4**: The AKR conjecture equally applies to properties that are monotone downwards, because the complement of an upward-monotone property is a downward-monotone property, and the decision tree complexity of a property and its complement is the same. However, the notion of monotonicity in the AKR conjecture is with respect to edge removal, whereas the OP's question is about monotonicity with respect to vertex removal. These define two different classes of properties.  
> **username_0**: It might be interesting to do a new question for substructure-closed classes.  

---

