Problem 1216

A tournament is a complete directed graph. Let $f(n)$ be such that every tournament on $n$ vertices contains a transitive tournament on $f(n)$ vertices (i.e. one such that if $i\to j\to k$ then $i\to k$ ).

Is it true that $f(n)=\lfloor \log_2 n\rfloor +1$ ?

Source: erdosproblems.com/1216

Graph theory
Ramsey theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. Reid and Parker proved in 1970 that every tournament on $14$ vertices contains a transitive subtournament on $5$ vertices (Theorem 4, printed p. 235; with their $13$ -vertex tournament free of $TT_5$ , pp. 235--236, this is $R(5)=14$ ), so $f(14)=5$ while $\lfloor\log_214\rfloor+1=4$ , and more generally $f(n)\ge\lfloor\log_2(16n/7)\rfloor=\lfloor\log_2n+4-\log_27\rfloor$ for $n\ge14$ (Corollary 2, p. 235), which exceeds $\lfloor\log_2n\rfloor+1$ for $n$ in the range $[7\cdot2^j,2^{j+3})$ of each $j\ge1$ . Their paper (J. Combinatorial Theory 9 (1970), 225--238, refereed) is in the publisher's open archive: library home Reid and Parker 1970, result pages Theorem 4 and Corollary 2. The claim page Reid and Parker 1970 records the theorem, its postings and the acceptance evidence; the later refutations each have their own claim page (listed under Claims below), and the frontmatter standing is derived from them. The paper states the conjecture in the equivalent form "for each positive integer $k$ , there exists a $T_n$ with $n=2^{k-1}-1$ which contains no $TT_k$ " (p. 226) and shows it "false for all $k\ge5$ " (p. 235). The standing rests on Theorem 4; its proof was followed as a reduction to the paper's Theorems 2 and 3 and is not independently checked. The origin's own bounds, $\lfloor\log_2n\rfloor+1\le f(n)\le2\lfloor\log_2n\rfloor+1$ , are cited from the origin itself.

ErMo64: Erdős, P. and Moser, L., On the representation of directed graphs as unions of orderings. Magyar Tud. Akad. Mat. Kutató Int. Közl. 9 (1964), 125--132; Theorem 1 and the conjecture, printed p. 127; Stearns's argument, p. 126. Library home: Erdős and Moser 1964.
RePa70: Reid, K. B. and Parker, E. T., Disproof of a conjecture of Erdős and Moser on tournaments. J. Combinatorial Theory 9 (1970), no. 3, 225--238, doi:10.1016/S0021-9800(70)80061-8; Theorem 4 and Corollaries 1--2, printed p. 235; the values of $f(n)$ for $n\le23$ and the note on $n\le27$ , p. 236; Theorem 5, pp. 236--238 (locators to the publisher's open-archive version). Library home: Reid and Parker 1970
Sa94: Sánchez-Flores, A., On tournaments and their largest transitive subtournaments. Graphs Combin. 10 (1994), no. 2--4, 367--376, doi:10.1007/BF02986687; [Sa98b] Sánchez-Flores, A., On tournaments free of large transitive subtournaments. Graphs Combin. 14 (1998), no. 2, 181--200, doi:10.1007/s003730050025 (Crossref records). Neither held; their theorems, $R(7)\le55$ in [Sa94] and $R(7)\le54$ in [Sa98b], are recorded from their zbMATH reviews (Zbl 0811.05029, Zbl 0918.05058) on their claim pages, and attested in part by [IRW21], [NMH22] and [Na14].
St59: Stearns, R., The voting problem. Amer. Math. Monthly 66 (1959), 761--763. Not held; its argument is reproduced in [ErMo64], p. 126, and its theorem attested in [ErRa67], pp. 624--625.
ErRa67: Erdős, P. and Rado, R., Partition relations and transitivity domains of binary relations. J. London Math. Soc. 42 (1967), 624--633; pp. 624--625 and Theorem 4 (i), p. 632. Library home: Erdős and Rado 1967.
IRW21: Ihringer, F., Rajendraprasad, D. and Weinert, T., New bounds on the Ramsey number $r(I_m,L_n)$ . Discrete Math. 344 (2021), 112268; arXiv:1707.09556v3; the survey paragraph on p. 2. Library home: Ihringer and Weinert 2017.
NMH22: Neiman, D., Mackey, J. and Heule, M. J. H., Tighter bounds on directed Ramsey number $R(7)$ . Graphs Combin. 38 (2022), no. 5, Paper No. 156, doi:10.1007/s00373-022-02560-5; arXiv:2011.00683. The locators are to the NSF author manuscript (17 pp.): p. 2 and Section 5. Library home: Neiman and Heule 2022.
MM25: McCarthy, D. and Monico, C., A Mathon-type construction for digraphs and improved lower bounds for Ramsey numbers. Electron. J. Combin. 32 (2025), no. 2, P2.42, doi:10.37236/13294; arXiv:2408.04067. Theorem 1 (p. 2) and Table 1 (p. 7) of the journal's open-access file. Library home: McCarthy and Monico 2025
Na14: Nagy, Z. L., Density version of the Ramsey problem and the directed Ramsey problem. arXiv:1401.6823 (v1 27 January 2014; v3 21 January 2016, 17 pp.); Theorem 4.2 and the introduction's survey, cited from the author-hosted revised copy (14 pp., linked from the site's thread; fetched 2026-09-18, 285,814 bytes). The copy thanks a referee. Not held in the library.
NeLa94: Neumann-Lara, V., A short proof of a theorem of Reid and Parker on tournaments. Graphs Combin. 10 (1994), 363--366, doi:10.1007/BF02986686 (Crossref record). Not held; by its zbMATH review (Zbl 0811.05028) it gives a shorter proof of Reid and Parker's Corollary 1, recorded on its claim page.

Problem 1216

Status

Proof claims

Discussion