Tuesday, July 14, 2009

Lesson 5: The Journey Begins

We're ready to start our search for minimal strongly asteroidal triples. There is a fairly important result which will make the search easier. In previous lessons, I've just been stating results and either linking to the relevant citation, or referring to my dissertation, but this result actually doesn't exist in print anywhere, so I need to prove it. As a result, this section will be much more technical than the first four; if you are not a trained mathematician, you may want to take proper safety precautions, or you may just want to skip to the end, where I sum everything up.

First, we need to introduce one more concept, that of the irreducible path. A path in a graph G is a sequence of distinct vertices x1, x2, ..., xk, such that the vertex xi is adjacent to the vertex xi+1. If xi and xj are adjacent in G, and i and j differ by more than one, the path is reducible. For example, if a path has vertices x1, x2, ..., x6, and x2 is adjacent to x5, then we can skip over vertices x3 and x4, making a shorter path between x1 and x6. A path which is not reducible is irreducible. Lekkerkerker and Boland showed that the paths in a minimal AT must be irreducible. Once more, let us consider the minimal asteroidal graphs, below.

Suppose that G is a chordal, strongly asteroidal graph, and that no proper subgraph of G is strongly asteroidal (in other words, G is minimal). As was mentioned in lesson 2, the bad aster and parasol (graphs I and II) are strongly asteroidal. These are also mimimally asteroidal, so these are our first two minimal strongly asteroidal graphs. In lesson 3, I stated that k-suns are also minimal strongly asteroidal graphs. Recall that a strongly chordal graph is one which is chordal and sun-free, so, as we search for the other minimal sATs, we may assume that G is strongly chordal, not just chordal.

Let a1, a2, and a3 be a strongly asteroidal triple in G. Note that, even if G is minimal, it may contain more than one sAT. We may have to choose a specific triple in a few sentences, but, for now, let's just pick the first one we find.

Let W1, W2, and W3 be paths such that Wi is ai-light, and contains no neighbor of ai. Each of these paths contains an irreducible path, if it is not itself irreducible; let W′1, W′2, and W′3 be these irreducible paths.

Because G is minimal, it follows that
W1W2W3N(a1) ∪ N(a2) ∪ N(a3) = G

(where N(v) refers to the open neighborhood of v - the set of all vertices adjacent to v.)
If we consider W′1W′2W′3, each ai must be simplicial: if ai has two neighbors bi and ci (it will not have more, as each W′i is irreducible), then the three paths contain a cycle which contains bi−ai−ci as consecutive vertices, where bici and ai has no other neighbors. Then (because G is chordal) bi is adjacent to ci. Further, because ai is necessarily aj-light for ji, there is no need to place a vertex of Wj between ai and either bi or ci. Therefore, we may assume that each ai is simplicial in W1W2W3. Finally (and here's where we may have to pick a different triple), we may assume that each ai has at least one neighbor adjacent to vertices on Wi: if not, then let b be any neighbor of ai. Then, because ai is not adjacent to any member of Wi, b is also in a sAT with the vertices aj , ji. If b has a neighbor adjacent to a member of Wi, then replace ai with b; if it does not, then G is not minimal.

Now, let G′ be a minimal subgraph such that a1, a2, and a3 are asteroidal. In other words, remove as many vertices from G as we can while keeping those three vertices as an AT (not a sAT). Then G' is a minimal asteroidal triple - in other words, G' is one of the graphs above!

To see this, note that G′ is a subgraph of W′1W′2W′3, and that each of the vertices ai is necessarily simplicial in G′, and are the only simplicial vertices in G′. Let X1, X2, and X3 be irreducible paths of G′ such that Xi contains no neighbor of ai (while connecting the other two vertices in the triple). If G′ contains another minimal asteroidal triple, then at least one of a1, a2, or a3 is not in this triple. Because this vertex is simplicial, it would not be part of an irreducible path; thus, it can be removed to make a smaller asteroidal graph. Without loss of generality, suppose that a1 can be removed. Then G′a1 has an asteroidal triple of simplicial points (this is a result of Lekkerkerker and Boland, in the paper linked above). The only simplicial points are a2, a3, and (possibly) the neighbors of a1, so a1 has some neighbor b which is in an asteroidal triple with a2 and a3. Then b is the next vertex on one of the irreducible paths X2 or X3; without loss of generality, suppose b is on X2. Consider W2 and W3; if b is not the second vertex (after a1) of these paths, then it is adjacent to that vertex. Because b is not adjacent to every neighbor of a2 or a3, we can replace a1 with b as the first vertex of W2 and W3, and these paths will still be a2-light and a3-light, respectively. If any a2a3 path is b-light, then b, a2, and a3 are strongly asteroidal in Ga1, which contradicts the minimality of G. So, X1 must be b-heavy. Specifically, X1 must have two consecutive vertices u and v (with v closer to a2) adjacent to the next vertex on X2; call this vertex c. None of these vertices can be a3, so we may assume that u is not a neighbor of a3. Neither u nor c is adjacent to a1, so the portion of X1 from a2 to a, plus the portion of X2 from c to a3, contains no neighbor of a1. Thus, we can eliminate v, and any vertices of X1 between v and a3, and obtain a proper subgraph of G′ in which a1, a2, and a3 are still asteroidal, a contradiction. Phew!

This result implies that we can obtain the minimal strongly asteroidal graphs by simply appending vertices to the minimal asteroidal graphs in such a way as to make the asteroidal triples strongly asteroidal. We can break down our search for the strongly asteroidal graphs by looking at the minimal asteroidal graphs they contain. We'll get started on the first few cases next time.

No comments: