Accession Number : AD0698737

Title :   NOTES ON COMBINATORIAL MATHEMATICS: TRANSITIVE SUBTOURNAMENTS,

Corporate Author : RAND CORP SANTA MONICA CALIF

Personal Author(s) : Spencer,Joel

Report Date : NOV 1969

Pagination or Media Count : 18

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)

Descriptors :   (*GAME THEORY, *COMBINATORIAL ANALYSIS), GRAPHICS, SET THEORY, THEOREMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE