Topics on Tournaments in Graph Theory

John W. Moon

• Publisher: Dover Publications
• Year: 2015
• eBook ISBN: 9780486804736
• Topic: Mathématiques
• Subtopic: Mathématiques discrètes

Tournaments, in this context, are directed graphs ― an important and interesting topic in graph theory. This concise volume collects a substantial amount of information on tournaments from throughout the mathematical literature. Suitable for advanced undergraduate students of mathematics, the straightforward treatment requires a basic familiarity with finite mathematics.
The fundamental definitions and results appear in the earlier sections, and most of the later sections can be read independently of each other. Subjects include irreducible and strong tournaments, cycles and strong subtournaments of a tournament, the distribution of 3-cycles in a tournament, transitive tournaments, sets of consistent arcs in a tournament, the diameter of a tournament, and the powers of tournament matrices. Additional topics include scheduling a tournament and ranking the participants, universal tournaments, the use of oriented graphs and score vectors, and many other subjects.

1.   Introduction

A (round-robin) tournament T_n consists of n nodesp₁, p₂, · ··, p_n such that each pair of distinct nodes p_j and p_j is joined by one and only one of the oriented arcs

If the arc

is in T_n, then we say that p_i dominates p_j (symbolically, p_i →p_j). The relation of dominance thus defined is a complete, irreflexive, antisymmetric, binary relation. The score of p_i is the number s_i of nodes that p_i dominates. The score vector of T_n is the ordered n-tuple (s₁, s₂, ···, s_n). We usually assume that the nodes are labeled in such a way that s₁ ≤ s₂ ≤ · · · ≤ s_n.

Tournaments provide a model of the statistical technique called the method of paired comparisons. This method is applied when there are a number of objects to be judged on the basis of some criterion and it is impracticable to consider them all simultaneously. The objects are compared two at a time and one member of each pair is chosen. This method and related topics are discussed in David (1963) and Kendall (1962). Tournaments have also been studied in connection with sociometric relations in small groups. A survey of some of these investigations is given by Coleman (1960). Our main object here is to derive various structural and combinatorial properties of tournaments.

Exercises

1. Two tournaments are isomorphic if there exists a one-to-one dominance-preserving correspondence between their nodes. The nonisomorphic tournaments with three and four nodes are illustrated in Figure 1. Determine the number of ways of assigning the labels to the nodes of these tournaments and verify that there are a total of

labeled tournaments T_n when n = 3, 4.

Figure 1

2. The complement of a tournament is obtained by reversing the orientation of all its arcs. A tournament is self-complementary if it is isomorphic to its complement. Show that self-complementary tournaments T_n exist if and only if n is odd. [Sachs (1965).]

2. Irreducible Tournaments

A tournament T_n is reducible if it is possible to partition its nodes into two nonempty sets B and A in such a way that all the nodes in B dominate all the nodes in A; the tournament is irreducible if this is not possible. It is very easy to determine whether a tournament T_n is reducible; if (s₁, s₂,· · ·, s_n) is the score vector of T_n and s₁ ≤ s₂ ≤ ··· ≤ s_n, then T_n is reducible if and only if the equation

holds for some value of k less than n.

The (dominance) matrix of the tournament T_n is the n by n matrix M(T_n) = [aij] in which a_ij is 1 if p_i → p_j and 0 otherwise. All the diagonal entries are 0. A tournament matrix satisfies the equation

where J is the matrix of l’s and I is the identity matrix. If the tournament T_n is reducible and the scores

are in nondecreasing order, then its matrix has the structure

where M₁ and M₂ are the matrices of the tournaments defined by the sets A and B of the preceding paragraph.

There are

labeled tournaments T_n. We now derive an approximation for P(n), the probability that a random tournament T_n is irred...

Table of contents

• Cover
• Title Page
• Copyright Page
• Preface
• Contents
• 1. Introduction
• 2. Irreducible Tournaments
• 3. Strong Tournaments
• 4. Cycles in a Tournament
• 5. Strong Subtournaments of a Tournament
• 6. The Distribution of 3-cycles in a Tournament
• 7. Transitive Tournaments
• 8. Sets of Consistent Arcs in a Tournament
• 9. The Parity of the Number of Spanning Paths of a Tournament
• 10. The Maximum Number of Spanning Paths of a Tournament
• 11. An Extremal Problem
• 12. The Diameter of a Tournament
• 13. The Powers of Tournament Matrices
• 14. Scheduling a Tournament
• 15. Ranking the Participants in a Tournament
• 16. The Minimum Number of Comparisons Necessary to Determine a Transitive Tournament
• 17. Universal Tournaments
• 18. Expressing Oriented Graphs as the Union of Bilevel Graphs
• 19. Oriented Graphs Induced by Voting Patterns
• 20. Oriented Graphs Induced by Team Comparisons
• 21. Criteria for a Score Vector
• 22. Score Vectors of Generalizations of Tournaments
• 23. The Number of Score Vectors
• 24. The Largest Score in a Tournament
• 25. A Reversal Theorem
• 26. Tournaments with a Given Automorphism Group
• 27. The Group of the Composition of Two Tournaments
• 28. The Maximum Order of the Group of a Tournament
• 29. The Number of Nonisomorphic Tournaments
• Appendix
• References
• Index