Summer School

I'll post new trivia in a bit, but since I do claim to talk about math here, I would be remiss not to point out a shocker in the world of mathematics: A possible proof that P ≠ NP. There's been no confirmation that the proof is correct (the paper is only two days old), but it certainly doesn't appear to be a joke.
The shock is not so much the result (I think P=NP would have been the bigger surprise), but that there was little warning that anyone was close to proving it. This has big implications for computer science. For example, data encryption that relies on factoring large numbers (a problem known to be in NP) is secure, in that there is no algorithm that will allow an adversary to quickly find the decryption key.
We do live in interesting times. Here's hoping the proof is correct.

(HT: This guy.)

Who are three people who have never been in my kitchen?

I've run into two separate discussions based on this article about Jeopardy! and baseball questions (er, answers). The relevant quote:

Let's say you're on 'Jeopardy!' and you're absolutely routing your two opponents. You have $40,000 going into the final round, while one of your opponents has, let's say, $15,000. You're guaranteed to move onto the next day, but the final category comes up and it has something to do with baseball, which is your favorite sport. How much — if anything — do you risk?

The discussions of this article go along two paths. One is to compare how many of the ten Final Jeopardy! answers everyone got right (most participants have gotten at least seven of the ten - both sites have a fair number of people who are very knowledgeable about baseball). The other is to loudly decry the article's premise that, since you should be fairly confident that you will respond correctly (the article, on the Yahoo! Sports site, assumes you're a baseball fan), you should bet your entire $40,000 haul, rather than the $10,000 that will guarantee a win. Since the Preschool is all about the math these days, let's look at this in a little more detail. Specifically, let's look at the following situation: you have $40,000, the second-place competitor has $15,000, and the Final Jeopardy! category is something squarely in your wheelhouse. How much do you bet?

This (like the Scat decisions I'm supposedly writing about) is a problem of expected value. Suppose that you estimate the probability you will respond correctly as p; for example, if p is 0.8, it means you think you're 80% likely to be correct. If you respond correctly (as you will do 100p% of the time), you gain whatever you've bet; call this number b. If you respond incorrectly (which will happen 100(1-p)% of the time), you will lose b dollars. Your expectation for this decision is then 40,000 + bp - b(1-p), which simplifies to 40,000 - b + 2bp. If your only goal is to maximize your expectation for this decision, then the answer is simple: if p is at least 0.5, you should bet everything; if it's less than 0.5, you should bet nothing.

However, this is not your only goal, because if you win the game, you get to come back tomorrow, and try to win more money. Thus, we must also factor in your expectation of future winnings. (Incidentally, the primary argument I'm seeing against betting everything is that "you're risking a lot in future winnings.") Let's assume, for the sake of argument, that the second-place competitor will bet his entire $15,000, and will respond correctly. Thus, if you bet $10,000 (or less), you will win (or tie), and come back tomorrow, regardless of your response. If you bet more than $10,000, and respond incorrectly, you will lose.

At this time, I should point out that we could make this a more complicated model, estimating the probabilities that the other competitors will respond correctly. Also, you could bet something other than $10,000 or $40,000. Even if you factor in the chance of the other competitors missing, betting something like $20,000 seems a doubly bad idea; you leave $20,000 "on the table" if you are right, and risk losing if you are wrong. You could bet slightly less than $40,000, thus improving the probability that you will win if everyone misses the final answer. In fact, I think $39,998 might be the best bet if you're "going for broke." That said, complicating the model takes time, and might be better suited to a paper than a blog post—any undergrads looking for a thesis, this might be a starting point! Once we decide to stick with a simple model, betting anything other than $40,000 or $10,000 makes the math work out less nicely, and a couple of dollars here and there isn't going to make much difference, nor will the tiny probability that you'll win with $2. Let's assume, then, that this is a binary decision: bet $10,000 and always win, or bet $40,000 and lose if you're wrong.

Assume that, if you win, your expected earnings from future shows is x (we could take some time and figure out what x might be, but let's wait to decide whether or not to deal with that). Now, we can look at two different expectations: one for playing conservatively, and one for betting everything. If you play conservatively, and bet $10,000, you will always win, thus adding x to your expectation. Using the formula above, your expectation is now 30,000 + 20,000p + x. If you bet your entire $40,000, you will lose everything, including future winnings, if you respond incorrectly. However, when you respond correctly, you double your money, and you still get to come back tomorrow. Thus, you add px to your expectation, which is now 80,000p + px.

An aside: I think this is what a lot of the folks making the "future winnings" argument miss—you aren't giving up your future winnings, just a portion of them. If you can win more today than you're likely to get on future days, there's a strong incentive to go for it.

Anyway, let's see what that incentive is. The difference between playing recklessly and playing safe is 60,000p - (30,000 + (1-p)x). Economists refer to this as an opportunity cost - by betting only $10,000, you are forfeiting whatever you could have earned by betting everything. If this cost is positive, then, economically, you are making a mistake by only betting $10,000; if it is negative, then playing it safe is the right call. Your decision is based on whether 60,000p is larger than (30,000 + (1-p)x).

Let's look at an example: Suppose you think you're 80% likely to get the Final Jeopardy! question correct. You are then comparing 48,000 to 30,000 + .2x. If x is less than 90,000, then 48,000 will be larger. In other words, you should bet everything unless you think you'll make at least $90,000 from future shows; given that $50,000 is a pretty hefty one-day total, this would require a fair amount of confidence on your part!

Does this mean Jeopardy! players should be wagering more recklessly? Well, perhaps. The example above is pretty solidly in favor of betting it all, but the big issue is estimating that probabilty. I managed to get 8 of the ten questions posed in the linked article (nine, actually, but I had to think about one for more than 30 seconds, so I'd have been hosed in Final Jeopardy), but that doesn't mean I'd be 80% confident I could answer a question based only the fact that it would be about baseball. Also, the necessary value for x in order to play conservatively goes down very quickly; if p = 0.7, then you're comparing $42,000 to 30,000 + .3x, and x only needs to be $40,000 to break even; considering that you've got $40,000 right now, this is getting to the realm of possibility. If we knew x (and we can probably come up with a statistical value, given the probability that the previous day's champion wins again, and the mean winning total), we could come up with a "break-even" value for p. I might return to this, but for now, I think the risk-averse behavior is better, unless you are very very sure of yourself.

Another Post Just To Prove I Still Post

The latest post on Scat strategy has been half-finished for over a week, as I have been working on presentations of old and new research. Also, I'm still trying to find a new trivia night; I may give up soon and just start posting my own stuff. For now, here's a fun definition:

Let A_k be the set {1, 2, ..., k}. A graph G has an optimal t-tone coloring if each vertex can be assigned a t-element subset of A_k in such a way that if vertices u and v are distance d apart (in other words, the shortest path in G connecting these vertices contains d edges), then their subsets have at most d-1 elements in common.

For example, vertices adjacent to each other can have no shared elements in their subsets, while if the distance between two vertices is greater than t, they may be assigned identical subsets.

Sometimes, a pendant vertex is just a pendant vertex.

I had a dream last night, in which I saw the proof of a mathematical theorem. It involved copies of K₅, with pendant vertices arranged in such a way that all of the graphs linked perfectly together into a larger complete graph. It was a simple, beautiful proof, and I can still see the end of it now, hours later. A few of the details are fuzzy, but I'm sure I could work them out. There's only one problem.

I have absolutely no idea what it was I was proving.

Probabilistic Filler

Some important probabilities related to Scat:

As I mentioned last time, your chance of getting scat (no 1's) on your first roll is 3125/7776, or (5/6)⁵, which is just over 40% of the time. The probability, then, of having scat as your final hand is (5/6)¹⁵, or 6.5%, which works out to about twice every 31 turns.

The probability of rolling five 1's within three rolls is, in theory, about 1.3% (the exact probability simplifies to (91/216)⁵, which I think is kind of neat—not because that ratio has any significance, but because the otherwise-complicated calculation ends up simplifying so neatly), or about once every 75 turns. In practice, though, this probability is smaller, because of situations which dictate abandoning the all-1's strategy.

If there are k people still left to roll, then, the chance that at least one person gets scat is 1 - (1 - (5/6)¹⁵)^k; and the maximum probability that at least one person rolls all 1's is 1 - (1 - (91/216)⁵)^k. If, for example, four players were still to roll after you, there would be a 23.5% chance that at least one would roll scat (thus saving you from elimination, if you had a fairly low roll), and as much as a 5% chance that someone would end the game prematurely by rolling five 1's.

The main factor we must consider when deciding which dice to re-roll is the expectation of each decision; this expectation is specifically based on the probability of winning or losing the game after this decision. The probabilities above are part of calculating the expectation - you can make riskier moves (i.e., keeping only your 1's) when there are more players still to roll, because there is a higher chance that someone after you will get a bad hand, and because there is a higher chance that if you don't win right now, someone else will do so before you get another roll. I'll get more into the decision-making process next time.

Roll the dice, don't think twice

I'm a little behind on everything these days, and Scat strategy is one of them. Go back a month to review the rules.

When it is your turn, you have two strategies available:

1. Attempt to roll five 1's, thus winning the game.
2. Obtain a hand which is not likely to be the low hand for the round, thus avoiding elimination.

After your first roll, you have two opportunities to decide which dice to keep, and which dice to re-roll. This decision is a choice among three options:

1. Keep only the 1's, and re-roll all of the other dice.
2. Keep the 1's and your highest-ranking die or dice.
3. Keep the best hand you can make with the current dice.

For example, if your roll is 1-3-3-4-6, you can keep only the 1 (option 1), the 1 and the 6 (option 2), or the 1 and both 3's (option 3). There is no reason, ever, to keep the 4, or to not keep the 1.

In many cases, the decision is not even as complicated as the previous example; if the roll had been 1-3-4-6-6, or 1-3-4-5-6, options 2 and 3 would be the same. In fact, a little over 40% of the time (3126/7776, to be exact), there is only no decision to make - either you roll no 1's (3125 times), and must re-roll all five dice, or you roll five 1's (1 time), and win the game.

For those times when there is a decision to make, several additional factors should be considered:

• The current low hand. The low hand in each round is eliminated, so you will often (not always) choose the option with the best chance to beat the current low. More importantly, you will want to avoid options that have a very low probability of beating the low hand (keeping three 2's when the current low hand is four 4's, for example, is usually a bad plan).
• The number of players still to roll. Remember, you only need to beat one player each round, so if there are several players still to roll, you can choose a riskier option, based on the chance that not all of those players will beat you.
• The number of players still in the game. Without taking strategy into account, if there are n players at the beginning of the next round, your chance of winning by avoiding elimination this round is roughly 1/n.

I'll start getting into the probabilities of the game next time (and I hope that next time comes more quickly than this time did). However, I expect we'll find that, early in the game, the expectation gained by winning the game immediately will outweigh the risks of being eliminated early. In other words, rolling five 1's is the primary strategy (in my limited experience, most players make avoiding the low hand primary, and rarely go for the outright win unless they have already beaten the current low). This means that option 1 will frequently be the correct decision, because the other two options necessarily abandon the primary strategy. This will be particularly true after the first roll, because committing to any die other than a 1 restricts the ways for a hand to improve. I also expect that avoiding the low hand will become the primary strategy later in the game, when simply staying alive represents a greater increase in the probability of winning—my guess is that this happens when there are three players remaining, but we'll see.

Finally, and perhaps unfortunately, I expect we'll find that, while skillful play does increase one's expectation of winning, the overall effect won't be that great against people who do not play as well. In other words, you'll be able to win an n-player game against "normal" players more often than once every n games, but you'll likely need to play a few hundred games to see that result. Also, since each player's hand is independent of the other hands, we may find that there is a single pure strategy that maximizes one's probability of winning. In this case, the result of all players adopting that strategy makes the probability of winning an n-player game exactly 1/n. This is all conjecture for another time, though. Stay tuned.

Why does it happen? Because it happens.

When I lived in Michigan, a friend of mine hosted Monday Night Football parties. I expect he still hosts them, I just don't live there anymore. Anyway, a bunch of guys would show up, and we'd spend the evening drinking beer and sort-of watching the game. Since we usually only had a passing interest in the game, we would turn quickly to other distractions, usually games. It was at these parties that I was introduced to a dice game my friends called "Scat." Scat is a variation of poker dice. The rules are as follows:

• The goal for each player is to make the best "hand" (actually, it's to avoid making the worst hand, but I'll get to that in a second). A hand is the best possible set of any one rank. Sets are ranked first by cardinality (the size of the set) and then by ordinality (the rank of the dice in the set); for example, three sixes is better than three fours, but four twos is better than three sixes. Only the set itself counts, the "kickers" are irrelevant, e.g. four twos and a six is the same as four twos and a three). Ones are wild, so a one and two sixes is really three sixes. However, a hand must have a one to be valid; a hand with no ones is "scat," and is worth nothing.
• Each player has three rolls to make a hand. After each of the first two rolls, the player may choose to stop rolling any or all of the dice. However, the player must roll a one before setting aside any dice, i.e., if the player has scat, he must re-roll all five dice. If a die is set aside after the first roll, it may not be re-rolled after the second roll.
• Play passes clockwise around the table. After each player has rolled, the lowest hand is eliminated, and the remaining players begin a new round. The honor of starting each round passes counter-clockwise: the last player to roll in the previous round rolls first in this round, the first player in the previous round now rolls second, and so on. When only two players are left, the game becomes best-of-three (the first player to have the low roll twice loses).
• If, at any time, a player's dice "stack" (i.e., one die lands on top of another), that player is immediately eliminated, and the round ends.
• If, at any time, a player rolls five ones, that player wins the game, regardless of how many players are remaining.

Obviously, this is largely a game of chance, so its main purpose was to shift small sums of money around a table. However, I noticed the occasional opportunity for skillful play. For example, a player who rolled two ones, two threes, and a six would usually keep the threes, thus keeping four threes instead of three sixes. However, if the low roll was four fours, that player would need to roll a one or three on the fifth die to avoid elimination. A player who kept the six in the same situation would still need to roll a one or six, but would have two dice, thus improving his odds.

This round of math lessons will focus on this game. I'll first point out some basic probabilities related to the game, and then delve a little into strategies in specific situations. Finally, I'll look at the game theory aspects, in an attempt to come up with a basic strategy.

Lesson 12: Why Bigger Isn't Better

In the final post on strongly asteroidal graphs, we look at asteroidal graphs other than S₃; namely, graphs III_n (for n > 2) and IV_n (for n > 1). Fortunately, changing these graphs into minimal strongly asteroidal graphs is not nearly as complicated as it was for S₃, for two reasons. The first, and most important, is that there is only one potential middle vertex (a₁) in the asteroidal triple, so only one construction need be applied. The second reason is that applying the category B constructions (and, by extension, category C constructions) fails to produce a light path. Here's why:

Suppose that X₁ has three consecutive a₁-heavy vertices x-y-z, with a₁-light vertices u between x and y, and v between y and z. If x and z are not adjacent, then this creates a copy of graph II (with u, v, and a₁ as the strongly asteroidal triple). If, on the other hand, we attempt to place a single a₁-light vertex adjacent to x, y, and z, then this creates a chordless cycle with a₁. Therefore, category B constructions are minimal only if X₁ contains just two consecutive a1-heavy vertices, so we need not apply them when n > 2. Further, applying any category B construction to graph IV₂ will create a k-sun, where k is 3, 4, or 5, depending on the adjacencies between the a₁-light vertices and the neighbors of a₁.

This means we only need to focus on the category A constructions. Applying construction A1 to any of these graphs creates a copy of graph I, except in the case of graph IV₂, in which case we get graph 9. Applying construction A3 to any of these graphs results in a copy of graph II. Only construction A2 creates new minimal graphs. For the graphs in family IV_n, the added vertex must be adjacent to both neighbors of a₁; if it is only adjacent to one of the neighbors, a copy of graph II is created. This gives us two families of minimal strongly asteroidal graphs; these are 55_n and 56_n below.

There is one final construction to consider for graph IV_n; adding a pendant vertex v somewhere along the path X₁ might create a new sAT, in which a1 becomes part of a v-light path between a₂ and a₃. This construction can only work for n > 2, because v cannot be adjacent to a neighbor of a₂ or a₃. However, for n > 3, this construction will create a copy of graph II. The construction does work for graph IV₃, but the graph it creates is graph 43. We are out of ways to modify the minimal asteroidal graphs, so we conclude that we have, at long last, found all of the minimal strongly asteroidal graphs.

We have also, at long last, concluded this topic. The math talk will continue, though. Next up is some probability theory, as I examine a dice game.

Lesson 11: From C To Shining C

Welcome to the penultimate post on strongly asteroidal graphs. We've seen category A constructions, in which a neighbor is added to one of the asteroidal vertices of S₃, and category B constructions, which modify the path between two asteroidal vertices. Today, we will look at category C constructions, which do both.

In a category C construction, a vertex c₁ is added which is adjacent to a₁, b₁, b₂ and b₃, and a category B construction is added to the path X₁. In addition, edges are added between b₁ and every vertex in the category B construction. The modified category B construction still creates an a₁-light path, because there will not be consecutive vertices adjacent to c₁. Equivalently, this can be thought of as adding a regular category B construction, and then making c₁ adjacent to every vertex except a₂ and a₃. However, it is more convenient, in terms of adding later constructions, to modify the category B construction so that all of the vertices are adjacent to b₁. Each category B construction has a corresponding category C construction, so the category C constructions can intuitively be labeled C1-C4. The constructions are in the figure below.

Because c₁ is adjacent to b₂ and b₃, removing b₁ from construction Cn will make a graph isomorphic to one with construction Bn applied. Therefore, in order to create a new minimal sAT, it is necessary for b₁ to be part of another light path.

In construction C1, this means that a category B or C construction must be applied to either a₂ or a₃, but in constructions C2 and C4, b₁ is already part of at least one light path, which includes one vertex from the category B construction (it is difficult to see, but these paths are colored red and blue in the diagram).

Construction C1 does not combine with construction A3 (a parasol is created), but we do get new minimal sATs by applying construction B1 or B2 to the path X₂, and applying constructions A1, A2, or B1 to a₃ (or X₃); these are graphs 37-41. In addition, construction C1 can be combined with constructions B1 and B3 to create graph 42; construction B4 can be used instead of B3 to create graph 44, which we'll get to in a second. In the above figure, note that several of these graphs have been rotated/reflected.

Applying C1 a second time can lead to several new graphs. If the vertices c₁ and c₂ are not adjacent to each other, then the vertices v₁ and v₂ become unnecessary. If c₁ and c₂ are adjacent, but v₁ and c₂ are not, then v₂ is still unnecessary. Finally, we can allow c₁ to be adjacent to c₂ and v₂, and c₂ to be additionally adjacent to v₁.

Adding construction B1 or B2 to any of these combinations, or B3 to either of the latter two combinations, will create a new minimal strongly asteroidal graph. Graphs 43-45 are those that occur using construction B2, graphs 46-48 use B2, and graphs 49 and 50 use B3. The category A constructions and construction B4 do not lead to new minimal graphs.

Finally, there is one way to apply construction C1 to all three asteroidal vertices. The vertices c₁, c₂, and c₃ are adjacent to each other, and only one additional vertex v is necessary; it is adjacent to b₁, b₂, and b₃. This creates graph 51. Other modifications of the adjacencies between c₁, c₂, c₃, and v₁, v₂, and v₃ do not create new minimal graphs; the most common result is a 3-sun.

Only a few minimal graphs arise from the other category C constructions. Construction C2 actually is a minimal sAT by itself, as the adjacencies between b₁ and the B2 portion of the construction create a₂- and a₃-light paths. This is graph 52. Construction C3 does not lead to any new minimal graphs; because the only added vertex in construction B3 is already adjacent to b₁, the addition of vertex c₁ is unnecessary to create an a₁-light path. Finally, construction C4, like construction C2, contains an a₂-light path. Category B constructions that modify the path X₃ do not combine with this, for the same reason they do not combine with construction B4. However, constructions A1 and A2 can be applied to a₃ to make graphs 53 and 54.

These are the final minimal sATs that arise from the graph S₃. Next time, we'll finish up by looking at the infinite families of asteroidal graphs, and seeing how to modify those to create strongly asteroidal graphs.

Lesson 10: All This Has Happened B4

It has been two months since I posted lesson 9. There are a few reasons for the delay, but one reason is that the final category B construction has been a thorn in my side for months. I originally thought that it gave rise to no new minimal graphs. Then, I found one new sAT, then two, then three, then went back down to two, and so on. Every time I thought that I had thoroughly examined the construction, another combination occurred to me. Over the last month, I have examined each combination of constructions that included B4, one by one, and have officially convinced myself whether each combination does or does not produce a new minimal sAT.

Construction B4: The vertex v₁ is adjacent to a₂. In addition, a vertex u₁ is added, which is adjacent to v₁ and b₃. This creates the a₁-light path a₂-v₁-u₁-b₃-a₃.

The great difficulty in construction B4 lies in the fact that it lacks symmetry. With the previous category B constructions, adding a construction to a₂ was no different than adding it to a₃. For example, two combinations produce graph 16. With B4, this is no longer the case; when we apply other constructions, it is important whether they are applied to a₂ or a₃. In addition, if we apply B4 a second time, it matters which of the asteroidal vertices is adjacent to the vertex v₂.

One important thing to note is that applying this construction, and then removing the vertex b₂, is equivalent to just applying construction B1. To create a minimal sAT, the other two constructions must be applied in such a way that either b₂ is part of every a₃-light path, or that every a₂-light path would be heavy if b₂ were removed. This means that the construction applied to a₂ cannot be a category A construction, or construction B3. In addition, applying construction B1 or B2 to the path X₃ creates either a graph in which b₂ can be removed, or one with a chordless cycle. Applying construction A3 to either a₂ or a₃ creates a copy of the parasol.

If we apply a category B construction to the path X₂, the added vertices must be adjacent to v₁, in order to avoid suns and parasols. Construction B1 will create new minimal graphs when constructions A1, A2, or B3 are applied to a3; these are graphs 33-35 below. Construction B2 results in a graph in which u₁ is removable; in fact, it creates a category C construction, which we'll get to next time.

Attempting to apply B4 a second time creates problems. If it is applied to the path X₂, we must decide whether the vertex v₂ is adajcent to a₁ or a₃. If it is adjacent to a₁, then we do not get a minimal sAT, as (depending on the adjacencies) the resulting graph will contain suns, chordless cycles, or a category C construction. Suppose, then, that v₂ is adjacent to a₃. Then applying a category A construction to a₃, or construction B3 to the path X₃ is no longer possible (for the same reasons they could not be applied to a₂ or X₂ earlier). However, allowing v₁ to be adjacent to u₂ and v₂, and v₂ to additionally be adjacent to u₁, creates the a₃-light path a₁-b₁-u₂-v₁-a₂, while also preventing the removal of b₂ or b₃. This is, therefore, a minimal sAT; this is graph 36 at left.

Applying construction B4 to path X3 does not create new strongly asteroidal graphs; in any strongly chordal graph where this is applied, either a1 or b2 will be removable.

Next time, I'll start on the category C constructions. It's all downhill from here, kids. Two more posts max, and then we can move to a new topic.

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 v₁.

Construction B3: v₁ is adjacent to both a₂ and a₃, thus creating the path a₂-v₁-a₃, which is a₁-light. Combining this construction with previous constructions is tricky. Adding constructions A1 or A2 to both a₂ and a₃ creates a copy of the bad aster. However, if we modify these constructions by making the added vertices adjacent to v₁ as well, this creates a minimal graph (if a₂ uses the modified construction, but a₃ does not, then b₂ could be removed to make a smaller strongly asteroidal graph). Similarly, adding construction B1 to both X₂ and X₃ creates a sun, unless we modify the construction by making the added vertices adjacent to v₁. 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 a₁ 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 u₂, V₂, and W₂ are added to create the path a₁-b₁-u₂-v₂-w₂-b₃-a₃, then there is a parasol, unless v₂ and/or w₂ is adjacent to v₁. If only w₂ is adjacent to v₁, a chordless cycle is created, and if only v₂ is adjacent to v₁, a₁ and b₁ can be removed to make a smaller strongly asteroidal graph, regardless of the construction added to a₃ (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 a₁ and b₁ leaves a graph equivalent to combining B3 with B1 (with u₂ and v₁ standing in for a₁ and b₁). So, u₂, v₂, and w₂ must all be adjacent to v₁. Then, either a modified or unmodified type A construction can be added to a₃, producing graphs 27-30.

If construction B3 is applied twice, with vertex v₂ adjacent to a₁ and a₃ (as well as each vertex b_i), then v₁ and v₂ must be adjacent to avoid chordless cycles. Adding construction A1 or A2 to a₃ will produce a copy of graph 9, so we must add a type B construction to X₃ 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 v₁ and v₂. 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.

Lesson 8: B2, or not-B2

Welcome to the latest installment in the continuing struggle to find minimal strongly asteroidal graphs. We are creating these graphs by adding vertices to the minimal asteroidal graphs, as discussed in lesson 5. Specifically, we're adding these vertices to the graph S₃; see lesson 7 for the terminology I use in referring to the various vertices in that graph. Last time, we looked at category A constructions, which add a neighbor to the vertex a_i, in order to prevent it from being a middle vertex. In today's lesson, we'll start to look at the category B constructions, which involve adding vertices to the path X_i to make it a_i-light. The number of vertices we can add is limited somewhat; I'll spare the details, but an a_i-light path in a minimal sAT will have a maximum of three a_i-heavy vertices. This is a small result, but it is important, because it a) means that there are only a small number of constructions in this category, and b) it places an upper bound on the length of the a_i-light paths, which in turn places an upper bound on the order of the minimal graphs we can get by adding vertices to S₃, which means the number of sporadic cases is finite. Before we begin, recall that, when a construction of category B (or C) is applied, the added vertices can be adjacent to the added vertices from other constructions from category B or C. This adds a level of complexity not found in the category A constructions.

Construction B1: a single vertex u₁ is added, adjacent to b₂ and b₃. This creates an a₁-light path, and thus prevents a₁ from being a middle vertex. If this construction is applied twice, say by adding a vertex u₂ to prevent a₂ from being the middle vertex, then the new vertices cannot be adjacent: this would create a chordless cycle u₁−u₂−b₁−b₂−u₁, and adding a chord between b_i and u_i (where i is 1 or 2) would make u_i a_i-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 a_i-light paths. The other constructions of type B involve adding only one such vertex; we will call this vertex v₁.

Construction B2: In addition to v₁, vertices u₁and w₁ are added, such that u₁ is adjacent only to b₂ and v₁, and w₁ is adjacent only to b₃ and v₁. Then a₂−b₂−u₁−v₁−w₁−b₃−a₃ is a₁-light. This construction can be applied once, in combination with constructions A1 and A2, to produce graphs 15-17. Combining B2 with A3, by adding a neighbor to a₂, does not produce a minimal graph: this combination will have a copy of the parasol, unless the vertex added to a₂ is adjacent to v₁. But, in this case, a₁, a₂, and w₁ are in a strongly asteroidal triple, so a₃ can be removed to make a smaller strongly asteroidal graph (it is, in fact, graph 35, which we will see later). Combining B2 and B1 (by adding u₂ to the path X₂) also fails to make a minimal graph; adding any of the previous constructions to a₃ or X₃ will produce a graph in which a₂ (at least) can be removed to make a smaller strongly asteroidal graph. Applying B2 a second time creates an irregular construction. If vertices u₂, v₂, and w₂ are added to create the path a₁−b₁−u₂−v₂−w₂−b₃−a₃, then there is a 3-sun unless v₁ and v₂ are adjacent. Adding construction B1 to X₃ will produce a sun. Adding a construction of type A to a₃ creates a copy of either graph 13 or 14 (in which u₁, u₂, and a₃ are a strongly asteroidal triple), unless u₂ is adjacent to v₁ and/or u₁ is adjacent to v₂; we may assume the former. In this case, though, v₂ and w₂ (and the construction added to a₃) can be removed to make a smaller strongly asteroidal graph. Specifically, this is graph 18, in which, for 1 ≤ i ≤ 3, there is a vertex u_i adjacent only to b_i and v₁. Each u_i is a_j-light for j ≠ i, and so for each i, there is an a_i-light path between the other two asteroidal vertices. Applying B2 a third time creates a graph which contains either a sun, or a copy of graph 18, so this does not give us an additional minimal graph.

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.

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 S₃; let's label the vertices of the asteroidal triple as a₁, a₂, and a₃, and let b₁, b₂, and b₃ be their respective neighbors. Then the path X₁, for example, would be a₂-b₂-b₃-a₃. Each path X_i is a_i-heavy; our goal is to add vertices in such a way as to make either make this path a_i-light, or to create a new path that is a_i-light.

The category A constructions involve adding a single vertex adjacent to the vertex a_i, and possibly to additional vertices, specifically to prevent a_i 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 a₁ 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 a₁. This means that a₁ 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 a₁ and b₁. While a₁ is still simplicial, v is not adjacent to any vertex on the path X₁, which makes this path a₁-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 a₁ and b₁, and to one of the other interior vertices; in the example at left, v is adjacent to b₃. Like construction A2, this makes the path X₁ a₁-light. However, the path a₁-v-b₃-a₃ is a₂-light, so this construction also prevents a₂ 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, b₁ and b₃) 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 b₂ and b₃, 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.

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)
3. The bad aster
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 a₁, a₂, and a₃ be our asteroidal triple, and X₁, X₂, and X₃ the paths connecting them, as described previously.

The only graphs we need concern ourselves with are graphs from the III_n and IV_n families, where n > 1 (graph IV₁, recall, is the 3-sun). We will begin with graph III₂, which is S₃. 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 a_i from being a middle vertex. I have grouped these constructions into three categories:

• Category A constructions involve adding a vertex adjacent to a_i. This vertex may or may not be adjacent to any neighbors of a_i. In fact, adding a pendant vertex to a_i is the easiest way to prevent a_i from being a middle vertex, because it is no longer simplicial.
• Category B constructions modify the a_i-heavy path X_i by adding a_i-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 a_i which is adjacent to the a_i-heavy vertices on X_i, and then adding vertices to X_i 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.

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 x₁, x₂, ..., x_k, such that the vertex x_i is adjacent to the vertex x_i+1. If x_i and x_j are adjacent in G, and i and j differ by more than one, the path is reducible. For example, if a path has vertices x₁, x₂, ..., x₆, and x₂ is adjacent to x₅, then we can skip over vertices x₃ and x₄, making a shorter path between x₁ and x₆. 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 a₁, a₂, and a₃ 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 W₁, W₂, and W₃ be paths such that W_i is a_i-light, and contains no neighbor of a_i. Each of these paths contains an irreducible path, if it is not itself irreducible; let W′₁, W′₂, and W′₃ be these irreducible paths.

Because G is minimal, it follows that
W₁ ∪W₂ ∪W₃ ∪ N(a₁) ∪ N(a₂) ∪ N(a₃) = G

(where N(v) refers to the open neighborhood of v - the set of all vertices adjacent to v.)
If we consider W′₁ ∪ W′₂ ∪ W′₃, each a_i must be simplicial: if a_i has two neighbors b_i and c_i (it will not have more, as each W′_i is irreducible), then the three paths contain a cycle which contains b_i−a_i−c_i as consecutive vertices, where b_i ≠ c_i and a_i has no other neighbors. Then (because G is chordal) b_i is adjacent to c_i. Further, because a_i is necessarily a_j-light for j ≠ i, there is no need to place a vertex of W_j between a_i and either b_i or c_i. Therefore, we may assume that each a_i is simplicial in W₁ ∪ W₂ ∪ W₃. Finally (and here's where we may have to pick a different triple), we may assume that each a_i has at least one neighbor adjacent to vertices on W_i: if not, then let b be any neighbor of a_i. Then, because a_i is not adjacent to any member of W_i, b is also in a sAT with the vertices a_j , j ≠ i. If b has a neighbor adjacent to a member of W_i, then replace a_i with b; if it does not, then G is not minimal.

Now, let G′ be a minimal subgraph such that a₁, a₂, and a₃ 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′₁ ∪ W′₂ ∪ W′₃, and that each of the vertices a_i is necessarily simplicial in G′, and are the only simplicial vertices in G′. Let X₁, X₂, and X₃ be irreducible paths of G′ such that X_i contains no neighbor of a_i (while connecting the other two vertices in the triple). If G′ contains another minimal asteroidal triple, then at least one of a₁, a₂, or a₃ 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 a₁ can be removed. Then G′−a₁ 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 a₂, a₃, and (possibly) the neighbors of a₁, so a₁ has some neighbor b which is in an asteroidal triple with a₂ and a₃. Then b is the next vertex on one of the irreducible paths X₂ or X₃; without loss of generality, suppose b is on X₂. Consider W₂ and W₃; if b is not the second vertex (after a₁) of these paths, then it is adjacent to that vertex. Because b is not adjacent to every neighbor of a₂ or a₃, we can replace a₁ with b as the first vertex of W₂ and W₃, and these paths will still be a₂-light and a₃-light, respectively. If any a₂−a₃ path is b-light, then b, a₂, and a₃ are strongly asteroidal in G−a₁, which contradicts the minimality of G. So, X₁ must be b-heavy. Specifically, X₁ must have two consecutive vertices u and v (with v closer to a₂) adjacent to the next vertex on X₂; call this vertex c. None of these vertices can be a₃, so we may assume that u is not a neighbor of a₃. Neither u nor c is adjacent to a₁, so the portion of X₁ from a₂ to a, plus the portion of X₂ from c to a₃, contains no neighbor of a₁. Thus, we can eliminate v, and any vertices of X₁ between v and a₃, and obtain a proper subgraph of G′ in which a₁, a₂, and a₃ 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.

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, a_x and b_x, such that vertices x and y are adjacent if and only if a_x ≤ b_y and a_y ≤ b_x. If, for vertex x, a_x ≤ b_x, then x is known as a bounded vertex; if a_x ≥ b_x, 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.

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 S₃ (again) and S₄.

As was mentioned yesterday, S₃ contains a sAT. So does S₄, 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.

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 K_1,3. The graph on the right, the 3-sun, is denoted S₃; the middle graph is its complement, denoted S₃.

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 T₂. 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 III₂, is S₃. In family IV, the entire path on the "bottom" may just have one vertex, so the smallest member of this family, graph IV₁, 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 III_n and IV_n 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.

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