---

Claim. P. Erdős, On a problem in graph theory, Math. Gaz. 47 (1963), no. 361, 220--223, DOI 10.2307/3613396 (issued October 1963, the nominal first day of which is this page's date). Writing $f(k)$ for the least order of a tournament in which every $k$ vertices have a common dominator (Schütte's property $S_k$), the paper proves on p. 221 (inequality (1) and inequalities (2) and (2.1)) that $f(1)=3$ and $f(2)=7$, that $f(k)\ge2^{k+1}-1$ for every $k\ge1$ (1), and that $\limsup_kf(k)2^{-k}k^{-2}\le\log2$ (2), that is, for every $\varepsilon>0$ there is $K_\varepsilon$ with $f(k)\le2^kk^2\log(2+\varepsilon)$ for $k>K_\varepsilon$ (2.1). The upper bound comes from a first-moment count over all orientations of the complete graph, which also proves that $f(k)$ exists for every $k$ (p. 223). The paper guesses that $f(k)=2^{k+1}-1$ may hold for all $k$; the Szekeres--Szekeres bound refutes that guess for every $k\ge3$. The claim value is proved: the result proves values and bounds of $f$ without determining its order of magnitude.

Covers. The values $f(1)=3$ and $f(2)=7$, the existence of $f(k)$, the lower bound $2^{k+1}-1$ and the upper bound $2^kk^2\log(2+\varepsilon)$ for large $k$; not the order of magnitude, which the problem asks to estimate.

Depends on. Nothing in this wiki.

Acceptance. Refereed: published in The Mathematical Gazette, cited with its venue above. The site credits Erdős with $2^{n+1}-1\le f(n)\ll n^22^n$ in commentary on a problem it labels OPEN, which is not acceptance, so reviewed is not listed.

Formalization. The repository jaredwilder/erdos902 (README author Jared Wilder), linked above at its commit of 18 September 2026, contains files that present themselves as formalizations of three results of this paper: Erdos902ClosedForm.lean, the lower bound $f(n)\ge2^{n+1}-1$; Erdos902Control.lean, the values $f(1)=3$ and $f(2)=7$ checked by kernel evaluation; and Erdos902Existence.lean, the first-moment existence bound, in the weaker form $f(n)\le n+3n^2\cdot2^n$. This project has not built or audited the repository, so no formalized evidence is listed.