Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Robertson and Seymour tell us that any minor-closed family of graphs has a finite collection of excluded minors.

Standard examples include planar graphs with two excluded minors ($K_5$ and $K_{3,3}$) and knotlessly embeddable graphs with the Petersen family as excluded minors.

However in general, a finite list is not necessarily a short list, and there are natural properties with large numbers of excluded minors. In fact, I recall seeing examples where astronomical numbers of excluded minors have been proved to exist - unfortunately for the life of me, I can't remember these examples and I can't find them on MathSciNet.

So my question is: please give me references to results that show the existence of vast numbers of excluded minors for natural minor-closed classes of graphs.

share|improve this question
1  
The answer by Louigi Addario-Berry of mathoverflow.net/questions/46655 is relevant. –  Richard Stanley Nov 28 '11 at 3:01

3 Answers 3

up vote 3 down vote accepted

Here is another answer that I just recently learned about that I find quite shocking. A graph is called $Y \Delta Y$ reducible if it can be reduced to isolated vertices by applying any of the following six operations.

  1. Delete a loop.
  2. Delete a degree one vertex.
  3. Replace a pair of parallel edges by a single edge.
  4. Replace an induced path by a single edge.
  5. $Y \Delta$ transformation: Delete a degree 3 vertex $w$ and its three incident edges $wx, wy$ and $wz$, and add three edges $xy, yz$ and $xz$.
  6. $\Delta Y$ transformation: Delete the three edges of a triangle $\Delta:=xyz$, and add a new vertex $w$ and three new edges $wx, wy$ and $wz.$

Truemper showed that the class of $Y \Delta Y$ reducible graphs is minor-closed. Epifanov proved that all planar graphs are $Y \Delta Y$ reducible. Recently, Yu showed that there are more than 68 billion excluded minors for $Y \Delta Y$ reducibility.

Specically, Yu finds 68897913659 graphs that are excluded minors (up to isomorphism).

share|improve this answer

Here is a follow-up to Richard Stanley's comment. In his Master's thesis Hunting for torus obstructions (University of Victoria, 2002), Chambers (together with his adviser Myrvold) studied the forbidden minors (and forbidden topological minors) for embeddability on the torus.

According to this paper:

To date, Myrvold and Chambers have found 239,322 topological obstructions and 16,629 minor order obstructions that include those on up to eleven vertices, the 3-regular ones on up to 24 vertices, the disconnected ones and those with a cut-vertex. Previously, only a few thousand had been determined.

I am guessing that this was done by computer search, but I couldn't access the thesis from the UVic library.

share|improve this answer
    
That's good.. well, good in the sense of cautionary example which is what I was looking for - several hundred thousand obstructions for what seems to be a natural property. –  Gordon Royle Nov 28 '11 at 8:14
    
Yes, it was done by computer search. –  Brendan McKay Nov 28 '11 at 10:32
    
Thanks Brendan! I assume that they used NAUTY as a blackbox? –  Tony Huynh Nov 29 '11 at 10:45

Here is a cheeky answer. Let $\mathcal{C}$ be the class of graphs $G$ with $|V(G) \cup E(G)| \leq 10^{100}$. Then $\mathcal{C}$ is a minor-closed class and the excluded-minors for $\mathcal{C}$ are all non-isomorphic graphs $H$ with $|V(H) \cup E(H)|=10^{100}+1$. There are lots of these.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.