Scheduling Combinatorics

© Copyright 2008, Paul Kislanko

I didn't see A lightweight approach to scheduling in time to reply to it, but had I my reply would've gone along these lines.

We see such "analysis" pieces every year, and they are often presented as moral judgements, instead of the mere observations they are. It's easy to say "so-and-so should've scheduled better" but not as easy to say how exactly they could have. And every such "analysis" I've seen that tries to address non-conference schedules at a conference level ignores essential differences in scheduling combinatorics.

The Big Picture

Combinatorics is just a fancy word for counting things, and what we want to count here is the number of "good" matchups in the schedule compared to the number of possible matchups.

Since there are 120 teams in the division 1 Football Bowl Subdivision (hereafter referred to as D1A) there are (120 × 119) ÷ 2, or 7,140 possible matchups. Since each team can only play 12 games, the best a team can do is play 12 119ths the field, and most don't play 12. For 2008, there are 754 (10.56%) such matchups. We'll use that as a "baseline" percentage.

Fans (and self-proclaimed "experts") complain that we don't get enough matchups between "top" teams. Using the Majority Consensus rank of 106 computer rankings for 2007, there are 39 teams ranked #40 or better. That's 741 possible matchups, and in 2008 we have 202 top-40 vs top-40 games, or 27.26% of all possible such. That's over 43% of all games scheduled by top-40 teams - a lot more than we'd expect compared to the baseline, but it is worth noting that most of those are conference games.

( I define the "majority consensus" rank for a team to be the best rank for which at least 54 of the 106 rankings have the team ranked at least that highly. )

The next most common complaint is that top BCS-autobid conference teams play "too many" non-autobid conference teams, or (heavens!) Football Championship Subdivision (1AA) teams. 35 BCS teams finished in the top 40 in 2007, and are scheduled to play:

which doesn't look as dire as some would have us believe. Note again, though, that only 24 of those top-40 BCS vs top-40 BCS are non-conference games.

Could it be better?

One wonders how easy it would be to improve schedules that receive the most attention (criticism.) To identify those we order the top-40 BCS teams by (# non-BCS opponents + # non-D1A opponents) and team rank - presumably the better-ranked teams prefer better opponents. For each team we need to count the number of weekends that "need" improvement, the available dates, and the number of candidate opponents.

# of weekends that need improvement
is just the number of non-BCS + non-D1A opponents.

The "complaints" are somewhat problematic themselves. For this purpose we'll just have to ignore that non-BCS teams already complain about top BCS teams not giving them the opportunities it takes to get "proper" recognition, 2007 Hawaii notwithstanding. (For the most part, this is a myth, but for top-40 non-BCS teams there's some validity to the obsevation.) And it's not clear that the sport would be better off if the 1AA programs were cut off from the best source of funding available to them.

Available dates
are the currently scheduled BYE weeks (not including those reserved for a potential conference championship game) and those that are scheduled against non-BCS or non-D1A opponents (but see the note above.) These weekends are listed in the table below under the heading Opportunities.
Candidate opponents
are those who have at least one "available date" in common with the team. See the notes at the end of the table for an important qualification.

Opportunities for Schedule Improvement

Rank Team #nonBCS #nonD1A Need?      #Opps Opps #Candidates
1 LSU 3 1 4   6 – 1 2 3 6 10 12 23
29 Texas Tech 2 2 4   6 – 1 2 3 4 5 12 29
31 Wisconsin 3 1 4   5 – 1 2 3 4 13 30
3 Missouri 2 1 3   5 – 2 3 4 5 13 28
4 West Virginia 2 1 3   6 – 1 2 3 5 8 12 29
4 Kansas 2 1 3   5 – 1 2 4 5 13 28
7 Ohio State 2 1 3   4 – 1 2 4 10 27
9 Virginia Tech 2 1 3   5 – 1 2 6 7 10 27
14 Tennessee 3 0 3   5 – 2 3 6 11 12 22
15 Boston College 2 1 3   5 – 1 3 4 5 7 29
15 Texas 3 0 3   5 – 1 2 4 5 13 28
17 Cincinnati 3 1 3   6 – 1 3 4 5 6 8 30
18 Auburn 2 1 3   5 – 1 2 8 11 13 21
19 South Florida 2 1 3   6 – 1 2 4 7 11 14 28
23 Illinois 2 1 3   4 – 2 3 4 11 29
26 Kentucky 2 1 3   5 – 2 3 4 5 13 25
28 Arkansas 2 1 3   5 – 1 2 5 10 12 23
35 Mississippi St 2 1 3   5 – 1 2 6 9 11 24
38 Oklahoma St 2 1 3   5 – 2 3 4 5 13 29
40 Alabama 3 0 3   5 – 2 3 7 10 13 22
Rank Team #nonBCS #nonD1A Need?      #Opps Opps #Candidates
4 Georgia 1 1 2   4 – 1 2 6 13 22
8 Oklahoma 1 1 2   4 – 1 4 5 12 25
14 Arizona St 1 1 2   5 – 1 3 5 8 13 26
21 Michigan 2 0 2   3 – 2 4 7 27
22 Clemson 0 2 2   4 – 2 4 6 9 26
25 Penn State 1 1 2   3 – 1 4 10 25
32 Virginia 1 1 2   4 – 2 4 7 12 26
33 Connecticut 1 1 2   5 – 1 2 7 11 14 26
40 South Carolina 1 1 2   4 – 4 5 9 13 22
11 Florida 0 1 1   3 – 3 8 13 14
13 Oregon 1 0 1   4 – 2 8 13 15 26
28 Wake Forest 1 0 1   3 – 3 5 6 21
40 California 1 0 1   4 – 4 5 7 14 24
5 Southern California 0 0 0   3 – 2 4 13 27
20 Oregon St 0 0 0   3 – 4 9 15 18
Notes:
  1. When producing this report I failed to include the criterion that a "candidate opponent" must not only have a common BYE date but a non-zero "needs" count. So USC and Oregon State are not candidates for any team.
  2. A glance at the #Candidates column shows one of the combinatorial complexities many fail to consider: a team's choices for non-conference top-40 opponents depends upon how many of its conference-mates are in the top 40 on top of which teams have compatible dates.

    So, for a Big East team, 31 of the 35 top-40 teams are "non-conference," but for an SEC team only 25 are (and two of those are "taken" - see note 1).

  3. One could argue that a non-conference game against a BCS team from the bottom-40 is also an opportunity for improvement. I chose to exclude those because their conference-mates have no choice but to schedule them, so it would skew the results to include them for other BCS teams.

Another consequence of note 2 is a common mistake in analysis such as cited in the introduction. As we'll soon see, it's just as hard for a team from one conference to schedule a non-conference game against a top-40 BCS team as it is for a team from any other conference, but succeeding in doing so has a drastically different effect on the percentage of such games for teams in a conference that only allows 3 non-conference games (the Pac 10) than one that requires 5 (the Big East.) This isn't an apology for Big 12 or SEC scheduling tendencies, just an observation that that's not an appropriate metric so it's a waste of time to calculate it and make us re-read it every year.

Zooming In on the Big Picture

Comparing available dates of all pairs of BCS teams who finished in the top-40 last year shows that our answer is "yes" - it is possible to obtain more interconference matchups. Almost everybody who "needs" one or two could find a matchup. You can use this chart to build your team's dream schedule, just remember every time you make a new one two opportunities disappear and you create a non-good matchup of the displaced teams.
Legend
i j k ... Common opportunities occur in weeks i, j, k...
•The teams play each other
‡There are no common opportunities

I've split the pairwise matchings by conference, and included the BCS non top-40 teams just to indicate the BCS vs BCS interconference matchups involving a top-40 team. I've also indicated the unavailability of USC and Oregon State with  1 referencing note 1.

Rank Team Va Tech BC Clemson Wake VA Fla St Ga Tech MD NC Mia FL NC St Duke
1 LSU 1 2 6 10 1 3 2 6 3 6 2 12              
3 Missouri 2 3 4 5 2 4 3 5 2 4              
4 Kansas 1 2 1 4 5 2 4 5 2 4              
4 West Virginia 1 2 1 3 5 2 3 5 2 12              
4 Georgia 1 2 6 1 2 6 6 2   •          
5 Southern California1 2 4 2 4 ‡ •              
7 Ohio State 1 2 10 1 4 2 4 ‡ 2 4              
8 Oklahoma 1 1 4 5 4 5 4 12              
11 Florida ‡ 3 ‡ 3 ‡ •       •    
13 Oregon 2 ‡ 2 ‡ 2              
14 Arizona St 1 1 3 5 ‡ 3 5 ‡              
14 Tennessee 2 6 3 2 6 3 6 2 12              
15 Texas 1 2 1 4 5 2 4 5 2 4              
17 Cincinnati 1 6 1 3 4 5 4 6 3 5 6 4              
18 Auburn 1 2 1 2 ‡ 2              
19 South Florida 1 2 7 1 4 7 2 4 ‡ 2 4 7           •  
20 Oregon St1 ‡ 4 4 9 ‡ 4              
21 Michigan 2 7 4 7 2 4 ‡ 2 4 7              
23 Illinois 2 3 4 2 4 3 2 4              
25 Penn State 1 10 1 4 4 ‡ 4              
26 Kentucky 2 3 4 5 2 4 3 5 2 4              
28 Arkansas 1 2 10 1 5 2 5 2 12              
29 Texas Tech 1 2 1 3 4 5 2 4 3 5 2 4 12              
31 Wisconsin 1 2 1 3 4 2 4 3 2 4              
33 Connecticut 1 2 7 1 7 2 ‡ •       •      
35 Mississippi St 1 2 6 1 2 6 9 6 2   •          
38 Oklahoma St 2 3 4 5 2 4 3 5 2 4              
40 California 7 4 5 7 4 5 4 7     •        
40 Alabama 2 7 10 3 7 • 3 2 7              
40 South Carolina ‡ 4 5 • 5 4           •  
Rank Team Ohio St MI IL Penn St WI Mich St Purdue IN IA NWestern MN
1 LSU 1 2 10 2 2 3 1 10 1 2 3            
3 Missouri 2 4 2 4 • 4 2 3 4 13            
4 Kansas 1 2 4 2 4 2 4 1 4 1 2 4 13            
4 West Virginia 1 2 2 2 3 1 1 2 3            
4 Georgia 1 2 2 2 1 1 2 13            
5 Southern California1 • 2 4 2 4 4 2 4 13            
8 Oklahoma 1 4 4 4 1 4 1 4            
9 Virginia Tech 1 2 10 2 7 2 1 10 1 2            
11 Florida ‡ ‡ 3 ‡ 3 13            
13 Oregon 2 2 2 ‡ 2 13   •        
14 Arizona St 1 ‡ 3 1 1 3 13            
14 Tennessee 2 2 2 3 11 ‡ 2 3            
15 Boston College 1 4 4 7 3 4 1 4 1 3 4            
15 Texas 1 2 4 2 4 2 4 1 4 1 2 4 13            
17 Cincinnati 1 4 4 3 4 1 4 1 3 4            
18 Auburn 1 2 2 2 11 1 1 2 13            
19 South Florida 1 2 4 2 4 7 2 4 11 1 4 1 2 4            
20 Oregon St1 4 4 4 • 4            
22 Clemson 2 4 2 4 2 4 4 2 4            
26 Kentucky 2 4 2 4 2 3 4 4 2 3 4 13            
28 Wake Forest ‡ ‡ 3 ‡ 3            
28 Arkansas 1 2 10 2 2 1 10 1 2            
29 Texas Tech 1 2 4 2 4 2 3 4 1 4 1 2 3 4            
32 Virginia 2 4 2 4 7 2 4 4 2 4            
33 Connecticut 1 2 2 7 2 11 1 1 2            
35 Mississippi St 1 2 2 2 11 1 1 2            
38 Oklahoma St 2 4 2 4 2 3 4 4 2 3 4 13            
40 California 4 4 7 4 4 4 •          
40 Alabama 2 10 2 7 2 3 10 2 3 13            
40 South Carolina 4 4 4 4 4 13            
Rank Team MO KS OK TX TX Tech Okla St TexA&M CO NE Kans St Iowa St Baylor
1 LSU 2 3 1 2 1 12 1 2 1 2 3 12 2 3            
4 West Virginia 2 3 5 1 2 5 1 5 12 1 2 5 1 2 3 5 12 2 3 5   •        
4 Georgia 2 13 1 2 13 1 1 2 13 1 2 2 13            
5 Southern California1 2 4 13 2 4 13 4 2 4 13 2 4 2 4 13            
7 Ohio State 2 4 1 2 4 1 4 1 2 4 1 2 4 2 4            
9 Virginia Tech 2 1 2 1 1 2 1 2 2     •      
11 Florida 3 13 13 ‡ 13 3 3 13            
13 Oregon 2 13 2 13 ‡ 2 13 2 2 13            
14 Arizona St 3 5 13 1 5 13 1 5 1 5 13 1 3 5 3 5 13            
14 Tennessee 2 3 2 12 2 2 3 12 2 3            
15 Boston College 3 4 5 1 4 5 1 4 5 1 4 5 1 3 4 5 3 4 5            
17 Cincinnati 3 4 5 1 4 5 • 1 4 5 1 3 4 5 3 4 5            
18 Auburn 2 13 1 2 13 1 1 2 13 1 2 2 13            
19 South Florida 2 4 • 1 4 1 2 4 1 2 4 2 4            
20 Oregon St1 4 4 4 4 4 4            
21 Michigan 2 4 2 4 4 2 4 2 4 2 4            
22 Clemson 2 4 2 4 4 2 4 2 4 2 4            
23 Illinois • 2 4 4 2 4 2 3 4 2 3 4            
25 Penn State 4 1 4 1 4 1 4 1 4 4            
26 Kentucky 2 3 4 5 13 2 4 5 13 4 5 2 4 5 13 2 3 4 5 2 3 4 5 13            
28 Wake Forest 3 5 5 5 5 3 5 3 5           •
28 Arkansas 2 5 1 2 5 1 5 12 • 1 2 5 12 2 5            
31 Wisconsin 2 3 4 13 1 2 4 13 1 4 1 2 4 13 1 2 3 4 2 3 4 13            
32 Virginia 2 4 2 4 4 12 2 4 2 4 12 2 4            
33 Connecticut 2 1 2 1 1 2 1 2 2           •
35 Mississippi St 2 1 2 1 1 2 1 2 2            
40 California 4 5 4 5 4 5 4 5 4 5 4 5            
40 Alabama 2 3 13 2 13 ‡ 2 13 2 3 2 3 13            
40 South Carolina 4 5 13 4 5 13 4 5 4 5 13 4 5 4 5 13            
Rank Team WV Cincin S Fla CT Rutgers Lville Pitt Syracuse
1 LSU 1 2 3 12 1 3 6 1 2 1 2        
3 Missouri 2 3 5 3 4 5 2 4 2        
4 Kansas 1 2 5 1 4 5 • 1 2        
4 Georgia 1 2 1 6 1 2 1 2        
5 Southern California1 2 4 2 4 2        
7 Ohio State 1 2 1 4 1 2 4 1 2        
8 Oklahoma 1 5 12 • 1 4 1        
9 Virginia Tech 1 2 1 6 1 2 7 1 2 7        
11 Florida 3 8 3 8 ‡ ‡        
13 Oregon 2 8 8 2 2        
14 Arizona St 1 3 5 8 1 3 5 8 1 1        
14 Tennessee 2 3 12 3 6 2 11 2 11        
15 Boston College 1 3 5 1 3 4 5 1 4 7 1 7        
15 Texas 1 2 5 1 4 5 1 2 4 1 2        
18 Auburn • 1 8 1 2 11 1 2 11        
20 Oregon St1 ‡ 4 4 ‡        
21 Michigan 2 4 2 4 7 2 7        
22 Clemson 2 4 6 2 4 2        
23 Illinois 2 3 3 4 2 4 11 2 11 14        
25 Penn State 1 1 4 1 4 1       •
26 Kentucky 2 3 5 3 4 5 2 4 2   •    
28 Wake Forest 3 5 3 5 6 ‡ ‡        
28 Arkansas 1 2 5 12 1 5 1 2 1 2        
29 Texas Tech 1 2 3 5 12 1 3 4 5 1 2 4 1 2        
31 Wisconsin 1 2 3 1 3 4 1 2 4 1 2        
32 Virginia 2 12 4 2 4 7 •        
35 Mississippi St 1 2 1 6 1 2 11 1 2 11        
38 Oklahoma St 2 3 5 3 4 5 2 4 2        
40 California 5 4 5 4 7 14 7 14        
40 Alabama 2 3 3 2 7 2 7        
40 South Carolina 5 4 5 4 ‡        
Rank Team USC OR Ariz St Oreg St CA UCLA AZ Wash St WA Stanford
1 LSU 2 2 1 3 ‡ ‡          
3 Missouri 2 4 13 2 13 3 5 13 4 4 5          
4 Kansas 2 4 13 2 13 1 5 13 4 4 5          
4 West Virginia 2 2 8 1 3 5 8 ‡ 5          
4 Georgia 2 13 2 13 • ‡ ‡          
7 Ohio State • 2 1 4 4          
8 Oklahoma 4 ‡ 1 5 4 4 5       •  
9 Virginia Tech 2 2 1 ‡ 7          
11 Florida 13 8 13 3 8 13 ‡ ‡          
14 Tennessee 2 2 3 ‡ ‡ •        
15 Boston College 4 ‡ 1 3 5 4 4 5 7          
15 Texas 2 4 13 2 13 1 5 13 4 4 5          
17 Cincinnati 4 8 1 3 5 8 4 4 5          
18 Auburn 2 13 2 8 13 1 8 13 ‡ ‡          
19 South Florida 2 4 2 1 4 4 7 14          
21 Michigan 2 4 2 ‡ 4 4 7          
22 Clemson 2 4 2 ‡ 4 9 4          
23 Illinois 2 4 2 3 4 4 14          
25 Penn State 4 ‡ 1 • 4          
26 Kentucky 2 4 13 2 13 3 5 13 4 4 5          
28 Wake Forest ‡ ‡ 3 5 ‡ 5          
28 Arkansas 2 2 1 5 ‡ 5          
29 Texas Tech 2 4 2 1 3 5 4 4 5          
31 Wisconsin 2 4 13 2 13 1 3 13 4 4          
32 Virginia • 2 ‡ 4 4 7          
33 Connecticut 2 2 1 ‡ 7 14          
35 Mississippi St 2 2 1 9 ‡          
38 Oklahoma St 2 4 13 2 13 3 5 13 4 4 5     •    
40 Alabama 2 13 2 13 3 13 ‡ 7          
40 South Carolina 4 13 13 5 13 4 9 4 5          
Rank Team LSU GA FL TN Auburn KY AR Miss St AL SC Vandy MS
3 Missouri 2 3 2 13 3 13 2 3 2 13 2 3 4 5 13 2 5 2 2 3 13 4 5 13    
4 Kansas 1 2 1 2 13 13 2 1 2 13 2 4 5 13 1 2 5 1 2 2 13 4 5 13    
4 West Virginia 1 2 3 12 1 2 3 8 2 3 12 • 2 3 5 1 2 5 12 1 2 2 3 5    
5 Southern California1 2 2 13 13 2 2 13 2 4 13 2 2 2 13 4 13    
7 Ohio State 1 2 10 1 2 ‡ 2 1 2 2 4 1 2 10 1 2 2 10 4    
8 Oklahoma 1 12 1 ‡12 1 4 5 1 5 12 1 ‡ 4 5    
9 Virginia Tech 1 2 6 10 1 2 6 ‡ 2 6 1 2 2 1 2 10 1 2 6 2 7 10 ‡    
13 Oregon 2 2 13 8 13 2 2 8 13 2 13 2 2 2 13 13    
14 Arizona St 1 3 • 3 8 13 3 1 8 13 3 5 13 1 5 1 3 13 5 13    
15 Boston College 1 3 1 3 3 1 3 4 5 1 5 1 3 7 4 5    
15 Texas 1 2 1 2 13 13 2 1 2 13 2 4 5 13 • 1 2 2 13 4 5 13    
17 Cincinnati 1 3 6 1 6 3 8 3 6 1 8 3 4 5 1 5 1 6 3 4 5    
19 South Florida 1 2 1 2 ‡ 2 11 1 2 11 2 4 1 2 1 2 11 2 7 4    
20 Oregon St1 ‡ ‡ ‡ ‡ ‡ 4 ‡ 9 ‡ 4 9    
21 Michigan 2 2 ‡ 2 2 2 4 2 2 2 7 4    
22 Clemson 2 6 2 6 ‡ 2 6 2 2 4 2 2 6 9 • •    
23 Illinois 2 3 2 3 2 3 11 2 11 2 3 4 2 2 11 2 3 4    
25 Penn State 1 10 1 ‡ ‡ 1 4 1 10 1 10 4    
28 Wake Forest 3 6 6 3 3 6 ‡ 3 5 5 6 3 5 • •
29 Texas Tech 1 2 3 12 1 2 3 2 3 12 1 2 2 3 4 5 1 2 5 12 1 2 2 3 4 5    
31 Wisconsin 1 2 3 1 2 13 3 13 2 3 1 2 13 2 3 4 13 1 2 1 2 2 3 13 4 13    
32 Virginia 2 12 2 ‡ 2 12 2 2 4 2 12 2 2 7 4    
33 Connecticut 1 2 1 2 ‡ 2 11 1 2 11 2 1 2 1 2 11 2 7 ‡    
38 Oklahoma St 2 3 2 13 3 13 2 3 2 13 2 3 4 5 13 2 5 2 2 3 13 4 5 13    
40 California ‡ ‡ ‡ ‡ ‡ 4 5 5 ‡ 7 4 5    

One thing that's worth noting is that even though some matchups are theoretically possible, they're not necessarily likely. Some of the opportunity overlaps involve BYE weeks that a team won't use because they come before a big conference game or a rivalry game or even just after a long stretch without a break. An AD has to consider more than we fans do when making out a future schedule, sometimes years in advance (who knew Florida State, Georgia Tech and Miami weren't going to be top-40 teams in 2007 when they made their dates with 'em for 2008?)

More worrisome (trying not to be judgemental) is when two top-40 teams have a common scheduling opportunity because one of them canceled a scheduled game with the other. From the first chart the two teams who most need a quality opponent were originally scheduled to meet in week one, but #29 Texas Tech decided the cancellation fee was worth it not to have to face defending #1 LSU opening weekend. Had that game not previously been scheduled it's the first one we'd pick as a replacement game (see the first table) so it's hard to fault LSU for the schedule they wound up with.

Addendum - 2 Aug 2008

I actually understated the difficulties involved in trying to impose "better" schedules (more BCS top-40 vs BCS top-40 games.) We can list out all the possible matchups for each date, and count how many disappear when we use one of them.

Using only the 33 teams in last year's top-40 that don't already have an all BCS-opponent schedule, we find there are 817 date-pairs. This sounds like a lot, but there are lots of duplicates (same teams in different weeks) and 585 (71.6%) occur in the first month of the season.

Where combinatorics shows its complexities, though, is how many of those disappear when just one game is selected. For example, if the Texas Tech-LSU game were added back to the schedule, not only is that pair in week 1 eliminated, but so are the other three weeks they could've met and the 14 possible games between Texas Tech and teams besides LSU plus the 13 other possible pairings of LSU and teams other than Texas Tech in week 1. So just removing that one possible game from the list by making it an actual uses up a total of 33 possibilities. Something similar happens with every "new" pairing.

You can use the complete list of unscheduled top-40 BCS matchups to come up with better schedules. Just remember that when you "schedule" a game for a weekend you have to cross off all the possibilities for either team that weekend and all same-matchups in other weeks. Also reduce the "needs" count from the first table by one for each team in the pairing you picked, and if either becomes zero cross off all possible pairings involving the team with a zero needs count. It'd be interesting to see how many "good" games you can add before running out of options.