On tournaments free of large transitive subtournaments. (English) Zbl 0918.05058

P. Erdős and L. Moser [Can. Math. Bull. 7, 351-356 (1964; Zbl 0129.34701)] posed the problem of determining, for each integer \(n>0\), the largest integer \(v(n)\) such that all tournaments on \(n\) vertices contain the transitive tournament \(\text{TT}_{v(n)}\) on \(v(n)\) vertices. It is known that \(v(n)=3\) for \(4\leq n\leq 7\), \(v(n)=4\) for \(8\leq n\leq 13\), \(v(n)=5\) for \(14\leq n\leq 27\) and \(v(n)\geq 6\) for \(n>27\). Moreover it has been shown that there is a unique tournament with no \(\text{TT}_4\) on 6 and 7 vertices. There is a unique tournament on 13 vertices with no \(\text{TT}_5\) and a unique tournament on 27 vertices with no \(\text{TT}_6\).
In this paper it is shown that there is a unique tournament on 12 vertices with no \(\text{TT}_5\) and there is a unique tournament on 26 vertices with no \(\text{TT}_6\). It is shown that every tournament on 54 vertices contains \(\text{TT}_7\). Finally special classes of tournaments are studied with the aid of a computer.


05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory


Zbl 0129.34701
Full Text: DOI