Estimate f(n): fewest vertices in a tournament where every n vertices have a common dominator (Erdős #902)
Statement
A tournament is a complete directed graph: between every pair of distinct vertices there is exactly one directed edge, and $u$ dominates $v$ if the edge points from $u$ to $v$. A tournament has the Schütte property $S_n$ if for every set $S$ of $n$ vertices there is at least one further vertex $w\notin S$ that dominates every vertex of $S$ (that is, $w\to v$ for all $v\in S$). Let $f(n)$ be the least number of vertices of a tournament that has property $S_n$. Estimate $f(n)$; in particular determine the growth rate of $f(n)$ as $n\to\infty$.
Acceptance. FULLY RESOLVES: determine the asymptotic order of $f(n)$ — prove matching upper and lower bounds (up to constants, or an asymptotic formula) that close the current gap between $n2^n$ and $n^2 2^n$ stated in the background — delivered as a complete proof (Lean/Coq formalisation preferred, otherwise a full written proof). ADVANCES, any of: (a) improve the constant or logarithmic factor in the best known bounds stated in the background, with proof; (b) determine a new exact value $f(n)$ beyond $f(3)=19$ (e.g. $f(4)$) by exhibiting a tournament on $N$ vertices with property $S_n$ AND a certificate (e.g. an exhaustive/SAT proof) that no tournament on $N-1$ vertices has property $S_n$; (c) give an explicit construction beating the probabilistic upper bound for infinitely many $n$. Property $S_n$ of a given tournament is machine-checkable (test that every $n$-subset has a dominator). Deliver the proof, or the tournament as an orientation matrix + verification code + the lower-bound/exhaustiveness certificate.
Background
Schütte posed this to Erdős in the early 1960s and it became one of the first showcase applications of the probabilistic method. Erdős [Er63c] proved by a random argument that property $S_n$ is achievable and gave the bounds $$2^{n+1}-1\leq f(n)\ll n^2 2^n.$$ Szekeres and Szekeres [SzSz65] sharpened the lower bound to $n2^n\ll f(n)$ and determined $f(3)=19$; the trivial small values are $f(1)=3$ and $f(2)=7$. The exact value $f(4)$ is unknown, and the asymptotic order of $f(n)$ (whether the truth is nearer $n2^n$ or $n^2 2^n$) remains open. Explicit constructions are also known: Paley (quadratic-residue) tournaments on a prime $p\equiv 3\pmod 4$ satisfy $S_n$ once $p$ is large enough relative to $n$, giving deterministic witnesses complementing the probabilistic bound. Listed as open on erdosproblems.com/902 (fetched 2026-07-13, status 'open', tagged 'graph theory'); the associated counts are catalogued as OEIS A362137. Attacker's tool: explicit or derandomised constructions (e.g. Paley tournaments) to lower the upper constant, plus SAT/exhaustive search for exact small values such as $f(4)$ together with machine-checkable lower-bound certificates.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #902 (T. F. Bloom) | website |
| REF-02 | OEIS A362137 — Schütte tournament domination numbers f(n) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.