Thursday, July 23, 2009

Lesson 7: A is for Adjacent

In the previous lesson, I broke down the categories of construction which we can use to change an asteroidal triple into a strongly asteroidal triple. Today, we'll examine the category A constructions. Right now, we're only looking at S3; let's label the vertices of the asteroidal triple as a1, a2, and a3, and let b1, b2, and b3 be their respective neighbors. Then the path X1, for example, would be a2-b2-b3-a3. Each path Xi is ai-heavy; our goal is to add vertices in such a way as to make either make this path ai-light, or to create a new path that is ai-light.

The category A constructions involve adding a single vertex adjacent to the vertex ai, and possibly to additional vertices, specifically to prevent ai from being a middle vertex. There are three constructions in this category, each of which involves adding only one vertex, which we will call v.

Before we go further: when describing each construction, in this lesson and in future lessons, I will assume that vertices are being added for the explicit purpose of preventing a1 from being a middle vertex unless otherwise noted. Some constructions may affect other vertices or paths, and some constructions have special considerations when they are being used more than once; I will discuss these considerations when they come up.

Construction A1: v is a pendant vertex; in other words, the v is adjacent only to a1. This means that a1 is no longer simplicial, and thus cannot be a middle vertex. This construction can be applied to all three vertices to produce a minimal sAT; this is graph 3, shown below.


Construction A2: v is adjacent to both a1 and b1. While a1 is still simplicial, v is not adjacent to any vertex on the path X1, which makes this path a1-light. This construction can be applied to all three vertices, to produce graph 4; or, it can be applied in combination with construction A1 to produce graphs 5 and 6, shown below.

Construction A3: v is adjacent to both a1 and b1, and to one of the other interior vertices; in the example at left, v is adjacent to b3. Like construction A2, this makes the path X1 a1-light. However, the path a1-v-b3-a3 is a2-light, so this construction also prevents a2 from being a middle vertex! Thus, only one more construction is necessary to create a minimal sAT. If we attempt to combine this with construction A1, then we create a graph which contains the bad aster. However, combining it with construction A2 creates graph 7, below. Construction A3 can be applied twice, but the second added vertex must be adjacent to the same interior vertices (in the example above, b1 and b3) as v  to create a minimal sAT. The second added vertex may be adjacent to v or not. If it is not, we create graph 8; if it is adjacent to v, we create graph 9.

Other adjacencies for v do not create new constructions in this category. If v is adjacent to both b2 and b3, then we create no new light paths, so adding v would not prevent any of the asteroidal vertices from being the middle vertex. If v is adjacent to any of the other asteroidal vertices, then this would create a new light path, but the other adjacencies required (to keep our graph strongly chordal) will actually fall under category B or C. In this vein, construction A3 might be considered a category B construction; I have placed this construction in category A because it fits the definition of adding exactly one vertex, which is adjacent to exactly one asteroidal vertex, and which prevents that asteroidal vertex from being a middle vertex.

Next time, we'll get started on the category B constructions. Because each new construction can be combined (in most cases) with previous constructions, I'll probably break this category up into two or more parts. This also means fewer breaks if I want to get through this, so maybe it will have the added benefit of speeding up the lessons.

No comments: