1
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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, 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.

$\endgroup$
  • 2
    $\begingroup$ 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". $\endgroup$ – Kaveh Aug 4 '15 at 19:25
  • $\begingroup$ Yes, thanks, I should probably have included at least the Fagin reference in my answer, rather than burying it in the Wikipedia link. $\endgroup$ – David Eppstein Aug 4 '15 at 19:50

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.