Monday, December 14, 2009

A son! A son! A son! Hear the joyful celebrations in the street!

The trivia posts have been slowing down lately. The caller has moved to a new location, but hasn't set up trivia night yet, so this may have to hold you until 2010. Don't despair, though, I remain steadfast in my search for good trivia.

  1. What early-'80s rock diva was originally classically trained as an opera singer?
  2. Speaking of rock, and opera, what is Tommy's last name?
  3. In the novel Treasure Island, what is the name of Long John Silver's parrot?
  4. Who was the Girl from U.N.C.L.E.? (the character's name, not the actress)
  5. What was the name of Carrie's high school (in the film)?
  6. What is the only Van Gogh painting sold during the artist's lifetime?
  7. Which NFL team won its first game of the season 17 years in a row, from 1973-1985?

Thursday, December 10, 2009

Hit your marks, Stay in the light, and do the same thing every time, for continuity

WARNING: Minor Glee spoilers ahead. If you haven't seen this week's episode, consider coming back tomorrow.

When we last saw the gang at McKinley High, it was Wednesday, and Will had just stepped down as director. Sectionals are Saturday, and Saturday, just to remind you, is December 19.

We start with Emma taking over the glee club, and Mercedes showing us she ain't no Kelly Rowland. This might happen Wednesday, or it might be the next day, but that doesn't matter, because the team puts together its set list with just a few days to go, and then we jump to Saturday, and everyone's on the bus! Well, everyone except Mr. Schu, because he can't go, and Finn, because he's quit, and is busy cleaning out his locker, because football season has ended. Football season has ended? Really? The State Finals are Thanksgiving Weekend, and, as I have pointed out several times, McKinley wasn't making the playoffs. Football season has been over for this bunch for six weeks.

Anyway, we're over at Sectionals, and Frances McDormand and Lauren Hutton are rocking out to Jane Adams Academy and Haverhurst (no, seriously, watch it again, they're sitting right in front of the McKinley kids), and the set list has been compromised! That's okay, though, because Finn un-quits again (he's as good at this as Rachel), and the kids put together a song, complete with harmony and choreography, in one hour. This, I will point out, bothered the w quite a bit, but not me. I said this in a comment a while back, but a show like this is all about where you choose to suspend your disbelief. I'm okay with it being High School Musical, and everyone already knows the lyrics to every song and just starts dancing. What I'm not okay with is poor continuity.

And speaking of which, here comes Rachel and her amazing disappearing/reappearing band-aid (it's on her right knee... in about half of the first number)! Lea Michele is fantastic, but I gotta say, she has never looked less like a high school sophomore than in this number. Then we have the one-hour song, and we're off to judging. It's amusing and all, but then the Vice Comptroller mentions that she's only there because her boss got tickets to a NASCAR event at the last minute. And this is where I choose not to suspend my disbelief. It is December. Even if we give the show a couple of weeks of credit by just ignoring things like the football team's record (which gave us our first clue as to an actual date), it's the end of November at the earliest. Here is this year's NASCAR schedule. There isn't a NASCAR event in December. There isn't one remotely close to Ohio in November. On top of that, races are on SUNDAY! I know it's a throwaway line, it's just meant to be funny, but come on, people!

Anyway, the show ends, Emma resigns, her last day is Monday, and on Monday Sue is suspended and the kids sing Will a song and everyone is there despite the fact that it is December 21, and almost every public high school in the country let out for the year on the 18th. Maybe there was a snow day (and the snow completely melted away the next day, because the trees outside are still green), and now they have to make it up.

Anyway, that's what you missed on Glee. Join us in April for the Spring Semester. It had better be the Spring Semester.

Thursday, December 3, 2009

Deep Blue Something, or possibly not.

We're a bit behind on trivia because of the holidays, too. We've only been going about every other week, as the popularity at this particular watering hole has slowed down; it's just not that much fun if there are only four teams, even if we do win more often. The trivia caller is, apparently, moving his gig to a new restaurant, so we'll see if that picks things up.

1. What occurred the day before the Passion of the Christ?

2. Which comedian famously stopped aging at 39?

3. Who was the last American man to win the Olympic marathon?

4. More Olympics: who was the only American to win a gold medal during the '68 Winter Games?

5. Who played Hazel?

6. Who sang the score for the film Breakfast at Tiffany's?

This show has 74 flaws as of yesterday...

WARNING: Minor Glee spoilers ahead. If you haven't seen this week's episode yet, you may want to come back tomorrow.

We missed last week's Glee recap because of the holiday, so it's time to pack two episodes into one post. This will work out well, because we absolutely must assume most of these episodes take place in parallel, as we're about to see.

Last week, we met the competition for Sectionals. We don't really know when Will met with their respective choirmasters, but we do know that the rehearsal with the School for the Deaf took place on Monday. That's not the same Monday as the previous episode, so it has to be the next Monday, December 14.

This week, we find out that Sectionals are "a week from Saturday." If it's already after the Monday from last week, that means Sectionals are on St. Stephen's Day, which doesn't seem likely. Therefore, this has to have happened the previous week. That's all very well and good, but the episode still has to end later than last week's episode, because Will is no longer the Glee Club director. It is, at the earliest, December 16 - the "Imagine" rehearsal is Monday, Will sleeps in the office on Tuesday (we need the day on Tuesday to resolve other subplots), Mattressgate hits on Wednesday. Sectionals are now set in stone as December 19, there is no further way around it.

And that's what you missed on Glee. Next week we finally see Sectionals, and figure out how Emma is there and at her wedding at the same time, and perhaps resolve once and for all the fake baby plotline.

Saturday, November 21, 2009

There's no beating Judy's ham!

There's not much to say about this week's Glee. It's hard to stay with a timeline, as I can't find any point in this week's episode that specifically references an occurrence in the previous week's episode. There is a temporal clue, though, as we know that Finn is invited to the Fabrays' house for Sunday dinner. This does, of course, lead to more time-continuity issues, as Rachel appears to run into Susie Pepper in a restroom at school, immediately after dinner. That could be Monday morning, but then Rachel is wearing a different outfit before rehearsing with Mr. Schuester. Is that Tuesday?

Let's be generous, and assume that some of this week's episode happened in parallel with the previous episode's events. This seems unlikely, given that the gang would be spending a lot of time in wheelchairs, but if we don't start crediting the show a week here and there, we're going to hit Holiday Break in a hurry, and Sectionals (which are now "in a few weeks," by the way) will be happening around Valentine's Day. (This, as I alluded to last week, would actually be more in line with the schedule of show choir events in Ohio, but that's a whole other kettle of home-cured meat.) Sunday dinner is still going to happen after last week, but I'll assume that the final Schu-Rachel scene does take place on Monday (perhaps Rachel was slushied after lunch and had to change). That gives us a current date of December 7. Last day of school is the 18th, people, so sectionals better get here fast.

Sunday, November 15, 2009

Back then, of course, if the fight lasted less than fifty rounds, we demanded our nickel back!

It's been a while since I put up trivia, and I've been stocking up on misses. Unfortunately, I've misplaced most of that stock, but here are a couple of the tougher ones from the last few weeks. Get these, and you too could be taking your local pub for a bottle of wine and a gift certificate every week.

  1. According to Mattel, what is Barbie's last name?
  2. Who is the only Major League Baseball player to hit a home run for both leagues in the All-Star Game? (Not in the same game, obviously)
  3. What African dog breed is also known as "The Barkless Dog?"
  4. What comedian introduced Johnny Carson as the new host of The Tonight Show on October 1, 1962?
  5. What fruit forms the base for the liqueur creme de cassis?
  6. Who was the only boxer to defeat John L. Sullivan by knockout?

Thursday, November 12, 2009

It's beginning to look a lot like...

WARNING: Minor Glee spoliers ahead. If you haven't watched this week's episode, you may want to come back tomorrow. Also, there's a spot where I link to a blog post that links back here, so you could get caught in a Recursive Internet Loop if you're not careful.

Previously on Glee: The football team won its first game with three weeks left in the season, and then continued to practice for six more weeks. Meanwhile, Mr. Schuester announced that we were two weeks away from Sectionals, then led his merry band of singing, dancing teens through three weeks of mash-ups and throwdowns, all in preparation for the aforementioned Sectionals, which still haven't happened as of November 19.

They won't happen this week, either, as we find out that the team can't afford to rent the short bus to travel to Sectionals. There's cupcakes, and fighting, and more Artie than we're used to, which is a good thing, and more Brittany than we're used to, which is probably also a good thing. The plots all advance a little, but the main point of this episode is to showcase the Rachel-Kurt "Defying Gravity" performance, which is quite spectacular. Everyone feels good, everyone's happy, and there's no mention of fake pregnancy or any of the uncomfortable adult relationships or why anyone ever mentioned that Sectionals were in two weeks when most Ohio show choir competitions won't take place before next semester anyway.

So, what's the date? As usual, the show gives us one temporal clue, as Schu tells everyone to "be ready on Thursday" for the diva-off. We can assume, as usual, that all of the subplots and outfit changes take place over as short a time frame as possible, given the previous episode. The Thursday after November 19 would be the 26th, but that happens to be Thanksgiving. Thus, it has to be the following Thursday, December 3. We will note that the Cheerios have begun to practice indoors, so there is some attempt to keep the show in a universe in which Ohio actually gets cold in autumn and winter.

This week, it occurred to me that maybe the show wasn't totally serialized, and thus it could be earlier. After all, most of the subplots, particularly the various teen interactions, could easily have run in parallel. Kurt could join the football team and come out to his dad, and the whole Kristen Chenoweth thing could have been the week before, and that could still have been in a later episode, because they don't really have anything to do with each other. But every single episode has a moment, often just a few lines, that mark it as happening after the previous episode. This week, it's Quinn being kicked out of Cheerios. I get the need to tell the story as one continuous arc — it's easier for the viewer to keep track of everyone's relationships if we don't have to worry about whether today's events happened before or after the stuff we saw last week — but you have to account for the fact that time always moves forward. You can't just have everyone be a junior again for the second season.

Obviously, I'm more into the date-continuity issues of this show than most folks, but what really bothers me about them is how easy they would have been to avoid. If you don't say that the football team is 0-6, you can still claim it's early September. "Sectionals are in two weeks" was part of a throwaway line meant to show us that the kids weren't focusing, but details like that are exactly the sort of thing writers need to pay attention to. If you say "two weeks," you've committed yourself to a date, and that's a problem four episodes down the road, when you've had a month's worth of subplot, and still four more episodes until the actual competition.

And that's what you missed on Glee. Join us next week, as we'll find out whether women throw themselves at Will in spite of his v-neck cardigan/skinny tie ensembles, or because of them.

Tuesday, November 10, 2009

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.

Wednesday, November 4, 2009

Lesson 12: Why Bigger Isn't Better

In the final post on strongly asteroidal graphs, we look at asteroidal graphs other than S3; namely, graphs IIIn (for n > 2) and IVn (for n > 1). Fortunately, changing these graphs into minimal strongly asteroidal graphs is not nearly as complicated as it was for S3, for two reasons. The first, and most important, is that there is only one potential middle vertex (a1) 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 X1 has three consecutive a1-heavy vertices x-y-z, with a1-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 a1 as the strongly asteroidal triple). If, on the other hand, we attempt to place a single a1-light vertex adjacent to x, y, and z, then this creates a chordless cycle with a1. Therefore, category B constructions are minimal only if X1 contains just two consecutive a1-heavy vertices, so we need not apply them when n > 2. Further, applying any category B construction to graph IV2 will create a k-sun, where k is 3, 4, or 5, depending on the adjacencies between the a1-light vertices and the neighbors of a1.

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 IV2, 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 IVn, the added vertex must be adjacent to both neighbors of a1; 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 55n and 56n below.

There is one final construction to consider for graph IVn; adding a pendant vertex v somewhere along the path X1 might create a new sAT, in which a1 becomes part of a v-light path between a2 and a3. This construction can only work for n > 2, because v cannot be adjacent to a neighbor of a2 or a3. However, for n > 3, this construction will create a copy of graph II. The construction does work for graph IV3, 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.

Wednesday, October 28, 2009

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 S3, 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 c1 is added which is adjacent to a1, b1, b2 and b3, and a category B construction is added to the path X1. In addition, edges are added between b1 and every vertex in the category B construction. The modified category B construction still creates an a1-light path, because there will not be consecutive vertices adjacent to c1. Equivalently, this can be thought of as adding a regular category B construction, and then making c1 adjacent to every vertex except a2 and a3. 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 b1. 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 c1 is adjacent to b2 and b3, removing b1 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 b1 to be part of another light path.

In construction C1, this means that a category B or C construction must be applied to either a2 or a3, but in constructions C2 and C4, b1 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 X2, and applying constructions A1, A2, or B1 to a3 (or X3); 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 c1 and c2 are not adjacent to each other, then the vertices v1 and v2 become unnecessary. If c1 and c2 are adjacent, but v1 and c2 are not, then v2 is still unnecessary. Finally, we can allow c1 to be adjacent to c2 and v2, and c2 to be additionally adjacent to v1.

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 c1, c2, and c3 are adjacent to each other, and only one additional vertex v is necessary; it is adjacent to b1, b2, and b3. This creates graph 51. Other modifications of the adjacencies between c1, c2, c3, and v1, v2, and v3 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 b1 and the B2 portion of the construction create a2- and a3-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 b1, the addition of vertex c1 is unnecessary to create an a1-light path. Finally, construction C4, like construction C2, contains an a2-light path. Category B constructions that modify the path X3 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 a3 to make graphs 53 and 54.

These are the final minimal sATs that arise from the graph S3. 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.

Wednesday, October 21, 2009

Zoot Suit Riotous

WARNING: Minor Glee spoliers ahead. If you haven't watched this week's episode, you may want to come back tomorrow.

It's rehearsal time at McKinley, and we acknowledge the fact that we've had Sue as co-director for a week, but now that's over, and we're back on track for Sectionals. Apparently, Sectionals have been postponed, because they should have been this past weekend. Remember that, writers? When you said that Sectionals were "in two weeks," and then you packed two weeks' worth of "show" time into the next two episodes?

That doesn't matter, though, because now there's trouble brewing at football practice. Coach Tanaka has his knickers in a twist, and has declared that the team must practice this Thursday, when the glee club normally rehearses. The issue of why the team is still practicing at all, given that the football season ended three weeks ago, is not brought up. Remember that, writers? When you said the football team was 0-6, and then ran through two months without showing any more football? High school teams don't play into December. We will note that the students are beginning to wear cold-weather clothing.

Anyway, back to the stated premise of these posts. Let's assume that the original rehearsal is on the Monday following last week's episode (so, November 16). The Thursday practice happens. Let's further assume that the Rachel-Puck scene occurs at the end of that particular practice (even though that means Rachel changed outfits post-rehearsal), which will allow Finn to return to glee club on Friday. This packs a heck of a lot of subplot into one week, but as usual, we are generous here at the Preschool. The date is Friday, November 20. We've missed Halloween, and are getting ready for Thanksgiving break.

And that's what you've missed on Glee. It sounds like there will be a few weeks without new episodes, which might allow real time to catch up with show time. Sectionals, no doubt, will be postponed without explanation again. See you in a month.

Thursday, October 15, 2009

Eight Days a Week?

WARNING: Minor Glee spoilers ahead. If you haven't seen this week's episode, you may want to stop reading now. Of course, if you have normal human eyeballs, it's probably already too late. Sorry.

So... was "Keep Holding On" the sectionals song?

As you'll recall, last week's episode began with sectionals two weeks away, and ended a week (plus a few days) later. So, presumably, sectionals will be the next weekend.

This week, we begin with Sue and Schu fighting like Mom and Dad on payday, and then there's a flashback. A lot happens: Sue splits up the Glee Club, there's practices for a singing competition, Will flunks all the Cheerios (except for Quinn and Santana and Brittany, apparently), we find out that Puck is one of the Chosen People (shalom!), there's a big fight in Principal Figgins' office.

We could try to figure out dates for all of these. For example, assuming the previous episode ended on Thursday, the original meeting with Figgins has to be, at the very earliest, Monday - surely, he's not trying to "take the temperature" after a single practice? Fortunately, trying to figure out how all of these events shoehorn into a few days is totally unnecessary, thanks (as usual) to the B-plot - Terri's increasingly absurd fake pregnancy. Without going into any additional commentary on the ideas, writing, and character development surrounding this donnybrook, I'll just point out that the ultrasound appointment takes place (per Will) on Friday, just after the big shouting match with Sue. Assuming everything else did take place in the course of a single week (and, since there is no mention of sectionals, we have to assume that), we have a date for these events - it's Friday, November 13.

And this is where the show (finally) begins to lose date continuity. Will comes into Sue's office, and they apologize, and talk about the set list. We still haven't seen sectionals, so this scene takes place... when? Saturday morning? The sectionals were, per previous exposition, scheduled for this particular weekend. The gang sings us out, but it's unclear if this is the competition, or a practice, or a daydream. So, Will and Sue either make up Saturday, before sectionals, or Monday after sectionals which we didn't see (given the competition, plausible), or sectionals got postponed and no one told us, or most of the McKinley students and faculty own time-turners.

And that's what you missed on Glee. Tune in next week for football three weeks after the end of football season, and perhaps Halloween decorations just in time for Thanksgiving.

Tuesday, October 13, 2009

I also make a better door than a window

A while back, our regular trivia host took sick, and was missing for two weeks. One of the regulars got in touch with him, picked up the clues, and read them in his stead. In an effort to help out, I offered to write and read a round of trivia, and was allowed to do so the second week. I came up with ten questions that I thought were great. Unfortunately, it turns out I'm a better trivia-taker than trivia writer; the winning group in my round got one (1) question right, and they were the only ones to get that right. To be sure, I did a poor job. Hard questions are fine, but they're for separating the wheat from the chaff; you have to throw a couple of softballs out to keep people playing. Surely, though, you can do better than one.

  1. Name the Pep Boys.
  2. In Calvin and Hobbes, what is Calvin's favorite bedtime story?
  3. Who was the 23rd President of the United States, serving between Grover Cleveland's non-consecutive terms?
  4. What dog won the first three Frisbee World Championships, which are now named after him?
  5. In the Velvet Underground song, "Waiting for the Man," how much money is in the singer's hand?
  6. How many Canadian provinces border at least one Great Lake?
  7. Who was the first African-American woman awarded the Nobel Prize in Literature?
  8. On which island did Napoleon die, on May 5, 1821?
  9. What is the name of the theme music for The Daily Show?
  10. What Dutch driver holds the Indy 500 records for fastest practice lap, qualifying lap, four-lap qualifying time, and 200-lap race?

Monday, October 12, 2009

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 v1 is adjacent to a2. In addition, a vertex u1 is added, which is adjacent to v1 and b3. This creates the a1-light path a2-v1-u1-b3-a3.

The great difficulty in construction B4 lies in the fact that it lacks symmetry. With the previous category B constructions, adding a construction to a2 was no different than adding it to a3. 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 a2 or a3. In addition, if we apply B4 a second time, it matters which of the asteroidal vertices is adjacent to the vertex v2.

One important thing to note is that applying this construction, and then removing the vertex b2, 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 b2 is part of every a3-light path, or that every a2-light path would be heavy if b2 were removed. This means that the construction applied to a2 cannot be a category A construction, or construction B3. In addition, applying construction B1 or B2 to the path X3 creates either a graph in which b2 can be removed, or one with a chordless cycle. Applying construction A3 to either a2 or a3 creates a copy of the parasol.

If we apply a category B construction to the path X2, the added vertices must be adjacent to v1, 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 u1 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 X2, we must decide whether the vertex v2 is adajcent to a1 or a3. If it is adjacent to a1, 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 v2 is adjacent to a3. Then applying a category A construction to a3, or construction B3 to the path X3 is no longer possible (for the same reasons they could not be applied to a2 or X2 earlier). However, allowing v1 to be adjacent to u2 and v2, and v2 to additionally be adjacent to u1, creates the a3-light path a1-b1-u2-v1-a2, while also preventing the removal of b2 or b3. 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.

Thursday, October 8, 2009

What Time Is It, Mr. Fox?

If you're like me, you spend your Wednesdays from 9-10 p.m. watching Glee (if you're not like me, you still watch it, but you have a DVR, so you watch it later and without commercials). I love the singing, love the one-liners, and I'd watch Jane Lynch read "Sinners in the Hands of an Angry God," because I think she'd read it in a sardonic tone that would just crack me up the whole time. The relationships (all of them) are AWK-ward, but I prefer to view that as intentional, like it's a whole school of Michael Scotts. One thing has been bothering me, though. A couple weeks ago, I made the following comment over at ALOTT5MA:

I'm having trouble with the tiimeline for this show. If there's enough time passing that it's noticeable that Mr. Shuster only shows up for rehearsal once a week, where are we in the semester?

(This was referring to the "Acafellas" episode. And yes, I've misspelled "Schuester.")
Fortunately, the next week, we got an answer to exactly where we were: towards the beginning of the episode, Ken Tanaka made reference to the football team being 0-6. Assuming (generously) that it took one week for the following:
  1. Kurt joins the football team as its kicker (Monday)
  2. Kurt and Finn convince the entire football team to take dance lessons (Tuesday)
  3. The team choreographs and rehearses a dance routine to "Single Ladies" to the point of presentability (Wednesday, Thursday)
  4. The football team, with the help of their newfound dancing skills, wins their game on Friday.
Then the team has run its record to 1-6. High school football in the North generally starts the last Friday in August, so, assuming there were no bye weeks, the game took place on October 9. Finally, we have pinned down a date!
(NOTE: At ALOTT5MA, I said this game would have taken place on October 16, based on the fact that football starts the week before Labor Day. However, with the late Labor Day this year, that was not the case. This jibes with my own high school's football schedule.)

Having figured out what day it is for a specific episode, we can keep track of the chronology by estimating how long each new episode takes. Again, I want to be generous with these estimates - a lot more happens in a typical high schooler's day than most of us remember. Anyway, "The Rhodes Not Taken" begins with Rachel having quit the Glee Club to join the school play (this happened at the end of the previous episode). Let's assume that this happened on Saturday, at a weekend rehearsal. Then the episode opens at Monday's reharsal. In the course of this episode:
  1. Will talks to Emma about having found April's transcripts, then gets in touch with April.
  2. April returns to high school and meets the gang. This, obviously, couldn't happen until Tuesday.
  3. The Glee Club rehearses two songs. Along the way, April wins over the teenagers by contributing to their delinquency. This, plausibly, takes place over the course of the rest of the week. Given the number of outfit changes, this can't just be Tuesday and Wednesday. This is important, because:
  4. They perform two songs at their invitational. This, presumably, takes place on Saturday - given the previous assumption, it can't only be Thursday, and the football team (and Cheerios) would have a game on Friday. April leaves after the first song. Fortunately, Rachel has gotten fed up with Sandy Ryerson (after, what, two rehearsals? Three?), and re-joins Glee for the second song.
After this episode, I estimate the date as being October 17. We're now caught up to this week's episode, which begins with Mr. Schuester saying that sectionals are in two weeks, and that the kids have been coasting since last week, when they got the notice that their only competition would be a school for the deaf and an all-girls alternative school. I had originally given the benefit of the doubt and decided this announcement took place before the invitational, despite April's absence, but Rachel's presence (and outfit - she did re-join Glee for a day in the last episode, but quit again partway through the rehearsal) indicates that this is post-invitational, and thus we begin on October 26 at the earliest. Will then pits the boys and girls against each other in a singing competition, to be started, and I quote, "one week from today." The boys sing on Tuesday (so it was actually the 27th at the beginning of the episode), the girls sing on Wednesday, a drug scandal hits the program on Thursday. Sue Sylvester is now co-coach of the Glee Club as of, at the earliest, November 5. Two things to note from this:

  1. It is still sunny and warm in Lima, Ohio - as evidenced by none of the Cheerios wearing tights or long-sleeved shirts under their uniforms.
  2. The Ohio high school football playoffs begin on November 6. Even if the football team has won out to finish their season, they are, at best, 4-6, and not making the playoffs. Football season is over.
And that's what you've missed on Glee. Stay tuned in the following weeks, as I keep everyone up to date on the date!

Back to Bedlam

We're back, after a two-month hiatus. I hope that I have a little more energy to keep this thing going this time.

Anyway, the last couple of graph theory lessons are ready (oh joy!), I've got a stockpile of trivia questions, and there's one new piece that needs to be somewhere other than ALOTT5MA comment threads. Stick around.

Wednesday, August 5, 2009

Sports and Spice (but not Sporty Spice)

While we're waiting for the next graph theory lesson, here's some sports and music trivia to tide you over. We've been rocking the Monday trivia lately, so this ought to catch me up. The last few weeks have been in our wheelhouse, but the writer at this particular establishment is pretty in tune to that, so I expect things to get difficult in short order.

1. Who is the only player to hit a grand slam in the Major League Baseball All-Star Game?

2. In the forty-three Super Bowls to date, only once has either team failed to score a touchdown. Which team was it? (Bonus: which year?)

3. Which team lost Super Bowl II?

4. Which NHL team plays in an arena known as "The Igloo?"

5. Which island nation produces 90% of the world's cinnamon (as of 2006)?

6. What was the name of John Lennon and Paul McCartney's first band?

7. John Lennon was shot in front of what New York hotel?

Sunday, August 2, 2009

Be Afraid. Be Very Afraid.

Lesson 10 is coming. Really. Re-checking this construction is a bear.

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

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 S3; 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 ai, 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 Xi to make it ai-light. The number of vertices we can add is limited somewhat; I'll spare the details, but an ai-light path in a minimal sAT will have a maximum of three ai-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 ai-light paths, which in turn places an upper bound on the order of the minimal graphs we can get by adding vertices to S3, 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 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.

Construction B2: In addition to v1, vertices u1and w1 are added, such that u1 is adjacent only to b2 and v1, and w1 is adjacent only to b3 and v1. Then a2b2u1v1w1b3a3 is a1-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 a2, does not produce a minimal graph: this combination will have a copy of the parasol, unless the vertex added to a2 is adjacent to v1. But, in this case, a1, a2, and w1 are in a strongly asteroidal triple, so a3 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 u2 to the path X2) also fails to make a minimal graph; adding any of the previous constructions to a3 or X3 will produce a graph in which a2 (at least) can be removed to make a smaller strongly asteroidal graph. Applying B2 a second time creates an irregular construction. If vertices u2, v2, and w2 are added to create the path a1b1u2v2w2b3a3, then there is a 3-sun unless v1 and v2 are adjacent. Adding construction B1 to X3 will produce a sun. Adding a construction of type A to a3 creates a copy of either graph 13 or 14 (in which u1, u2, and a3 are a strongly asteroidal triple), unless u2 is adjacent to v1 and/or u1 is adjacent to v2; we may assume the former. In this case, though, v2 and w2 (and the construction added to a3) 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 ui adjacent only to bi and v1. Each ui is aj-light for ji, and so for each i, there is an ai-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.

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)
  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 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!

Thursday, June 25, 2009

Don't Be Cruel, Just Beat It

The L.A. Times reports that Michael Jackson has died. Someone will come up with a conspiracy theory fairly quickly; this is my attempt to beat everyone else to it. The following statement is entirely fabricated.

As everyone knows, Elvis faked his death back in 1977, and has since been living a comfortable retirement on a South Pacific island. What you may not know, however, is that Presley actually passed away last month at the age of 74. In an auction attended only by members of the Pentavirate (Jacko joined shortly after the release of Bad, filling the void left by Colonel Sanders a decade earlier), Jackson purchased Presley's island, and has faked his own death to retire to same.

The members of Duke Phillips Preschool wishes to send their condolences and prayers to Jackson's family.

Thursday, June 11, 2009

I'm gonna be a supermodel

Everyone loved Suzanne Vega so much, now I give you:


Go ahead, try to get it out of your head.