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
    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
    0 references
    transitive tournament
    0 references
    0 references