ere's
the scheduling problem that faced the XFL, the new
smack-in-the-mouth, kick-in-the-groin professional football
league that has its premiere tonight.
Two divisions with four teams each; each team plays every
other team in its own division twice and the teams in the other
division once. So far so good. Then the headaches began. Marquee
name games — like the Las Vegas Outlaws against the New York/New
Jersey Hitmen — had to take place on Saturday nights to mesh
with NBC's schedule, and the openers had to be in warm- weather
locations (no blizzards) and smaller stadiums (so the stands
would looked packed). Teams were not supposed to have too many
away games in a row, but the Chicago Enforcers could not play at
Soldier Field in February because the Auto Show needed the
parking lots; the Outlaws could not play at home in Week 8
because of the Moto Cross show; and Orlando Rage was probably
going to be displaced in Week 4 for a concert.
The organizers could have spent weeks or months matching and
rematching teams. But two mathematicians at the University of
Vermont — a college that doesn't even have a football team —
thought they could do better.
So Jeff Dinitz and Dalibor Froncek, experts in an arcane
field of math called combinatorics, offered to be the brains
behind the brawns' schedule.
"I just called them out of the blue," Mr. Dinitz, the
chairman of the mathematics and statistics department, said. "I
was surprised they were pretty receptive."
Indeed, the XFL, which was created by the World Wrestling
Federation, adopted Mr. Dinitz's and Mr. Froncek's schedule
virtually unchanged.
"We were very, very happy," said Rich Rose, a senior
consultant to the league who worked with the mathematicians.
Mr. Dinitz has been a fervent football fan ever since
graduate school at Ohio State in the late 1970's when the
legendary Woody Hayes coached. He invited Mr. Froncek, a
visiting professor from the Czech Republic — a nation without
the finer art of football — to his house to watch the games. One
day last February he mentioned to Mr. Froncek that a new league
was forming.
"I said, `If it's new then they have no schedule,' " Mr.
Froncek explained. " `Don't you think we should offer that we
would make a schedule for them?' I was pretty familiar with
these kinds of schedules. They're quite similar to what I have
done for the Czech guys." Mr. Froncek creates the schedules for
the 12- team Czech basketball league and the 14- team Czech
hockey league. Mr. Dinitz, meanwhile, discusses the N.F.L.'s
cumbersome scheduling procedure in a handbook of combinatorial
designs for which he was a co-editor.
So Mr. Dinitz got on his computer and went to the XFL's home
page and called the number listed. A public relations person
answered and, to Mr. Dinitz's amazement, he was quickly put in
touch with Mr. Rose. He began to schmooze football with him.
As it turned out, their timing was perfect. "We knew the
basics" of what we wanted, Mr. Rose said, "but we hadn't gotten
down to developing a schedule."
Mr. Dinitz said that the XFL had taken a crack at it and was
in trouble. "They sent us a sample schedule and it wasn't very
good," he said, "so we knew that we could help them."
For hundreds of years mathematicians have fiddled with
combination problems. Seventeenth-century mathematicians were
obsessed with figuring out gambling odds, like what the chances
are of getting a pair of aces in five-card poker. Galileo
figured out the odds for dice.
Las Vegas isn't the only place where combinatorics mavens
gravitate. It can also be used to devise a college course
schedule that accommodates all students' class preferences,
postal routes that begin and end in the same place but ensure
that no block is walked twice, and pharmaceutical experiments
that require trying out different combinations of drugs. In the
last few decades the field has become critically important
because it is used in computers.
"The main problem is to combine constraints," Mr. Froncek
said. "You can do one thing relatively well and the other
relatively well, but when you want to put these things together,
you can't do that without a deep knowledge of some mathematical
methods."
For the XFL schedule, Mr. Rose sent Mr. Dinitz and Mr.
Froncek a list of must-haves (like one Eastern time game and one
Pacific time game each weekend) and a list of
it-would-be-nice-to-haves (like minimizing the number of times
teams had to travel coast to coast).
Mr. Dinitz and Mr. Froncek used graphs to visualize the
schedule. "Once you picture something, it's a lot easier to work
with," Mr. Dinitz explained. "I represent each of the eight
teams by just a dot on my page. There's a dot for New York and a
dot for Chicago, and if New York is at Chicago, I'll draw a line
between them with an arrow from New York to Chicago."
He and Mr. Froncek kept adding dots and flipping arrows,
trying out various combinations. "The cool thing is it's
mathematics, but there isn't an equation in it," Mr. Dinitz
said.
By the end of March, the two professors sent the XFL three
possible schedules that satisfied various soups of requirements
and preferences. They asked for $1,000 and an expense-paid trip
to the league's Super Bowl. Excuse me, Mr. Rose scolded over the
telephone, the N.F.L. has a Super Bowl; the XFL has a
Championship Game.
They received a check for $1,250, with no mention of
championship tickets. But then in July, Mr. Rose called back
with the first in a series of new requirements (for example, the
San Francisco Demons had to be at home the first week), and wish
lists (that Los Angeles be the host to either New York or
Chicago). The two mathematicians also made some suggestions of
their own, like avoiding three home games in a row, and an
intradivisional round robin for the last three weeks.
They asked for $4,000 more, a lot less than the $100 an hour
that Mr. Dinitz usually charges for consulting. "I didn't know
how much to ask," he said, and "I didn't want to scare them
away." Still, he and Mr. Froncek began suggesting other types of
remuneration at the end of their letters: "We also remember that
the XFL is into performance bonuses — does that include us? How
about one of those cool-looking footballs? Stock options?" (So
far, only the footballs have shown up.)
After the 14th version of the schedule, which they labeled X5
and called perfect, the league was satisfied.
"Jeff and Dalibor were great," Mr. Rose said, adding that
there were a couple of last- minute adjustments to X5. "We fully
plan on using them in 2002."
Mr. Dinitz is having an XFL party at his house tonight for
the math department. And while the XFL has unveiled its schedule
to tens of millions of potential fans, he and Mr. Froncek plan
to unveil the work behind that schedule to tens of combinatorics
fans in the March-April issue of Congressus Numerantium, a
journal published in Winnipeg.
So what about the N.F.L.? Mr. Dinitz said he believed they
could improve its schedule, too, "but we haven't gotten around
to calling them yet."
