18
$\begingroup$

The Robertson–Seymour theorem concerns downwardly closed classes of isomorphism classes of finite undirected graphs. (Am I committing some sin by referring to a class of classes? An isomorphism class is a proper class, and a set, as opposed to a proper class, is a class that is a member of some other class. But ignore this present comment, unless you decide not to ignore it.)

Downwardly closed means that if any (isomorphism class of a) graph is a member, then so are (the isomorphism classes of) all of its minors, a minor being defined as a graph obtained by deleting vertices (and all of their incident edges) or contracting edges (so that two vertices become one vertex with each contraction).

The theorem says that the set of minimal non-members of every such class is finite.

For example, the set of minimal non-members of the class of planar graphs has just two members: $K_5$ and $K_{3,3}.$

Other such classes include outer-planar graphs (embeddable in a plane with vertices on a circle and edges as non-crossing chords of the circle), where the forbidden minors are $K_4$ and $K_{3,2},$ and the graphs linklessly embeddable in $\mathbb R^3$, or the knotlessly embeddable graphs, or the graphs embeddable in a torus, or some other classes defined in ways not relying on geometry (I think?). With some such classes, more than just two minimal non-members are needed, but, according to the theorem, always only finitely many.

So a set of forbidden minors can always be reduced to a finite subset.

Is this equivalent to the compactness of some topological space?

(And I'm wondering if someone's going to tell me the answer is obviously "yes.")

$\endgroup$
0

1 Answer 1

26
$\begingroup$

The Robertson–Seymour graph minor theorem states that the set of all (isomorphism classes of) finite undirected graphs under the graph minor relation is a well-quasi-ordering (or wqo for short). It is a theorem that a quasi-ordering $Q$ is a wqo if and only if the Alexandrov topology on $Q$ is Noetherian, meaning that every subspace of $Q$ is compact. See for example Reverse mathematics, well-quasi-orders, and Noetherian spaces, by Emanuele Frittaion, Matt Hendtlass, Alberto Marcone, Paul Shafer, and Jeroen van der Meeren.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .