Tejas Iyer's 2016 honours thesis in mathematics, on "Random Tournaments",
supervised by
Brendan McKay and
Scott Morrison, is available here.
Outline
Tournaments are an important class of directed graph. They were first introduced by Landau in 1953 [Lan53] in order to model dominance relations in flocks of chickens and nowadays are used widely in comparison based ranking, with applications to biology, chemistry, networks and sports.
This thesis concerns itself with results related to random tournaments, which are probability distributions over tournaments. In Chapter 1, we provide a brief introduction to the theory of tournaments and prove many famous results in the area. Then, in Chapter 2, we introduce random tournaments and provides a brief survey of results in the field.
In Chapter 3, we introduce the combinatorial objects of multi-tournaments, generalised multi-tournaments and generalised tournaments which are closely related to random tournaments. By using the tools of convex analysis, we prove some interesting results related to these objects which, for example, have interesting implications for voting theory.
Chapter 4 uses the theory developed in Chapter 3 to derive results related to a special type of random tournament called the β-model. This has many interesting applications to the study of comparison based ranking. By making use of results from this chapter, in Chapter 5 we derive an asymptotic formula for the number of tournaments with a particular score vector (see Definition 1.1.21) that works for a wide range of ‘tame’ score vectors. This provides a means for one to calculate the probability of a tournament with a particular ‘tame’ score vector with respect to any β-model random tournament.
The methodologies in Chapters 3, 4 and 5 are mostly original, inspired by similar results in the field of random graphs and the direction of the author’s supervisor Brendan McKay and Mikhail Isaev. The results are also new, unless otherwise stated.
