# zbMATH — the first resource for mathematics

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.

##### MSC:
 05C20 Directed graphs (digraphs), tournaments 05C35 Extremal problems in graph theory
##### Keywords:
transitive tournament
Full Text: