## Tuesday, July 28, 2009

### Sarek Knows Best

This week's trivia misses themes: science fiction and Oscars trivia!

1. According to starwars.com, how old was Jabba the Hutt?

2. What year did the original Star Trek first premiere on television?

3. What actress played Spock's mother on both the Star Trek television series and in the fourth film?

4. What science fiction novel, now one of the top-selling sci-fi novels of all time, won the 1985 Nebula Award for best novel?

5. What song, from The Poseidon Adventure, won the 1972 Academy Award for Best Original Song?

6. What Best Picture-winning comedy also earned Billy Wilder Academy Awards for directing and writing?

## Monday, July 27, 2009

### Lesson 9: Construction B3

We're still looking for minimal strongly asteroidal graphs, and it's time to move on to the next category B construction. Recall (from last time) that this construction will involve adding a vertex which is adjacent to all three interior vertices; we will call this vertex v1.

Construction B3: v1 is adjacent to both a2 and a3, thus creating the path a2-v1-a3, which is a1-light. Combining this construction with previous constructions is tricky. Adding constructions A1 or A2 to both a2 and a3 creates a copy of the bad aster. However, if we modify these constructions by making the added vertices adjacent to v1 as well, this creates a minimal graph (if a2 uses the modified construction, but a3 does not, then b2 could be removed to make a smaller strongly asteroidal graph). Similarly, adding construction B1 to both X2 and X3 creates a sun, unless we modify the construction by making the added vertices adjacent to v1. This modification does not work for construction A3, however, as it creates a copy of the parasol.

If we combine constructions of type A with construction B1, we must still use the modified construction of B1; otherwise, we will create a graph in which a1 can be removed to make a smaller strongly asteroidal graph. We may, however, use modified or unmodified type A constructions. Graphs 19-21 use only type A constructions with construction B3, and graphs 22-26 use construction B1 at least once.

Construction B3 can also be combined with construction B2. If vertices u2, V2, and W2 are added to create the path a1-b1-u2-v2-w2-b3-a3, then there is a parasol, unless v2 and/or w2 is adjacent to v1. If only w2 is adjacent to v1, a chordless cycle is created, and if only v2 is adjacent to v1, a1 and b1 can be removed to make a smaller strongly asteroidal graph, regardless of the construction added to a3 (which must be a type A construction, because B2 does not combine with B1, and applying B2 twice will produce a copy of graph 18). If both are adjacent, then removing a1 and b1 leaves a graph equivalent to combining B3 with B1 (with u2 and v1 standing in for a1 and b1). So, u2, v2, and w2 must all be adjacent to v1. Then, either a modified or unmodified type A construction can be added to a3, producing graphs 27-30.

If construction B3 is applied twice, with vertex v2 adjacent to a1 and a3 (as well as each vertex bi), then v1 and v2 must be adjacent to avoid chordless cycles. Adding construction A1 or A2 to a3 will produce a copy of graph 9, so we must add a type B construction to X3 to obtain a minimal graph. Applying B3 a third time will result in a 3-sun, but both B1 and B2 will work, as long as all of the added vertices are adjacent to both v1 and v2. Construction B1 produces graph 31, and construction B2 produces graph 32.

Next time, we face the horror that is construction B4. For those who couldn't give a rip about all of this graph theory, there will be trivia posted tonight or tomorrow.

## Friday, July 24, 2009

### Lesson 8: B2, or not-B2

Construction B1: a single vertex u1 is added, adjacent to b2 and b3. This creates an a1-light path, and thus prevents a1 from being a middle vertex. If this construction is applied twice, say by adding a vertex u2 to prevent a2 from being the middle vertex, then the new vertices cannot be adjacent: this would create a chordless cycle u1u2b1b2u1, and adding a chord between bi and ui (where i is 1 or 2) would make ui ai-heavy, defeating the purpose of the construction. Then B1 cannot be applied to all three paths, as this will create a 3-sun. It may be applied up to twice, though, in combination with constructions A1 or A2, to produce graphs 10-14. Applying constructions A3 and B1 together produces a copy of the parasol, so this is not minimal.

Starting with construction B2, the remaining constructions all involve adding one or more vertices which are adjacent to all three interior vertices, and to other vertices (possibly one or more of the asteroidal vertices) to create ai-light paths. The other constructions of type B involve adding only one such vertex; we will call this vertex v1.

That wasn't so bad, was it? Things get tougher, though, with construction B3, and I may need to spend the weekend re-checking my notes before I'm ready to show you B4.

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

## Friday, July 17, 2009

### He only dreamed of places now and of the lions on the beach.

As I continue to catch up on our trivia misses, this week's theme is Famous Characters in Literature (and other media). The Lone Ranger's nephew's horse is still not a question.

1. Which family did Hazel work for?
2. Who is the superhero alter ego of Steve Rogers?
3. What is the name of Andy Capp's wife?
4. What is the name of Oscar Madison's wife?
5. What well-known novel features a character named Aarfy Aardvark?
6. Who is Tom Sawyer's girlfriend?
7. In The Old Man and the Sea, what is the old man's name?

## Thursday, July 16, 2009

### Lesson 6: There is NO lesson 6

We now know a few of the minimal forbidden subgraphs for the co-TT class of graphs:

1. Chordless cycles (co-TT graphs are chordal)
2. k-suns (co-TT graphs are, in fact, strongly chordal)
4. The parasol

Last time, we learned that we can find the minimal strongly asteroidal graphs by modifying the minimal asteroidal graphs to create light paths. Let a1, a2, and a3 be our asteroidal triple, and X1, X2, and X3 the paths connecting them, as described previously.

The only graphs we need concern ourselves with are graphs from the IIIn and IVn families, where n > 1 (graph IV1, recall, is the 3-sun). We will begin with graph III2, which is S3. This graph is unique, because of its rotational symmetry; any of the three asteroidal vertices could be a middle vertex (the rest of the graphs which we have to consider have only one middle vertex, and only one heavy path). This means we must create light paths for each of these vertices. There are several constructions that we can use to prevent an asteroidal vertex ai from being a middle vertex. I have grouped these constructions into three categories:

• Category A constructions involve adding a vertex adjacent to ai. This vertex may or may not be adjacent to any neighbors of ai. In fact, adding a pendant vertex to ai is the easiest way to prevent ai from being a middle vertex, because it is no longer simplicial.
• Category B constructions modify the ai-heavy path Xi by adding ai-light vertices. When category B constructions are added to more than one of the asteroidal vertices, we also gain the option of adding edges between the newly added vertices. This has to be done carefully; many graphs produced by these constructions are not strongly chordal.
• Category C constructions combine the other two constructions, adding a new neighbor to ai which is adjacent to the ai-heavy vertices on Xi, and then adding vertices to Xi which are not (all) adjacent to this new neighbor. These are the most difficult constructions to find, but in at least one case, applying this construction to one asteroidal vertex prevents the entire triple from having a middle vertex.

We'll start with the category A constructions next time. They are fairly simple, so we should be able to get through all of them in one go. This will not be the case for the other two categories.

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

## Monday, July 13, 2009

### Lesson 4: Stuck In the Middle

In lesson 2, I pointed out that, while two of Lekkerkerker and Boland's minimal asteroidal graphs also contain sATs, the two infinite families (except for the 3-sun) do not. This is because the lower path contains consecutive vertices adjacent to the neighbor(s) of the "top" vertex (and this is the only path between the "left" and "right" vertices not passing through these neighbors).

In their original paper, Monma, Reed, and Trotter showed that a graph is a co-TT graph if and only if each vertex x can be assigned two real numbers, ax and bx, such that vertices x and y are adjacent if and only if axby and aybx. If, for vertex x, axbx, then x is known as a bounded vertex; if axbx, then x is unbounded. A graph which contains only bounded vertices is equivalent to an interval graph (Jamison, "Cross Comparison Graphs," no citation currently exists), so the unbounded vertices are the key to the difference between interval graphs and co-TT graphs.

At left is a graph with the a and b values assigned to each vertex. The "top" vertex is the only unbounded vertex in this assignment, though any or all of the pendant vertices could be made unbounded.

If a graph does not contain an AT, it is an interval graph, so we are most interested in what happens with asteroidal triples. For a vertex v in an AT to be given an unbounded assignment, it must satisfy the requirement that every path between the other two vertices in the AT that does not contain a neighbor of v must be v-heavy. A vertex is v-heavy if it is adjacent to every neighbor of v; a path is v-heavy if it contains two consecutive heavy vertices. A vertex or path which is not v-heavy is v-light.

A vertex in an AT which satisfies these two properties is a middle vertex. In families III and IV, the "top" vertex is a middle vertex; to obtain sATs, we must add vertices to these graphs to create a light path between the other two asteroidal vertices. How do we do that? Stay tuned.

## Friday, July 10, 2009

### Like Lazarus (which, by the way, was a question last week)

We've found a new place for trivia, so the weekly "trivia misses" post is back!
The new format is old-style pub quiz: rounds of ten questions each, so we've got a bunch of misses saved up. I'll dole them out slowly, just in case we miss a week. There's also a round or two of "celebrity photos," in which one must identify the celebrity face, which the quizmaster has cut from a magazine and pasted onto a cartoon body. These, sadly, do not translate well to the Internets, or we'd have a lot more questions. Here, anyway, are some of our recent misses. This week's theme: animal names. Everyone's favorite animal name question was not asked.

1. On Bonanza, what was the name of Ben Cartwright's horse?
2. What is the name of the Yale Bulldog? (as in, the dog himself has a name, what is it)
3. What was the name of the goldfish in the Disney version of Pinocchio?
4. Who is Porky Pig's girlfriend?
5. What was the name of the cross-eyed lion on Daktari?

## Thursday, July 9, 2009

### Lesson 3: Here Comes The Sun

I've mentioned chordal graphs a few times already. Today, we'll look at strongly chordal graphs. If a graph has a cycle with k vertices in it (where k > 3), and we label the vertices 1, 2, ..., k, consecutively (so 1 is adjacent to 2 and to k), then if vertices i and j are adjacent, and i and j differ by more than one (and aren't 1 and k), then the edge between i and j is a chord. If the difference between i and j is odd (even), then this edge is an odd (even) chord. A strongly chordal graph is a graph in which every cycle of at least four vertices has a chord (which makes it chordal), and every cycle of at least six vertices has an odd chord.

Strongly chordal graphs are equivalently defined as graphs which have a strong elimination ordering (the definition begins at the bottom of page 76 in the linked text). Farber defined the strong elimination ordering in a 1983 paper, and also showed that strongly chordal graphs are precisely the graphs which are chordal and sun-free. A k-sun is an even cycle, with at 2k vertices (k > 2), in which the vertices can be numbered such that the even vertices have no additional edges (beyond the two you'd expect), and the odd vertices form a clique. If the odd vertices form a chordal graph, but not a complete graph, then the cycle is an incomplete sun. Some graph theorists prefer to call the latter graph a sun, and the former a complete sun. Every incomplete sun contains a k-sun, so the difference is semantic. Below are S3 (again) and S4.

As was mentioned yesterday, S3 contains a sAT. So does S4, and, in fact, every sun. This is not a surprise; Monma, Reed, and Trotter showed in their original paper that co-TT graphs are strongly chordal (by finding a strong elimination ordering). In my dissertation, I showed that the k-suns are minimal forbidden subgraphs; removing any vertex from a k-sun results in a co-TT graph. If we label the vertices of a k-sun as described above, any three of the even vertices form a sAT; simply moving along the cycle from one vertex to the next gives a light path, as opposed to a heavy path, which I mentioned yesterday, and will talk about tomorrow.

## Wednesday, July 8, 2009

### Lesson 2: More Triples Than Johnny Damon

Yesterday, I introduced (again) the strongly asteroidal triple, and began laying the groundwork for the search for minimal strongly asteroidal graphs. First, though, I should mention where the term "strongly asteroidal" comes from. The sAT is related to two weaker conditions:

Given three distinct vertices a, b, and c in a graph, if there are paths between each pair of vertices which contain no neighbor of the third, then a, b, and c are an asteroidal triple (AT). If the paths between each pair of vertices do not contain two consecutive neighbors of the third, then a, b, and c are a astral triple. Every strongly asteroidal triple is also asteroidal, and every asteroidal triple is also astral. The astral and asteroidal triples are known in graph theory for being forbidden subgraphs of other graph classes. Interval graphs were shown by Lekkerkerker and Boland to be precisely the graphs which are chordal and AT-free (in other words, containing no asteroidal triple). Jackowski showed that unit interval graphs (interval graphs in which each interval is the same length) are precisely the graphs which are astral triple-free.

The three graphs to the left are the minimal chordal graphs containing an astral triple (each cycle of length at least 4 also contains astral triples). The graph on the far left is known as the claw, and is also denoted K1,3. The graph on the right, the 3-sun, is denoted S3; the middle graph is its complement, denoted S3.

These four graphs are the minimal chordal graphs containing an asteroidal triple. The first graph, which one of my advisors refers to as the "bad aster," is sometimes denoted T2. The second graph has no name that I know of; I occasionally refer to it as the "parasol" (the "umbrella" is something else), or simply as Graph II. The remaining two graphs represent infinite families; the dashed line represents a path with as many vertices as desired (even 0, in which case the vertices on either end are the same vertex), all of which are adjacent to the neighbor(s) of the "top" vertex. The smallest member of family III, graph III2, is S3. In family IV, the entire path on the "bottom" may just have one vertex, so the smallest member of this family, graph IV1, is the 3-sun.

A quick check of these graphs reveals that the asteroidal triples in the bad aster and the parasol are also strongly asteroidal, as is the 3-sun. However, for n ≥ 2, graphs IIIn and IVn do not contain a sAT, as every path between the "right" and "left" asteroidal vertices either passes through a neighbor of the "top" vertex, or contains consecutive vertices adjacent to all of those neighbors (I refer to such a path as heavy). More on heavy paths and middle vertices later; tomorrow, I'll talk about suns and strongly chordal graphs.

## Tuesday, July 7, 2009

### Deep Impact

So, on to the promised new content. I'll put up some trivia this week, too, but for now, I'm beginning a little lecture on graph theory. For those unfamiliar with the topic, one can find some basic definitions on Wikipedia, or Mathworld, or in this nice little primer.
In my final post of 2008, I defined a strongly asteroidal graph as one which contains three distinct vertices a, b, and c, such that there is a path between each pair of these vertices which
1. contains no neighbor of the third vertex, and which
2. does not contain two consecutive vertices adjacent to every neighbor of the third vertex.
The vertices a, b, and c are then referred to as a strongly asteroidal triple. This will often be referred to as a sAT in the later posts on this topic.

All very well and good, but why am I telling you this? In my dissertation, I showed that the class of graphs known as co-TT graphs (which are the complements of threshold tolerance graphs, defined in this paper) are precisely the graphs which are chordal and sAT-free. This is a major step towards finding the minimal forbidden subgraphs for this class. It is, therefore, of some interest to find the minimal graphs (a graph minimally satisfies a condition if the removal of any vertex leaves a graph which no longer satisfies that condition) which are both chordal and contain a sAT. There are three infinite families of minimal (chordal) strongly asteroidal graphs, plus at least 54 sporadic cases. Finding these cases is tedious, and does not lend itself well towards publishing in a journal. I want this work out there, though, so that there is actually a record of what the minimal forbidden subgraphs for this class are. So, for the next few weeks, I'll be working through the minimal strongly asteroidal graphs. There will be pictures, there will be words, there may be mistakes (which is one reason I hope people start following this). If you stick with me, you might learn something, or you might teach me something, or you might be really bored.

A rough outline of where we're going:
1. Intro (that's this post)
2. Astral and asteroidal triples
3. Suns and strongly chordal graphs
4. Constructing strongly asteroidal graphs from asteroidal graphs
a. Type A constructions
b. Type B constructions
c. Type C constructions

## Wednesday, July 1, 2009

### Like School In Summer

I hope everyone is enjoying their Summer Break. Here at the Preschool, we're undergoing the long-threatened redesign, which involves more than just a layout change. There will still be trivia (I've been saving some up), but I've got something planned for after Independence Day weekend. If you're not a mathematician, you probably won't find the first series interesting. Or maybe you will; it's graph theory, which means there might be pictures. Happy weekend!