Problem Statement
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)$.
Categories:
Graph Theory
Progress
Schütte asked Erdős this in the early 1960s.It is easy to check that $f(1)=3$ and $f(2)=7$. Erdős [Er63c] proved\[2^{n+1}-1 \leq f(n) \ll n^22^n.\]Szekeres and Szekeres [SzSz65] proved that $f(3)=19$ and\[n2^n \ll f(n).\]
Source: erdosproblems.com/902 | Last verified: January 19, 2026