A Deeper Look at Schedule Topology

© Copyright 2011, Paul Kislanko

I've been writing about the schedule topology for a few years now, but mostly about what might be called the distance matrix. This is a count of how many teams each team can be connected to by an A plays B plays... chain at each of 1, 2, 3... "plays" path-lengths. When every team has an A plays B plays... path to every other team in this way, the field is connected.

To "see" what's going on, take a (large) piece of paper and place one dot on it for each team. Then for each game draw a (probably curvy) line between the dots corresponding to team A and team B if team A and team B play each other. For each team, count the number of other teams they are connected to by one line. Then count the number of teams (not in the first list) that they are connected to by two lines.

Continue through the number connected by three lines, four lines, etc. until every team is connected to every other team by some number of lines.

"Dots" are "vertices" and "lines" are "edges" in what's called the games graph.

To construct that table I only care about the length of the path between teams (the number of edges), and for any pair of teams I count the shortest such chain. Otherwise, the same game can be counted multiple times. In what follows I'll use ↔ to indicate a game: x↔y means x and y play each other; and ⇔λ as shorthand for a series of λ ↔s. Suppose A plays B and D, B plays C, and C plays D. Then not only is there the A↔B chain, there's the A↔D↔C↔B (A⇔3) and even the A↔B↔C↔D↔A↔B (A⇔5B.)

There are A⇔3B paths for each of A's opponents (including B) since there's an A⇔2A path for each of A's opponents and each of them adds to the number of paths of length 3 from A to each of A's opponents. You don't even want to think about the number of paths between A's opponents the A⇔2A add to the initial A↔B and A↔C giving B⇔2C.

If you've tried the "connect the 120 dots with 674 lines" technique and then tried to count the number of paths of length 2, 3, etc. between each pair of teams you'll hate me for waiting until now to say there's an easy way to do that without actually drawing lines that are hard to count.

First just give each of the dots a counting number, starting with 1 and ending with the number of teams (120 for the 2011 FBS field.) Then create a table where the cell corresponding to the ith row and jth column contains the number of games played by team i against team j. Call the table IM and the contents of the cell in row i and column j [ im ]i, j.

IM is the incidence matrix that describes the schedule. The number of unique paths of length λ in the games graph is given by IMλ, with [ im ]λi, j being the number of them that connect team i and team j.

To find Mk+1 for any square matrix just find Mk × M. Beginning with IM×IM = IM2 giving [ im ]2i, j - the number of paths of length 2 between every team pair. IM2×IM = IM3 where [ im ]3i, j - the number of 3-long paths between teams i and j.

While the prospect of multiplying two 120×120 matrixes might send a human back to the paper with dots and lines, computers routinely do such things before breakfast (well, mine does!)

Here's what the incidence matrix looks like for FBS' 2011 season:

Incidence Matrix

Every dot represents one end of the edge that represents the game the two ends (vertices/teams) play against each other. We don't need to draw any lines because we can make each end coincide by folding the picture along the diagonal that runs from upper left to lower right.

When I assigned the teams' row/column numbers I gave teams from the same conference consecutive rows and columns. It's easy in this picture to tell which conferences have divisions (also grouped together) and which play round-robin schedules. It's even easier to visualize the importance of interconference games.

IM 2 includes all teams that have an opponent's opponent relationship. Note that now that includes paths from each team to itself (the diagonal) once for each of its paired points in the first graph.

O-O pairs

Going from the graph of A↔B connections to A⇔2B paths "connects" many more team-pairs, but it is worth noting that more than half of the graph is still white. In all other Division One team sports over half of the team-pairs are connected by a path of length one or two. Teams connected by A⇔3B paths nearly connect the field.

O-O-O pairs
It's important to notice, though, that ⇔3 doesn't just include opponents' opponents' opponents. Because each team shows up in the ⇔2 list, a teams' opponents each show up about 10 times for each path to a true O-O-O.

You can find ⇔4 paths from every FBS team to every other FBS team;

Games graph paths of length 4
If you want to see what numbers are in each cell, see IM4.

I'll look at the powers of the incidence matrix in more detail later, but it is worrisome that over time there are fewer of the games that contribute the most to our ability to judge relative team strength.