NOTES ON COMBINATORIAL MATHEMATICS: TRANSITIVE SUBTOURNAMENTS,
Abstract
The report describes a round robin tournament in which each player plays one game with every other player, and each game ends in a win for one of the players. In a tournament of this type with 15 players, it is shown that some 5 players will be involved in a transitive subtournament. That is, considering only the games that the 5 players play among themselves, the players can be ranked in such a way that no upsets occur. Although the same result has been obtained by other authors using different techniques, this proof is unique in that it involves close scrutiny of the subtournament of players that have lost to one individual player. Certain families of sets of players are studied that turn out to be Steiner triple systems on seven elements. This result disproves a conjecture of the Hungarian mathematicians P. Erdos and L. Moser. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1969
- Accession Number
- AD0698737
Entities
People
- Joel Spencer
Organizations
- RAND Corporation