Connectivity measurements, again

© Copyright 2009, Paul Kislanko

You only thought I'd run out of different ways to measure the schedule graph! Well, I have, but this is kind of a follow-on to my 11 August essay.

Sets of sets

The first step in the Network Group Analysis is to find all the subsets S of U in which every team in the subset plays every other team in the subset. There are 4160 such subsets, the largest consisting of the Pac 10 teams since they each play all the other Pac 10 teams.

1022 of the 4160 are just subsets of that largest group and there's a similar redundancy due to round-robins in other conferences or conference divisions. So we define

S′ = {S |S is not a proper subset of a larger S}
There are 278 elements in S′: 1 with 10 members, 3 with 9 (WAC, MWC, and Sun Belt), 1 with 8 (Big East), 9 with 6 (divisions in 12-team conferences) 17 with 5, 85 with 4, 61 with 3, and 101 with 2.

The 101 elements of S′ with two members are the the games between teams who have no common opponents. I suggested that those games contributed the most to connecting the field, because each of the teams' opponents would contribute the team's opponent's OO list.

The rest of that article dealt with Jeff Bihl's suggestion to look at the sets of games (edges) instead of sets of teams (vertices) in the schedule graph. Here I'll pick up where I left off in the quoted text.

Define "connectors" as

S″ = { S′ | at least one t∈S′ and t ∉ any other S′ that contains all other elements }
The short version of that is S″ is the subset of S′ that contains at least one team t that's in a different S′ than all the others. An even shorter version is S″ is the set of all members of S′ for which not all teams are from the same conference.

There are 159 members of S″: Connecting Subgroups.

Finally, we can use S″ to return to the question "which teams' schedules contribute the most to connectivity. Every team appears in at least two of these subsets, and by counting the number of unique games represented in any subset of S″ we find that 269 of 675 games contribute the most:
#Groups #Games Team O2 O3 O4 O5
8 12 Navy 3 5 0 0
6 12 Notre Dame 2 2 1 1
9 11 Army 5 3 1 0
5 8 Purdue 1 3 1 0
4 7 Eastern Michigan 2 1 1 0
4 7 Florida Atlantic 2 1 1 0
4 7 Hawaii 1 3 0 0
5 6 Idaho 2 3 0 0
5 6 Nevada 2 3 0 0
4 6 Ball State 1 2 1 0
4 6 Colorado St 0 4 0 0
4 6 Florida Intl 2 2 0 0
4 6 Michigan 0 3 1 0
4 6 Penn State 0 3 1 0
4 6 Texas 2 2 0 0
4 6 Troy 1 3 0 0
3 6 Clemson 0 3 0 0
3 6 Rice 1 1 1 0
3 6 Southern California 1 1 0 1
3 6 Stanford 1 1 0 1
#Groups #Games Team O2 O3 O4 O5
3 6 Temple 0 2 1 0
3 6 Washington 2 0 0 1
3 6 Washington St 2 0 0 1
4 5 Bowling Green 3 1 0 0
4 5 BYU 3 1 0 0
4 5 Colorado 2 2 0 0
4 5 Connecticut 3 1 0 0
4 5 LSU 3 1 0 0
4 5 Miami-Ohio 3 1 0 0
4 5 New Mexico St 2 2 0 0
4 5 Ohio State 3 1 0 0
4 5 Pittsburgh 2 2 0 0
4 5 San Diego St 1 3 0 0
4 5 Tennessee 3 1 0 0
4 5 Texas A&M 3 1 0 0
4 5 Toledo 2 2 0 0
4 5 Utah 2 2 0 0
4 5 Vanderbilt 2 2 0 0
4 5 Virginia Tech 2 2 0 0
4 5 Western Michigan 0 4 0 0
#Groups #Games Team O2 O3 O4 O5
3 5 Arkansas St 2 0 1 0
3 5 Indiana 1 2 0 0
3 5 Michigan St 0 2 1 0
3 5 Minnesota 2 0 1 0
3 5 Nebraska 1 1 1 0
3 5 New Mexico 1 2 0 0
3 5 North Texas 0 3 0 0
3 5 Northwestern 2 0 1 0
3 5 UAB 1 2 0 0
3 5 UL Lafayette 1 1 1 0
2 5 Texas Tech 0 1 1 0
4 4 Louisville 4 0 0 0
3 4 Akron 0 3 0 0
3 4 Arkansas 2 1 0 0
3 4 Auburn 2 1 0 0
3 4 Baylor 2 1 0 0
3 4 Boise St 2 1 0 0
3 4 Central Michigan 2 1 0 0
3 4 Cincinnati 2 1 0 0
3 4 East Carolina 0 3 0 0
#Groups #Games Team O2 O3 O4 O5
3 4 Florida 1 2 0 0
3 4 Florida St 2 1 0 0
3 4 Georgia 2 1 0 0
3 4 Iowa State 2 1 0 0
3 4 Kansas 2 1 0 0
3 4 Marshall 1 2 0 0
3 4 Maryland 2 1 0 0
3 4 Memphis 1 2 0 0
3 4 Miami-Florida 2 1 0 0
3 4 Middle Tenn St 2 1 0 0
3 4 Mississippi St 2 1 0 0
3 4 Northern Illinois 1 2 0 0
3 4 Ohio 2 1 0 0
3 4 SMU 2 1 0 0
3 4 UNLV 1 2 0 0
3 4 Utah St 1 2 0 0
3 4 UTEP 2 1 0 0
3 4 Virginia 2 1 0 0
3 4 West Virginia 2 1 0 0
3 4 Wyoming 1 2 0 0
#Groups #Games Team O2 O3 O4 O5
2 4 Fresno St 0 2 0 0
2 4 Houston 1 0 1 0
2 4 Louisiana Tech 0 2 0 0
2 4 Oklahoma St 1 0 1 0
2 4 San Jose St 0 2 0 0
2 4 Syracuse 0 1 1 0
2 4 Wisconsin 0 2 0 0
3 3 Boston College 3 0 0 0
3 3 Buffalo 3 0 0 0
3 3 Iowa 3 0 0 0
3 3 Kentucky 3 0 0 0
3 3 Missouri 3 0 0 0
3 3 Oklahoma 3 0 0 0
3 3 Oregon 3 0 0 0
3 3 Rutgers 3 0 0 0
3 3 Southern Miss 3 0 0 0
3 3 Tulane 3 0 0 0
3 3 Tulsa 3 0 0 0
3 3 UCF 3 0 0 0
3 3 UCLA 3 0 0 0
#Groups #Games Team O2 O3 O4 O5
3 3 UL Monroe 3 0 0 0
3 3 Wake Forest 3 0 0 0
3 3 Western Kentucky 3 0 0 0
2 3 Air Force 1 1 0 0
2 3 Alabama 1 1 0 0
2 3 Georgia Tech 0 2 0 0
2 3 Illinois 1 1 0 0
2 3 Kansas St 1 1 0 0
2 3 Kent St 1 1 0 0
2 3 Mississippi 0 2 0 0
2 3 North Carolina 1 1 0 0
2 3 North Carolina St 1 1 0 0
2 3 South Carolina 1 1 0 0
2 3 South Florida 1 1 0 0
2 3 TCU 1 1 0 0
2 2 Arizona 2 0 0 0
2 2 Arizona St 2 0 0 0
2 2 California 2 0 0 0
2 2 Duke 2 0 0 0
2 2 Oregon St 2 0 0 0
#Groups #Games Team O2 O3 O4 O5
           
159 269 #Groups of order: 101 52 5 1