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.

2. 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.

3. 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]

2. 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]

3. 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]

4. 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]

5. 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]

6. 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]

| number of common dominators | number of four-sets |

|---:|---:|

| 1 | 22,110 |

| 2 | 110,550 |

| 3 | 219,626 |

| 4 | 267,531 |

| 5 | 112,761 |

| 6 | 31,691 |

| 7 | 2,211 |

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]

| \(q\) | total four-sets | bad four-sets | maximum witnesses |

|---:|---:|---:|---:|

| 7 | 35 | 35 | 0 |

| 11 | 330 | 275 | 1 |

| 19 | 3,876 | 1,653 | 2 |

| 23 | 8,855 | 2,530 | 2 |

| 27 | 17,550 | 3,159 | 3 |

| 31 | 31,465 | 3,875 | 3 |

| 43 | 123,410 | 3,010 | 4 |

| 47 | 178,365 | 2,162 | 5 |

| 59 | 455,126 | 3,422 | 6 |

| 67 | 766,480 | 0 | 7 |

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;

2. checks the tournament axioms;

3. exhausts all four-sets using common-in-neighbour bit masks;

4. recomputes domination with unions of closed out-neighbourhoods, a

different formulation;

5. exhausts all \(9{,}657{,}648=\binom{67}{5}\) five-sets;

6. verifies the deletion-critical counts in one independent pass;

7. generates every admissible Paley prime-power order through \(67\),

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

8. 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

2. 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.