Problem 902

Let $f(n)$ be minimal such that there is a tournament (a complete directed graph) on $f(n)$ vertices such that every set of $n$ vertices is dominated by at least one other vertex. Estimate $f(n)$ .

Source: erdosproblems.com/902

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Open. No source determining $f(n)$ , its order of magnitude, or any value beyond $n=3$ was found in the search whose scope the Current assessment records. The best known bounds are

(n+2)2^{n-1}-1\le f(n)\le2^nn^2\log(2+\varepsilon)\quad(n>K_\varepsilon),

the upper bound from Erdős's 1963 paper [Er63c], the lower bound from Szekeres and Szekeres [SzSz65] (not held; stated in J. W. Moon's zbMATH review, Zbl 0134.43502, and attested in the refereed paper of Graham and Spencer [GrSp71], in Erdős's 1982 collection [Er82e] and in the 2026 preprint of Jeffries [Je26]), and the 2026 preprint says the two "remain the best known bounds for $f(k)$ " (a preprint's attestation, not a refereed one). The exact values are $f(1)=3$ , $f(2)=7$ ([Er63c]) and $f(3)=19$ ([SzSz65], second-hand), and $48\le f(4)\le67$ (the lower bound is Corollary 7 of [RMHH04], the upper bound [GrSp71]'s $T_{67}$ ); Theorem 5 of [RMHH04] with $QRT_{19}$ also proves $f(3)=19$ in a refereed paper. This is a bounded negative finding, not a certificate of openness. The claim pages are Erdős 1963, Szekeres and Szekeres 1965 and Reid, McRae, Hedetniemi and Hedetniemi 2004, each an accepted partial claim on refereed evidence; none settles the order of magnitude, so the standing stays open.

Er63c: Erdős, P., On a problem in graph theory. Math. Gaz. 47 (1963), 220--223, doi:10.2307/3613396 (Crossref; issued October 1963). The definition, $f(1)=3$ , $f(2)=7$ , the guess $f(k)=2^{k+1}-1$ and inequalities (1), (2) and (2.1), p. 221; the seven-town example, p. 220. Library home: Erdos 1963 (a Rényi archive scan whose text layer misreads the inequality signs); paged at Erdos 1963, Inequality (1) (p. 221) and Erdos 1963, Inequalities (2) and (2.1) (p. 221).
SzSz65: Szekeres, E. and Szekeres, G., On a problem of Schütte and Erdős. Math. Gaz. 49 (1965), no. 369, 290--293, doi:10.2307/3612854 (Crossref; issued October 1965). Not held: the Cambridge Core article page, offers an abstract and no PDF link. Its bound and its value $f(3)=19$ are stated, without a range of $k$ , in J. W. Moon's zbMATH review (Zbl 0134.43502); the bound, the value and the conjecture are also attested in [GrSp71], [Er82e] and [Je26].
Er82e: Erdős, Paul, Some of my favourite problems which recently have been solved. Proceedings of the International Mathematical Conference (Singapore, 1981), North-Holland Math. Stud. 74 (1982), 59--79; §2, printed p. 70. Library home: Erdős 1982.
GrSp71: Graham, R. L. and Spencer, J. H., A constructive solution to a tournament problem. Canad. Math. Bull. 14 (1971), no. 1, 45--48, doi:10.4153/CMB-1971-007-1 (Crossref). Not a site key; cited in the thread. The quoted bounds (1) and (2), the construction and the Theorem, p. 45; the concluding remarks, p. 47. Library home: Graham and Spencer 1971; paged at Graham and Spencer 1971, Theorem (p. 45).
Je26: Jeffries, Joel, Schütte's property for sets of tournaments and an application to dice games. arXiv:2604.08790v1 (9 April 2026; arXiv lists no later version and no journal reference). A preprint; not a site key. Theorem 1.1, p. 1; the survey sentences, p. 2. Library home: Jeffries 2026; paged at Jeffries 2026, Theorem 1.1 (p. 1).
RMHH04: Reid, K. B., McRae, A. A., Hedetniemi, S. M. and Hedetniemi, S. T., Domination and irredundance in tournaments. Australas. J. Combin. 29 (2004), 157--172 (https://ajc.maths.uq.edu.au/pdf/29/ajc_v29_p157.pdf; volume dated March 2004). Not a site key; linked from OEIS A362137. The equivalence of $S_k$ with domination number above $k$ , p. 160; display (2), the Szekeres--Szekeres bound printed without a range, p. 162; Theorem 5, p. 165; $QRT_{19}$ and Fisher's computations, p. 166; Proposition 14 and Corollary 7, pp. 170--171. Claim page: Reid, McRae, Hedetniemi and Hedetniemi.
Er62: Erdős, P., Applications of probability to combinatorial problems. Proc. Colloq. Combinatorial Methods in Probability Theory (Aarhus, 1962), 90--92, as [GrSp71]'s reference [2] for Schütte's question of 1962. Not held.

Problem 902

Status

Proof claims

Discussion