Disproof of a Conjecture of Erdos and Moser on Tournaments

摘要

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)