DISPROOF OF A CONJECTURE OF ERDOS AND MOSER ON TOURNAMENTS,
Abstract
Erdos and Moser displayed a tournament of order 7 with no transitive subtournament of order 4 and conjectured for each positive integer k existence of a tournament of order 2 superscript (k-1)-1 with no transitive subtournament of order k. The conjecture is disproved for k = 5. Further, every tournament of order 14 has a transitive subtournament of order 5. Inductively, the conjecture is false for all orders above 5. Existence and uniqueness of a tournament of order 13 having no transitive subtournament of order 5 are shown. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1964
- Accession Number
- AD0678783
Entities
People
- E. T. Parker
- K. B. Reid
Organizations
- University of Illinois Urbana–Champaign