Graph Minor Theory, Part 4

by

< See Part 3

Before starting this post, I have to warn you that it will be getting somewhat technical. I should also say that I’m not an expert in this area. I learned much of what I’m talking about by reading Graphs on Surfaces by Bojan Mohar and Carsten Thomassen.

Last time I promised that I would try to explain the six forbidden trivalent minors for the projective plane. To start, let me present some new drawings of these minors:

Forbidden Trivalent Graphs for the Projective Plane

These are the same six graphs (drawn in the same order) as in the previous post, and the colors are designed only to highlight the structure. The drawings above are “maximally symmetric”, in the sense that you should be able to see the entire symmetry group of the graph. For example, the fifth graph consists of a 9-gon with three tripods attached, and you can see that any rotations or reflection of the 9-gon is possible by permuting the three tripods.

The Role of K_{3,3}

The key to understanding embeddings of trivalent graphs in the projective plane is to understand the role of K_{3,3}. First observe the following:

Theorem. Any trivalent graph that cannot be embedded in the projective plane contains a copy of K_{3,3}.

Proof: Observe that any planar graph embeds on the projective plane as well. Therefore, any trivalent graph that does not embed on the projective plane is not planar, and therefore contains K_{3,3}. (This was the trivalent Kuratowski theorem from part 3.)\;\square

In particular, each of the six forbidden minors drawn above contains K_{3,3} in several different ways. Indeed, the first of the forbidden minors is just a disjoint union of two copies of K_{3,3}:

The First Forbidden Minor

The fact that this graph is forbidden is roughly equivalent to the following theorem:

Embedding Theorem. Any embedding of K_{3,3} in the projective plane separates it into four discs. Indeed, there is only one embedding of K_{3,3} in the projective plane up to homeomorphism:

K{3,3} on the Projective Plane

(In the picture above, the four discs are the central hexagon, together with three squares that each cross the boundary circle.)

This theorem represents a fundamental topological property of the projective plane, a sort of analogue of the Jordan curve theorem. I’m not going to give a proof, but you ought to be able to prove it yourself if you play with it for a few minutes.

Understanding the Forbidden Minors

Let’s try to get a sense of why the other five minors are forbidden. We’ll start with the first one, which has several different copies of K_{3,3} sitting inside of it:

The Second Forbidden Minor

We have highlighted one copy of K_{3,3} in red, with the remaining three edges in blue. Watch what happens when we try to draw this graph on the projective plane:

This Graph Doesn’t Embed

By the embedding theorem, we have essentially no choice in how to draw the red edges. As you can see, there is no way to draw the blue edges that avoids crossing the red ones, and therefore this graph cannot be embedded in the projective plane.

A similar proof works for each of the forbidden minors. For example, here is a drawing of the third forbidden minor:

The Third Forbidden Minor

Again, the red edges form a copy of K_{3,3}, with the complement in blue. The blue subgraph is attached at four places to a single red edge, and the order of attachment makes it impossible to avoid crossings:

Another Failure!

Here are some drawings of the final three forbidden minors:

The Other Three Minors

Again, these were obtained by first finding a copy of K_{3,3,} inside of the minor, and then attaching the edges of the complement to a drawing of K_{3,3} in the projective plane. In each case, the way in which the blue edges are attached to the red ones forces them to cross.

Some Nitpicking

There is a slight problem with the reasoning we have been using. As I have stated, there is only one embedding of K_{3,3} in the projective plane “up to homeomorphism”. To be precise:

Embedding Theorem (Precise). Given any two embeddings i,i^\prime\colon K_{3,3} \rightarrow P^2, there exist homeomorphisms \varphi\colon K_{3,3}\rightarrow K_{3,3} and h\colon P^2\rightarrow P^2 such that i^\prime = h \circ i \circ \varphi.

The important thing is that a graph automorphism \varphi may be required for this equivalence. In particular, a labelled copy of K_{3,3} has six different embeddings, corresponding to six different automorphisms of K_{3,3}:

Six Embeddings

This is important, because these six embeddings give six different possible ways of attaching the extra edges. For example, here was the drawing presented for the last forbidden minor:

The last Forbidden Minor

Clearly the blue edges must cross in this embedding of K_{3,3}, but to show that this graph can’t be drawn on the projective plane we must consider each of the six embeddings. This turns out not to be a problem: the blue tripod must lie in the central hexagon to avoid crossings, and then the picture is exactly as shown.

Incidentally, the reason that there are six different embeddings is that there are precisely six hexagons in the graph K_{3,3}.

Further Thoughts

So far, we have shown that the six minors presented at the beginning of this post are in fact forbidden. What we have not shown is that these graphs suffice, i.e. that any trivalent graph that doesn’t embed in the projective plane contains one of these six.

The problem is, I don’t really understand why this is true. It is proven rigorously in this paper, but the details seem complicated, and I am left without a deep understanding. In addition to the obvious reasons, I have an ulterior motive for wanting to understand this subject better:

Open Problem. Find the forbidden trivalent minors for the torus.

Ideally, a good understanding of the six trivalent forbidden minors for the projective plane would shed some light on those for the torus. There is good reason to think that the two cases are similar:

Embedding Theorem. Any embedding of K_{3,3} on the torus separates the surface into three discs.

While I’m on the subject of open problems, I should mention a conjecture related to what we’ve been talking about:

Negami’s Conjecture. A graph embeds on the projective plane if and only if some finite cover of the graph embeds on sphere.

Note that embedding on the sphere is the same as embedding on the plane, so the conjecture is that a graph is projective if and only if some finite cover is planar. It’s not hard to see that “having a finite planar cover” is minor-closed, so it suffices to check that none of the forbidden minors for the projective plane has one. This has been proven for all but one of the minors (see these papers):

Theorem (Mohar and Hlineny). Negami’s conjecture holds if and only if K_{2,2,2,1} has no finite planar cover.

K_{2,2,2,1} is a (non-trivalent) forbidden minor for the projective plane. Note that K_{2,2,2} is the 1-skeleton of the octahedron, so K_{2,2,2,1} is the 1-skeleton of the cone of the octahedron.

As far as I know, no one has tried to prove Negami’s conjecture for trivalent graphs. Of the six forbidden trivalent minors, I think that the fourth is the only one that has K_{2,2,2,1} as a minor. Therefore:

Observation. Negami’s conjecture holds for trivalent graphs if and only if the following graph has no finite planar cover:

The Fourth Forbidden Minor

About these ads

10 Responses to “Graph Minor Theory, Part 4”

  1. Greg Muller Says:

    I was playing around with some graphs (for an unrelated purpose, actually), and I discovered the following disturbing graph:

    It is clearly homotopic to the second forbidden minor listed, and so can’t be embedded in the projective plane. However, it is not isomorphic to that graph (the easiest way I can see to show this is that this graph has cycles of length 5, where as that forbidden minor has only even cycles). However, it has 10 vertices, and so it can’t contain any of the other forbidden minors.

    This graph is a pretty neat one, called the Peterson graph. It came up today when I was looking at the locus of non-smooth curves in the Deligne compactification of the moduli space of the Riemann sphere with five marked points. The non-smooth locus consists entirely of Riemann spheres, and the graph is the intersection graph of those spheres.

  2. Jim Belk Says:

    The Peterson graph can be embedded in the projective plane, as the 1-skeleton of a half-dodecahedron. (It is dual to the embedding of K_6 given in my last post.)

    The Peterson graph is actually one of my favorite finite graphs. The graph is completely symmetric (i.e. the automorphism group acts transitively on the verices and edges), but the edges cannot be three-colored, meaning that it is not the Cayley graph of a finite group. (Indeed, it is the smallest vertex-transitive graph that is not a Cayley graph.)

    Incidentally, the Peterson graph can be defined as the graph whose vertices are two-element subsets of {1,2,3,4,5}, with an edge between two vertices if the subsets are disjoint. Is this related to your statement about the moduli space? For example, does each Riemann sphere somehow correspond to a choice of two of the five marked points?

  3. mnoonan Says:

    This reminds me of a question that I had a long time ago: among graphs which have Aut(G) acting transitively on vertices and edges, can we tell which ones are Cayley graphs? Is there a nice set of invariants?

  4. Greg Muller Says:

    Argh, it wont let me put pictures in the Comments. Theres a picture in the files section called ‘Peterson’ graph, which I have drawn very different from the usual way (in fact, its not completely clear it is the peterson graph, except that its symmetry group is S_5). The way I have drawn it, it is homotopic to the second forbidden minor, and so it should also be forbidden. What am I screwing up?

    Also, you are abolutely correct in how it arises as the boundary of moduli space. As you go to the boundary of the moduli space of 5 points on a Riemann sphere (thought of with the hyperbolic metric), a geodesic must shrink to length 0. There is one geodesic for each closed curve on the sphere that seperates the marked points into 2 and 3 points. Therefore, a point on the boundary corresponds to a wedge product of 2 spheres, one with 2 points and one with 3. There is a Riemann sphere’s worth of such spaces for a given partition of the 5 points. Also, it is possible but non-generic that TWO geodesic got short as you went to boundary of moduli space. This corresponds to a partition of the 5 points into 2, 2, and 1, and these points are the intersections of the Riemann spheres in the boundary.

  5. Jim Belk Says:

    First, I should say that I don’t know of a notion of “homotopy” for graphs that preserves embeddability. The graph you gave is clearly homotopy equivalent to the second minor (by sliding the two vertices along the red edges), but in the same way any graph is homotopy equivalent to a wedge of circles.

    So what happens if you attempt to perform this homotopy on the projective plane? I have two good ways of looking at this:

    1. Look above at the first two pictures of the “Understanding the Forbidden Minors” section. You’re essentially taking two of the three blue edges and sliding them along the red edges that they’re attached to, past vertices and onto adjacent red edges. There are clearly some ways of doing this that makes the blue edges embeddable.

    2. In particular, if you embed your Peterson graph in the projective plane, I think the long black edges are being attached from inside the black circle. So when you slide the attachment vertices along, they just go around the circle instead of going up the red edges.

    Does that help? It’s a little hard to communicate without drawing pictures.

  6. Maria Belk Says:

    Greg, your graph is different from the Peterson graph. For example, it has a cycle of length 4 (around the outside), but the Peterson graph does not.

    Jim’s argument above that your graph embeds on the projective plane is still valid (although I found it hard to follow — I had to ask him to explain it with pictures).

  7. Greg Muller Says:

    Argh, I was worried that the homotopy thing wasn’t an embedding invariant. It is pretty much the only logical explanation for what I was getting.

    Though, even in my sheepishness, I maintain that it is the Peterson graph (unless I drew it wrong). The outside has length 6, not 4. I just constructed an explicit isomorphism, by picking (any) cycle of length 5, sending it to the outside of the usual Peterson graph, and then seeing that the rest have to go to the star inside.

  8. mnoonan Says:

    Maybe I’m not understanding you exactly or your graph of the drawing here isn’t what you have on paper, but by picking the 5-cycle made by the top hemicircle of the left loop in your picture to be the outer pentagon, I got this graph. The central red line in your picture corresponds to the long edge connecting the outside to the inside. The other two red lines in your picture are contained in the two edges of the inside pentagon adjacent to the edge I just described. In any case: is this really the graph you meant?

    Incidentally, that graph also embeds in the projective plane.

  9. Graph Minor Theory « Abner’s Postgraduate Days Says:

    [...] Graph Minor Theory, Part IV « The Everything Seminar [...]

  10. deep blue watch Says:

    Hello, constantly i used to check website posts here early in the daylight, for the reason that i love to learn more and
    more.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 102 other followers

%d bloggers like this: