Problem 112

Let $k=k(n,m)$ be minimal such that any directed graph on $k$ vertices must contain either an independent set of size $n$ or a transitive tournament of size $m$ . Determine $k(n,m)$ .

Source: erdosproblems.com/112

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open. No formula for $k(n,m)$ , and no determination beyond the values listed in the Current assessment ( $k(n,1)=k(1,m)=1$ and $k(n,2)=n$ ; the tournament column $k(2,m)$ for $m\le6$ ; $k(3,3)=9$ , $k(4,3)=15$ , $k(5,3)=23$ ), was found in the search whose scope the Current assessment records. A pending partial claim, Muhamadiev's $k(3,4)=21$ , was posted on 22 September 2026. The bounds verified here from the sources read are Erdős and Rado's $k(n,m)\le(2^{m-1}(n-1)^m+n-2)/(2n-3)$ (1967), Larson and Mitchell's $k(n,3)\le n^2$ and their polynomial bound of degree $m-1$ in $n$ with leading coefficient $2^{m-2}/(m-1)!$ (1997), and, for the oriented threshold, $k(n,3)\le n^2-n+3$ , $k(n,3)=\Theta(n^2/\log n)$ and $k(n,m)\le2^{17m}n^{m-1}/(\log_2n)^{m-2}$ (Ihringer, Rajendraprasad and Weinert, Discrete Math. 2021). This is a bounded negative finding, not a certificate of openness.

ErRa67: Erdős, P. and Rado, R., Partition relations and transitivity domains of binary relations. J. London Math. Soc. 42 (1967), 624--633, doi:10.1112/jlms/s1-42.1.624. Theorem 1 (p. 624) and Theorem 2 with relation (3) and Remark (i) (p. 625). Library home: Erdős and Rado 1967.
ErRa56: Erdős, P. and Rado, R., A partition calculus in set theory. Bull. Amer. Math. Soc. 62 (1956), 427--489; Theorem 25, which the 1967 paper quotes as its Theorem 1 and which Ihringer, Rajendraprasad and Weinert restate as $r(\omega m,n)=\omega\,r(I_m,L_n)$ . Library home: Erdős and Rado 1956 (filed for Problem 1172; its Theorem 25 was not read for this page).
LaMi97: Larson, Jean A. and Mitchell, William J., On a problem of Erdős and Rado. Ann. Comb. 1 (1997), 245--252, doi:10.1007/BF02558478. Proposition 3.1 and Lemmas 4.1--4.2 with the corollary $r(K_4^*,L_3)\le16$ (p. 248), Lemma 4.13 with the growth estimates (p. 251), Theorem 2.4 and the table of small values (p. 247). Library home: Larson and Mitchell 1997.
IRW21: Ihringer, F., Rajendraprasad, D. and Weinert, T., New bounds on the Ramsey number $r(I_m,L_n)$ . Discrete Math. 344 (2021), no. 3, 112268, doi:10.1016/j.disc.2020.112268; arXiv:1707.09556 (v3 8 April 2020, 20 pp., whose pagination the locators follow). Theorems 1.1--1.5 (pp. 3--4), Proposition 3.4 (p. 9), Theorem 5.6 (p. 15). Library home: Ihringer and Weinert 2017.
Be74: Bermond, J.-C., Some Ramsey numbers for directed graphs. Discrete Math. 9 (1974), 313--321, doi:10.1016/0012-365X(74)90077-6. Proposition 2.5 (p. 316), $R(TT_3,K_3^*)=9$ , with the definitions of p. 313 and Theorem 2.2 and Proposition 2.4 (pp. 314--315). Library home: Bermond 1974.
Ba74: Baumgartner, J. E., Improvement of a partition theorem of Erdős and Rado. J. Combin. Theory Ser. A 17 (1974), 134--137, doi:10.1016/0097-3165(74)90037-5. The note's one result, unnumbered (p. 135), $\omega_\alpha\cdot l_0(m,n)\to(m,\omega_\alpha\cdot n)^2$ for all $\alpha$ , $m$ and $n$ , with the sentences of pp. 134--135 it rests on. Library home: Baumgartner 1974.
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 (p. 127), the tournament column. Library home: Erdős and Moser 1964.
St59: Stearns, R., The voting problem. Amer. Math. Monthly 66 (1959), 761--763. Not held; its tournament-column bound is quoted from [IRW21], p. 2, and its argument is reproduced on p. 126 of [ErMo64].
RePa70: Reid, K. B. and Parker, E. T., Disproof of a conjecture of Erdős and Moser on tournaments. J. Combinatorial Theory 9 (1970), 225--238; Theorem 4 (p. 235) with the values of $f(n)$ and the note on a $TT_6$ -free $T_{27}$ (pp. 235--236), the tournament column beyond $m=4$ . Library home: Reid and Parker 1970.

Problem 112

Status

Proof claims

Discussion