6
$\begingroup$

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

$\endgroup$

1 Answer 1

6
+50
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Ah, thanks! I'll upvote/accept/award this as soon as I get a chance to verify the antichain for myself. Note, by the way, that the antichain given in the paper is not $B_n$ (because in fact this is a chain -- each is a subgraph of the next), but rather what it calls $A_n$; $A_n$ is $B_{n-1}$, but with the two end vertices each having two self-loops in addition. (And I'm guessing by subdividing you could probably make an antichain of simple graphs too?) $\endgroup$ Feb 12, 2013 at 5:28
  • 1
    $\begingroup$ Having checked this I can say that yes, by subdividing you can thereby also get an antichain of simple graphs. Thanks again! $\endgroup$ Feb 12, 2013 at 17:12
  • $\begingroup$ @HarryAltman Would you mind elaborating on how to obtain an antichain by subdivision? If say you take the antichain $(A_n)_n$ where $A_n:=$ the edge-repeated n-path with loops on the two ends (as Fig 2 in Excluding a Long Double Path Minor), subdivide each $A_n$ into a simple graph $A'_n$, it is not obvious why $(A'_n)_n$ remains an antichain. $\endgroup$
    – Shaopeng
    Mar 7, 2022 at 6:09
  • $\begingroup$ I just meant taking a doubled paths and subdividing them to obtain simple graphs. This is an antichain because, e.g., the number of vertices of degree 4 is different in each one, and subdivision can't change that. $\endgroup$ Mar 9, 2022 at 1:36
  • $\begingroup$ Thanks for your clarification, @HarryAltman. I still fail to see why $A_n\not\preceq A_m$ implies $A'_n\not\preceq A'_m$ for each $n<m$ though, where $A'_n$ is a subdivision of $A_n$ into simple graph. We seem to need $A_n\preceq A'_n$ and $A'_m\preceq A_m$ for the implication above to hold, but we only have $A_n\preceq A'_n$. $\endgroup$
    – Shaopeng
    Mar 11, 2022 at 0:15

You must log in to answer this question.

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