About the inequalities of Erdős and Moser on the largest transitive subtournament of a tournament. (English) Zbl 0609.05042
Combinatoire énumérative, Proc. Colloq., Montréal/Can. 1985, Lect. Notes Math. 1234, 308-320 (1986).
[For the entire collection see Zbl 0602.00001.]
Let v(n) denote the largest integer v such that every tournament \(T_ n\) contains a transitive subtournament \(T_ v\). The author states that v(n)\(\leq [-1\frac{1}{2}+(3n+3\frac{1}{4})^{1/2}]\); but an argument is given only for those integers n for which a homogeneous tournament \(T_ n\) exists and the inequality is in fact false when, for example, \(n=2\) or 8. The author also states that v(n)\(\geq [\log_ 2(n/14)]+5\) for \(n\geq 14\); K. B. Reid and E. T. Parker [J. Comb. Theory 9, 225-238 (1970; Zbl 0204.246)] showed that v(n)\(\geq [\log_ 2(16n/7)]\) for \(n\geq 14\). The author also makes some observations about the size of the transitive subtournaments in certain homogeneous tournaments of order 27 and 31, among other things.
Let v(n) denote the largest integer v such that every tournament \(T_ n\) contains a transitive subtournament \(T_ v\). The author states that v(n)\(\leq [-1\frac{1}{2}+(3n+3\frac{1}{4})^{1/2}]\); but an argument is given only for those integers n for which a homogeneous tournament \(T_ n\) exists and the inequality is in fact false when, for example, \(n=2\) or 8. The author also states that v(n)\(\geq [\log_ 2(n/14)]+5\) for \(n\geq 14\); K. B. Reid and E. T. Parker [J. Comb. Theory 9, 225-238 (1970; Zbl 0204.246)] showed that v(n)\(\geq [\log_ 2(16n/7)]\) for \(n\geq 14\). The author also makes some observations about the size of the transitive subtournaments in certain homogeneous tournaments of order 27 and 31, among other things.
Reviewer: J.W.Moon
MSC:
| 05C20 | Directed graphs (digraphs), tournaments |
