Fun&Games with Sets and Subsets - some corrections

© Copyright 2009, Paul Kislanko

In Fun&Games with Sets and Subsets I wrote

We tend to think of the FBS football schedule as not being as well-connected as basketball or baseball because fewer than half the team-pairs are opponents' opponents. However, it turns out that the connections that do exist are highly robust. A few years ago in baseball there was one A↔B↔C↔D↔E chain which if broken would cause the diameter of the schedule graph to grow from 4 to at least 5. If we count the number of games with a non-zero RC for each of the 237 FBS team-pairs that are 4 steps apart, we find that to increase the schedule graph's diameter by 1 we'd need to eliminate 69 games. That's over 10 percent of the schedule!
but while what I wrote in the article was otherwise correct, it turns out the program that produced the report I based the statement on was not counting games as I described.

I found the error while generalizing "responsibility count" to include distances less than the schedule graph's diameter. Define RCn(game) (1 < n ≤ diameter) as
x ∈ O[ i ](a) and y ∈ O[ j ](b)
or
x ∈ O[ j ](a) and y ∈ O[ i ](b)
and
distance(x,y) = n
For even n, i = ½ n and j = i-1. For odd n, i=j = ⌊ ½ n ⌋. We take O[ 0 ](t) = { t } to find pairs 2 steps apart. ⌊ x ⌋ is the greatest integer less than x. (Just divide by 2 and round down.)

Now we can define a more complete measure of a game's contribution to connectivity:
WRC(game) = d
∑ [ (i-1)× RCi(game) ]
i=2
(d is the diameter of the schedule graph. We don't need i=1 because that's just the list of games themselves.)

The Connectivity Contribution by Game includes corrected values for RC4(game) and the corresponding count of games that connect team-pairs 4 edges apart. The connections are still robust, but not astonishingly so.