<p>It's not quite the same, but you may be interested in the 0-1 law for first order properties of graphs. A first order property is something you can describe by a logical formula with existential and universal quantifiers, in which the variables refer to vertices of a graph and there are two two-argument predicates: equality, and another predicate $\sim$ that tests whether two vertices are adjacent. For example, whether there is a universal vertex adjacent to all other vertices can be tested by the first-order formula $\exists v\forall w\,v\ne w\rightarrow v\sim w$.</p>

<p>Then, for every first-order property, the fraction of all $n$-vertex graphs that satisfy the property, as $n\to\infty$, approaches either 0 or 1. More strongly, there exists an infinite graph, <a href="https://en.wikipedia.org/wiki/Rado_graph">the Rado graph</a>, such that this fraction approaches 0 or 1 exactly when the Rado graph does not or does have the same property, respectively. But when the fraction approaches 1, it still might not be the case that the property holds for all graphs, so this differs somewhat from what you're asking.</p>

CC BY-SA 3.0
2015-08-04T19:25:41.523Z
0-1 law for first-order logic (essentially uniform AC0) is due to Fagin, "Probabilities on finite models". See also: Blass, Gurevich, and Kozen, "[A zero-one law for logic with a fixed point operator](http://www.cs.cornell.edu/~kozen/papers/bgk.pdf)".
Kaveh
CC BY-SA 3.0
2015-08-04T19:50:00.983Z
Yes, thanks, I should probably have included at least the Fagin reference in my answer, rather than burying it in the Wikipedia link.
David Eppstein
CC BY-SA 3.0
2015-08-04T17:55:54.770Z
2015-08-04T17:55:54.770Z
David Eppstein
<p>Let us say that a graph class has the <strong>jump property,</strong> if it either contains all $n$-vertex graphs for every large enough $n$, or else the fraction of $n$-vertex graphs that belong to the class approaches 0, as $n\rightarrow\infty$. </p>

<p>The answers to an earlier question (see 
<a href="https://cstheory.stackexchange.com/questions/32112/can-a-hereditary-graph-class-contain-almost-all-but-not-all-n-vertex-graphs">here</a>) show that every hereditary graph class has this jump property.</p>

<p><strong>Question:</strong> What are some other (nontrivial) examples of graph classes with this  property? </p>

<p><em>Note:</em> It would be good to see natural examples, that is, classes that arise from independent considerations, not created just for the sake of the jump property.</p>

<graph-theory>
Graph classes with a "jump property"
Andras Farago
# Graph classes with a "jump property"

(Asked by: username_0 on 2015-08-01)

Let us say that a graph class has the **jump property,** if it either contains all $n$-vertex graphs for every large enough $n$, or else the fraction of $n$-vertex graphs that belong to the class approaches 0, as $n\rightarrow\infty$.

The answers to an earlier question (see
[here](https://cstheory.stackexchange.com/questions/32112/can-a-hereditary-graph-class-contain-almost-all-but-not-all-n-vertex-graphs)) show that every hereditary graph class has this jump property.

**Question:** What are some other (nontrivial) examples of graph classes with this property?

*Note:* It would be good to see natural examples, that is, classes that arise from independent considerations, not created just for the sake of the jump property.

**Tags:** graph-theory


---

## 1 answers

### Answer by username_1 on 2015-08-04. Score: 5 | Accepted answer

It's not quite the same, but you may be interested in the 0-1 law for first order properties of graphs. A first order property is something you can describe by a logical formula with existential and universal quantifiers, in which the variables refer to vertices of a graph and there are two two-argument predicates: equality, and another predicate $\sim$ that tests whether two vertices are adjacent. For example, whether there is a universal vertex adjacent to all other vertices can be tested by the first-order formula $\exists v\forall w\,v\ne w\rightarrow v\sim w$.

Then, for every first-order property, the fraction of all $n$-vertex graphs that satisfy the property, as $n\to\infty$, approaches either 0 or 1. More strongly, there exists an infinite graph, [the Rado graph](https://en.wikipedia.org/wiki/Rado_graph), such that this fraction approaches 0 or 1 exactly when the Rado graph does not or does have the same property, respectively. But when the fraction approaches 1, it still might not be the case that the property holds for all graphs, so this differs somewhat from what you're asking.

> **Comments:**
> **username_2**: 0-1 law for first-order logic (essentially uniform AC0) is due to Fagin, "Probabilities on finite models". See also: Blass, Gurevich, and Kozen, "[A zero-one law for logic with a fixed point operator](http://www.cs.cornell.edu/~kozen/papers/bgk.pdf)".  
> **username_1**: Yes, thanks, I should probably have included at least the Fagin reference in my answer, rather than burying it in the Wikipedia link.  

---

