Erdős problem #902 — wave 7s

Access date: 2026-07-28 (UTC).

Outcome

The problem remains open. The concrete verified output is:

The lower bound is in the literature and is [b] rigorous modulo the Reid--Brown nonexistence theorem for nontrivial triply regular tournaments. The upper bound has the following completely explicit certificate:

The dependency-free checker exhausts all \(\binom{67}{4}=766{,}480\) four-sets and finds at least one common dominator for every one. This is [d] computational-only. It also independently proves by exhaustive enumeration that this tournament has domination number exactly \(5\).

This construction and the \(48\) lower bound are known, so this is not a new solution. The useful contribution of this run is a self-contained closed-form certificate, an independently reproducible checker, an exact witness distribution, and a precise account of the remaining asymptotic and computational walls.

Claim labels

• [a] elementary-rigorous: a complete proof is given here.
• [b] rigorous-modulo-named-theorem: the deduction is complete assuming

the precisely identified published theorem.

• [c] plausible/structural-unverified: a proposed route or diagnosis, not

a theorem.

• [d] computational-only: a finite exhaustive computation or an exact

diagnostic from the supplied code, not a uniform theorem.

Step 0: mandatory live-page audit

I fetched the Cloudflare-protected live page and its discussion thread through the Bright Data browser path before doing any mathematics.

The live page showed:

• status: OPEN;
• 0 claimed proofs;
• “Interested in collaborating: None”;
• “Currently working on this problem: None”;
• “Likes this problem: None” and all other interest/reaction markers: None;
• source keys in the problem header: [Er63c] and [Er82e];
• “Formalised statement? No” and related OEIS sequence A362137;
• three comments, all dated 14 December 2025.

Thus none of the mandatory stop conditions applied.

Verbatim live 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)\).

Source: Erdős Problems #902.

Results listed on the live page

The page says that Schütte asked Erdős the problem in the early 1960s and lists:

and

These are [b] as statements of the cited results.

All three live comments

The discussion thread contains no proof claim and no work marker.

1. Alfaiz, 15:11 on 14 December 2025, says that Graham--Spencer

\([{\rm GrSp71}]\) gives a constructive proof of a weaker bound, with an edit thanking Stijn for the clarification.

1. StijnC, 15:24, emphasizes that the paper does not solve the problem: it

gives only a weaker constructive bound, while the asymptotic upper and lower bounds remain a factor \(n\) apart.

1. Alfaiz, 15:28, agrees and explains that the original wording “It seems”

was meant to signal that tentative interpretation.

Interpretation as domination number

For a tournament \(T\), call \(D\subseteq V(T)\) a dominating set when every vertex \(x\notin D\) is beaten by some \(d\in D\). Write \(\gamma(T)\) for the least size of such a set.

For any \(D\), the following are equivalent:

1. no vertex outside \(D\) beats every member of \(D\);
2. for every \(x\notin D\), some \(d\in D\) beats \(x\);
3. \(D\) is a dominating set.

Indeed, in a tournament, “\(x\) does not beat every \(d\in D\)” means that some \(d\in D\) beats \(x\). Therefore

For the reverse implication when a dominating set has fewer than \(n\) vertices, extend it to an \(n\)-set; a superset of a dominating set is still dominating. This equivalence is [a].

Thus \(f(4)\) is the smallest order of a tournament with domination number at least \(5\). Some domination papers shift the index and ask for the smallest tournament with \(\gamma(T)=5\); this is the same first unknown small case.

Primary-source literature audit

I searched using the exact statement, “Schütte property \(S_k\),” “\(k\)-paradoxical tournament,” “tournament domination number 5,” and the names in the live references. I checked the mathematical text of the following primary sources, not just search-result titles.

1. P. Erdős, On a problem in graph theory,

Math. Gaz. 47 (1963), 220--223, DOI 10.2307/3613396. The paper defines \(S_k\), proves \(f(k)\geq2^{k+1}-1\), and gives the probabilistic \(f(k)\leq(\log 2+o(1))k^2 2^k\) upper bound. [b]

1. E. Szekeres and G. Szekeres,

On a problem of Schütte and Erdős, Math. Gaz. 49 (1965), 290--293. The bibliographic record and journal extract were checked. Its exact lower bound \[ f(k)\geq(k+2)2^{k-1}-1\qquad(k>2) \] is also reproduced explicitly in the Graham--Spencer, Simon, and Jeffries primary texts below. [b]

1. R. L. Graham and J. H. Spencer,

A constructive solution to a tournament problem, Canad. Math. Bull. 14 (1971), 45--48, DOI 10.4153/CMB-1971-007-1. The paper constructs quadratic-residue tournaments, proves its general (weaker) constructive bound, and explicitly records that the \(67\)-vertex example has \(S_4\). [b]

1. K. B. Reid, A. A. McRae, S. M. Hedetniemi, and S. T. Hedetniemi,

Domination and irredundance in tournaments, Australas. J. Combin. 29 (2004), 157--172. Proposition 14 proves the elementary \(47\) lower bound for domination number \(5\), and Corollary 7 excludes order \(47\), yielding \(f(4)\geq48\). The final exclusion invokes the nonexistence of nontrivial triply regular tournaments from K. B. Reid and E. Brown, Doubly regular tournaments are equivalent to skew Hadamard matrices, JCTA 12 (1972), 332--338, DOI 10.1016/0097-3165(72)90098-290098-2). I verified the Reid--Brown bibliographic record but did not recover its full text; the exact dependency used here is the theorem as quoted and applied in the 2004 paper. [b]

1. H. U. Simon, arXiv:2205.08357,

Minimum Tournaments with the Strong \(S_k\)-Property and Implications for Teaching (2022). Section 3 reproduces the exact Szekeres lower bound and Erdős upper bound; Section 4 states Graham--Spencer's quadratic-residue theorem. It studies a stronger variant and does not improve the original asymptotic gap. [b]

1. J. Jeffries, arXiv:2604.08790,

Schütte's property for sets of tournaments and an application to dice games (submitted 9 April 2026). The introduction explicitly says that the Erdős--Szekeres bounds remain the best known bounds for \(f(k)\). It also reports the small Paley orders \(3,7,19,67,\ldots\), while the paper's new results concern sets of several tournaments. [b]

The 2004 paper attributes the “smallest rotational tournament” computation to a private communication from D. Fisher. I do not use that private computation as a theorem. The supplied checker independently handles the smaller claim that \(67\) is the first finite-field Paley order with \(S_4\). [d]

I found no primary source claiming a proof, counterexample, or asymptotic improvement for the original one-tournament problem. This is a report of the searches above, not a claim that an exhaustive citation search is possible.

A from-scratch lower bound for the first open case

This section reproduces the elementary part of the \(f(4)\) lower bound. For a vertex \(a\), let

Suppose \(\gamma(T)\geq5\).

Choose \(b\in I(a)\), then \(c\in I(a)\cap I(b)\), and put

These choices and \(S\neq\varnothing\) are forced: if one of the successive intersections were empty, respectively \(\{a\}\), \(\{a,b\}\), or \(\{a,b,c\}\) would dominate the tournament by following the first edge in the cascade \(a,b,c\) that points to a given outside vertex.

If some \(x\) beat every member of \(S\), then \(\{a,b,c,x\}\) would dominate \(T\), using the same cascade. Hence no vertex beats all of \(S\). By the equivalence above, \(S\) is itself a dominating set, so

This holds for every \(c\in I(a)\cap I(b)\). Consequently every vertex of the induced tournament \(T[I(a)\cap I(b)]\) has indegree at least \(5\). A tournament of minimum indegree \(r\) has at least \(2r+1\) vertices, because its average indegree is \((m-1)/2\). Therefore

Applying the same averaging argument inside \(T[I(a)]\), for every \(b\in I(a)\), gives

Finally every vertex of \(T\) has indegree at least \(23\), so

This proves \(f(4)\geq47\) entirely elementarily. [a]

If equality \(47\) held, equality would hold at every averaging step: \(T\), every \(T[I(a)]\), and every \(T[I(a)\cap I(b)]\) would be regular of orders \(47,23,11\), with indegrees \(23,11,5\). This is the triply regular \((5,11,23)\)-tournament excluded by the theorem invoked in Reid et al., Corollary 7. Thus

The last step, unlike the \(47\) bound, is [b], not [a].

Explicit \(67\)-vertex construction

Let

These are the \(33\) nonzero quadratic residues modulo \(67\). On \(\mathbb Z/67\mathbb Z\), orient

Because \(67\equiv3\pmod4\), \(-1\) is a quadratic nonresidue. Thus exactly one of \(x-y\) and \(y-x\) is in \(Q\), so this is a tournament. [a]

For a four-set \(A=\{a,b,c,d\}\), its common dominators are

The standalone checker obtains the following exact distribution. [d]

The counts sum to \(766{,}480=\binom{67}{4}\), and the weighted checksum is

In particular the minimum witness count is \(1\), proving computationally that this tournament has \(S_4\), hence

The upper bound is [d].

An independent domination-set pass finds no dominating set of sizes \(1,2,3,4\), finds exactly \(1{,}056{,}858\) dominating five-sets, and finds the lexicographically first one to be

Thus this particular tournament has \(\gamma=5\). [d]

The construction is vertex-deletion critical for \(S_4\): each of its 67 one-vertex deletions has exactly 330 undominated four-sets. This follows in the checker by assigning each of the 22,110 uniquely witnessed four-sets to its unique witness; every vertex receives 330. [d]

Exact Paley prime-power table through \(67\)

The checker also enumerates every prime power \(q\equiv3\pmod4\), \(5\leq q\leq67\). It implements \(\mathbb F_{27}\) directly as \(\mathbb F_3[t]/(t^3+2t+1)\), so the non-prime order is not omitted. “Bad” means a four-set with no common dominator. [d]

Therefore \(P_{67}\) is exactly the first nonvacuous finite-field Paley tournament of admissible order \(q\geq5\) with \(S_4\). This is only a result inside the Paley family, not a lower bound for arbitrary tournaments. [d]

Reproduction and independent checks

The standalone verifier is:

runs/erdos902_wave7s_reverify.py

Run:

python runs/erdos902_wave7s_reverify.py

It uses only the Python standard library. Its main construction is literally:

p = 67
Q = {x*x % p for x in range(1, p)}
edge = [[u != v and (u-v) % p in Q for v in range(p)] for u in range(p)]

The script then:

1. builds the orientation once from the square table and independently

checks every edge with Euler's criterion;

1. checks the tournament axioms;
2. exhausts all four-sets using common-in-neighbour bit masks;
3. recomputes domination with unions of closed out-neighbourhoods, a

different formulation;

1. exhausts all \(9{,}657{,}648=\binom{67}{5}\) five-sets;
2. verifies the deletion-critical counts in one independent pass;
3. generates every admissible Paley prime-power order through \(67\),

including a from-scratch implementation of \(\mathbb F_{27}\);

1. checks the stable upper-triangle orientation hash

b705bc7dab8b1f6fa78cc8871b2bec828378d17c4f046941f0ee5d193ab48d04.

The recorded run was:

PASS: closed-form P_67 is a tournament with property S_4
P_67 witness distribution: {1: 22110, 2: 110550, 3: 219626, 4: 267531, 5: 112761, 6: 31691, 7: 2211}
P_67 domination number: 5
first dominating 5-set: (0, 1, 2, 3, 40)
number of dominating 5-sets: 1056858
each one-vertex deletion has 330 undominated 4-sets
Paley prime-power table (q: total4, bad4, max_witnesses):
  7: (35, 35, 0)
  11: (330, 275, 1)
  19: (3876, 1653, 2)
  23: (8855, 2530, 2)
  27: (17550, 3159, 3)
  31: (31465, 3875, 3)
  43: (123410, 3010, 4)
  47: (178365, 2162, 5)
  59: (455126, 3422, 6)
  67: (766480, 0, 7)
orientation sha256: b705bc7dab8b1f6fa78cc8871b2bec828378d17c4f046941f0ee5d193ab48d04
elapsed=3.37 sec maxrss=15472 KB

Capped repair search below \(67\)

The auxiliary heuristic is:

runs/erdos902_local_search.cpp

Build and run:

g++ -O3 -std=c++20 runs/erdos902_local_search.cpp -o /tmp/erdos902_ls
/tmp/erdos902_ls 10 902

It begins with \(P_{67}\) minus one vertex, maintains the exact coverage count of all \(\binom{66}{4}=720{,}720\) four-sets under edge flips, and uses a repair heuristic on uncovered sets. It performs a full recount at the end to validate its incremental state.

The capped run returned:

initial_bad=330 total_4sets=720720
NO_CONSTRUCTION best=330 final=550 iterations=2580

This exact run record is [d], but “no construction found” is not a nonexistence result and gives no lower bound. Extrapolating from it would be [c]. In particular, it does not show that order \(66\) is impossible.

Clean reduction and the exact asymptotic wall

Let \(B_v=N^+(v)\), the set of vertices beaten by \(v\). Then \(T\) has \(S_n\) exactly when the \(N\) blocks

cover every \(n\)-subset of \(V(T)\). These blocks obey the skew constraints

Thus #902 is precisely a covering-design problem with a global antisymmetry constraint. [a]

The strongest verified general bounds remain

This is [b], and leaves a factor of order \(n\).

The ordinary random-tournament/union-bound method cannot reach the lower scale. For a random tournament on \(N\) vertices, the expected number of undominated \(n\)-sets is

If \(N=Cn2^n\), its logarithm is

which tends to \(+\infty\) on the \(n^2\) scale. At \(N=Cn^2 2^n\), the negative term becomes \(-Cn^2\), and the threshold constant from this calculation is \(C=\log2\). This explains exactly why the elementary probabilistic proof stops at \(n^2 2^n\). [a]

A resolution therefore needs at least one genuinely new ingredient:

• an antisymmetric half-block construction on \(O(n2^n)\) vertices (or an

intermediate scale), whose uncovered-set events have correlations very unlike a random tournament; or

• an overlap/degree-distribution theorem for skew block covers strong

enough to improve the Szekeres \(\Omega(n2^n)\) lower bound, potentially to \(\Omega(n^2 2^n)\).

No such lemma was found in the primary literature checked here. The assertion that one of these two endpoints is the true order is [c]; the true scale could be intermediate.

What exact computation would be needed next

Even the next concrete question, whether an \(S_4\) tournament exists on 48 vertices, is nontrivial. A direct labeled enumeration has

orientations. At the unrealistically optimistic rate of \(10^9\) orientations per core-second, this is about \(10^{327}\) core-hours, or about \(10^{323}\) years; brute force is not an option. [a]

A straightforward Tseitin SAT encoding has:

• \(1{,}128\) edge-orientation variables;
• \(\binom{48}{4}=194{,}580\) four-set constraints;
• \(194{,}580\cdot44=8{,}561{,}520\) witness auxiliaries;
• \(8{,}562{,}648\) total variables and \(34{,}440{,}660\) clauses.

These counts are exact [a]. Raw literals already require hundreds of megabytes, and a realistic CDCL run plus proof logging would need several gigabytes. A serious symmetry-broken/lazy-constraint campaign should be budgeted initially at roughly \(10^2\)--\(10^3\) core-hours (about \(\$5\)--\(\$50\) at \(\$0.05\) per core-hour), but there is no defensible guarantee that this would finish or yield a checkable UNSAT certificate; that cost forecast is [c]. I did not run it because it exceeds the few-minute budget.

The precise finite target is either:

1. a checkable SAT construction of order \(48\) through \(66\), improving

the explicit upper bound; or

1. a solver-independent/DRAT-checkable UNSAT certificate at order \(48\),

improving the concrete lower bound to \(49\).

Neither target has been reached here.

PARTIAL: Verified \(48\leq f(4)\leq67\); \(P_{67}\) is an explicit \(S_4\) tournament with a standalone exhaustive checker, while the asymptotic factor-\(n\) gap remains open.