## Who Won!We shall see that some of the same tools that help with scheduling problems can also be brought to bear on ranking questions....
Joseph Malkevitch
## Introduction
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)
## Winners and rankings
The diagram in Figure 1 is an example of a geometrical problem solving tool called a
Figure 2 (Tournament digraph with its arrows removed)
The dots in a graph or digraph are called (a) tree
(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)
n teams if and only if:
## Other approaches to rankingsConsider the tournament graph in Figure 9. Figure 9
Figure 10 (William Rowan Hamilton)
Figure 11
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
## References
Cook, W. and I. Golan, M. Kress, Heuristics for ranking players in round robin tournaments, Computers and Operations Research 15 (1988) 135-144.
Joseph Malkevitch |
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 |