On tournaments free of large transitive subtournaments (Q1393032)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On tournaments free of large transitive subtournaments |
scientific article |
Statements
On tournaments free of large transitive subtournaments (English)
0 references
2 August 1998
0 references
\textit{P. Erdős} and \textit{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.
0 references
transitive tournament
0 references