co.combinatorics - Generalizations of Planar Graphs

A well ordering, $leq$, on a set $S$ is a WELL-QUASI-ORDERING if and only if every sequence $x_iin S$ there exists some $i$ and $j$ natural numbers with $i < j$ with $x_ileq x_j$. (See wikipedia article at bottom)

Robertson-Seymour Theorem: The set $S=Graphs/isomorphism$ are well-quasi-ordered under contraction.

The corollary of this theorem is that any property $P$ of graphs which is closed under the relation of contraction (meaning if $P(G_2)$ and $G_1leq G_2$ then $P(G_1)$) is characterized by a finite set of excluded minors (Which is explained below). An example of such a $P$ is planarity, or linkless embeddability of a graph into R^3. i.e. Every contraction of a planar graph is planar.

Suppose $P$ is a property closed under $leq$.

***If $Bleq G$ and $B$ is not $P(B)$, Then not $P(G)$.

The idea is to characterize $P$ by a collection of bad $B$'s. The finiteness of the set of excluded minors comes from the well-quasi ordering and doesn't use the idea of a graph:
Assuming we have well-quasi-ordered set $(S,leq)$. One can prove that every property $P$ which is closed under the relation is characterized by a Finite set of excluded minors.That is, there exists some $X=lbrace x_1,ldots,x_nrbrace subset S $ such that for all $sin S$, $$ mbox{ not } P(s) iff exists i, x_i leq s $$.

The existence of a finite set $X$ is implicitly in 12.5 of Diestel (link at bottom, see the corollary of Graph Minor Theorem in Diestel). First convince yourself that there exists a set of $B's$ (not necessarily finite) as in * that characterize property $P$. Then consider the smallest such set of $B$'s and using the property of well-quasi ordering show that is is finite. Note that as in the second wikipedia article, we can say any set of elements $Asubset S$ such that for all $a,bin A$ we have $a nleq b$ must be a finite set (provided $leq$ is a well-quasi-ordering).

Actual work done showing stuff in a topological direction has be done by Eran Nevo http://www.math.cornell.edu/~eranevo/

I suspect that Matroids have a well-quasi-ordering and that there is work being done toward proving an analogous theorem for them.

I have a limit on links:

en.wikipedia.org/wiki/Well-quasi-ordering

en.wikipedia.org/wiki/Robertson-Seymour_theorem

diestel-graph-theory.com/GrTh.html