Robertson-Seymour fails for topological minor ordering? (I.e., subgraphs and subdivision)

1k Views Asked by At

The Robertson-Seymour theorem says that the set of isomorphism classes of finite graphs, with the minor ordering ($G \le H$ if $G$ is a minor of $H$) is a well partial ordering (it is well-founded and has no infinite antichains).

Wikipedia currently says that if we replace the minor ordering by the "topological minor" ordering -- that is, $G\le H$ if some subdivision of $G$ can be embedded in $H$ -- then this is no longer a well partial order.

Unfortunately it gives no citation for this so I was hoping someone could either point me to a counterexample or come up with one. (Or tell me that in fact it's wrong, or that the problem is still open, etc.)

Obviously, this order is still well-founded, so a counterexample would have to take the form of an infinite antichain. (Well, or some other way of showing that something's not a wpo.)

1

There are 1 best solutions below

7
On BEST ANSWER

I believe that an example of an infinite canonical antichain is constructed in this paper, in which it is proved that a minor closed class of graphs $\mathcal{G}$ is quasi-well-ordered by the topological minor relation if and only if some $B_n$ is not in $\mathcal{G}$, where $B_n$ is the path obtained from doubling each edge in an $(n+1)$-path.

EDIT: Here is the antichain construction:

Antichain double circles Antichain double paths