Posted September 2010.
We shall see that some of the same tools that help with scheduling problems can also be brought to bear on ranking questions....
Competitions are a staple of American life whether they take the form of an end of season basketball tournament between a collection of colleges, a little league baseball team playoff, or a group of individuals competing for the American chess championship. Many schemes have been devised to get at the best player or team.
Figure 1 (Digraph model for a tournament)
The diagram in Figure 1 is an example of a geometrical problem solving tool called a digraph, a short term for directed graph. It generalizes the concept of a graph, which is a diagram consisting of dots and line segments. The diagram in Figure 2 arises from suppressing the directions on the edges of the digraph in Figure 1:
Figure 2 (Tournament digraph with its arrows removed)
The dots in a graph or digraph are called vertices or nodes, while the line segments are known as edges or arcs. Note that we don't pay attention to the physical points in Figures 1 and 2 where lines between the (large) dots may meet. (In Figure 2 there are 5 such points but one can redraw the picture so that only one such non-vertex "crossing" occurs; the diagram shows connections between the same vertices.) Sometimes an effort is made to use different terms for the dots and lines in graphs and directed graphs to keep track of which of these two mathematical worlds one is working in, but here I will use the generic terms vertices for the dots and edges for the line segments. Other examples of graphs and digraphs are shown in Figures 3 and 4. Such diagrams are useful in a wide variety of applications other than for the study of tournaments.
(b) Simple polygon
Figure 3 (Examples of some graphs)
(a) (Example of a digraph)
(b) (Digraph with two vertices having two edges going in opposite directions)
Figure 4 (Examples of digraphs)
Figure 5 (Digraph showing a tournament)
Figure 6 (A tournament where each team won two games)
Figure 7 (A complete graph with 7 vertices)
Tournaments outside of sports
One of the early pioneers of understanding the structure of tournament graphs was H. G. Landau (1909-1966). Although Landau is sometimes described as a sociologist or psychologist, his academic training was as a statistician. Landau (his full name was Hyman Garshin Landau) got his doctorate in statistics in 1946 from the University of Pittsburgh. It appears that he worked during World War II at the Ballistics Research Laboratory and left there to join the Committee on Mathematical Biology at the University of Chicago. He was forced to leave the University of Chicago due to accusations by the House Un-American Activities Committee (HUAC), but did subsequently find work at Columbia University. However, Landau's interest in what are now known as tournaments did not arise from his studying of sports competitions. As so often happens in mathematics, the source of Landau's interest was something rather different. He was interested in animal behavior and the work he did grew out of dealing with the pecking orders of poultry (chickens). For each pair of chickens there appeared to be one of the two that in the chicken hierarchy was the dominant chicken with respect to that pair. Landau became interested in understanding the nature of these hierarchies for chickens and their properties.
Figure 8 (Template for paired comparisons of 8 fruits)
Other approaches to rankings
Consider the tournament graph in Figure 9.
Figure 10 (William Rowan Hamilton)
It is worth noting that as the number of teams in a tournament goes up, the number of inequivalent (non-isomorphic) tournament digraphs grows rapidly. Here are the beginning statistics:
Remember that non-isomorphic tournaments might have the same score sequence, so determining the number of different score sequences with n teams is a different problem. The table below shows the number of different score sequences which can arise for n teams. Many different tournaments give rise to the same score sequence as the number of teams grows.
Cook, W. and I. Golan, M. Kress, Heuristics for ranking players in round robin tournaments, Computers and Operations Research 15 (1988) 135-144.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance