Erdoes #112 - working report - Erdős Problem a Day

Erdős problem 112 — live audit, literature correction, exact small cases, and a cyclic-Cayley census

Date: 2026-08-12 UTC (initial run 2026-07-26)

Companion verifier: runs/erdos112_wave5i_verify.py

2026-08-12 unrestricted order-21 update

The live main and proof-claim pages were fetched again through Bright Data before this update. They remained OPEN, with zero comments, zero proof claims, no current worker, and no interested collaborator. The dedicated claim page said no proof claims had been submitted. [LIVE PAGE]

No order-21 witness was found, and no unrestricted UNSAT result is claimed; the certified interval remains

21\le k(3,4)\le25.

Three exact finite advances sharpen the next attack. (a) For any root vertex of a hypothetical 21-vertex witness, its out-, in-, and non-neighbour counts, after reversing every arc if needed, must be exactly one of

(8,8,4), (8,7,5), (8,6,6), (7,7,6), (8,5,7), (7,6,7).

Indeed, the first two entries are at most 8 because each directed neighbourhood is (I_3,L_3)-free and k(3,3)=9; the last is at most 7 because it is (I_2,L_4)-free and every eight-vertex tournament contains a transitive four-set. The three entries sum to 20. (a)

(d) A definition-level exhaustive ternary backtracker proves that none of the eight cyclic order-20 witnesses in the initial report can be extended by one vertex while retaining all 190 old pair states. It visits between 1,907 and 10,598 nodes per witness and independently checks every anchored independent triple and transitive four-tournament. This does not exclude an order-21 witness whose induced order-20 subgraphs differ from those eight.

(d) A checked order-21 near witness has 137 arcs, 73 nonedges, no transitive four-tournament, and exactly one independent triple: (5,13,16). Its exact 210-state SHA-256 is 6be5046ca0dc52cbea5a6127f6f7ea8879831b7b5e325fe03b9a7955838cfa6f. Those three vertices are precisely the vertices of nondegree 8; every other vertex respects the local degree bounds.

The complete six-profile CNFs each have 6,573 variables and 158,010 clauses. All six exploratory solver runs were interrupted unresolved and are recorded as UNKNOWN, never UNSAT. Bounded Hamming-ball diagnostics around two one-defect states and the cyclic witnesses produced no repair, but had no proof logs and are not used as theorems.

The quick rigorous checker and continuation sources are frozen in the verification bundle. Run python3 verification/112/n21-attack/verify_n21_artifacts.py from the site repository. (d)

Outcome

The mandatory stop condition did not fire. The live page was OPEN, with zero claimed proofs and nobody marked as currently working or interested in collaborating.

The main substantive finding is that the live page is missing a directly relevant peer-reviewed 2021 paper. In the notation of the page, that paper proves

k(4,3)=15,\qquad k(5,3)=23,\qquad k(n,3)\le n^2-n+3,

and, using named results of Alon and Kim,

k(n,3)=\Theta\!\left(\frac{n^2}{\log n}\right).

I give a self-contained proof of the elementary upper bound, and the standalone checker exhaustively verifies the explicit lower-bound constructions for \(k(3,3)\), \(k(4,3)\), and \(k(5,3)\).

I also independently found and checked the cyclic construction

D_{20}=\operatorname{Cay}\!\left(\mathbb Z_{20}, \{2,4,5,7,11,14\}\right),

which has neither an independent triple nor a transitive tournament of order four. Thus

21\le k(3,4)\le25.

An exhaustive enumeration of every cyclic Cayley oriented graph on orders 20 through 24 finds eight valid connection sets at order 20 and none at orders 21--24. Hence order 20 is maximal within that restricted class. This is not a determination of \(k(3,4)\).

Claim labels

The mathematical assertions below use the requested labels:

(a) elementary-rigorous: proved here using finite counting and induction;
(b) rigorous-modulo-named-theorem: depends on an explicitly named

published theorem;

(c) plausible/structural-unverified: not used as a theorem;
(d) computational-only: established by the deterministic finite checker.

Live-page observations are marked [LIVE PAGE] and bibliographic facts checked in primary sources are marked [PRIMARY SOURCE].

0. Mandatory live-page audit

Access method

Direct datacenter access was not trusted. I used the Bright Data remote browser with Cloudflare solving and saved a screenshot while extracting the rendered text, links, and the separate LaTeX-source page. The page was accessed on 2026-07-26 UTC.

Live URLs:

<https://www.erdosproblems.com/112>
<https://www.erdosproblems.com/latex/112>

Verbatim current statement

Let \(k=k(n,m)\) be minimal such that any directed graph on \(k\) vertices must contain either an independent set of size \(n\) or a transitive tournament of size \(m\). Determine \(k(n,m)\).

Current status, discussions, proofs, and people markers

[LIVE PAGE]

Status: OPEN.
Comments: 0 comments on this problem.
Claimed proofs: 0 claimed proofs for this problem.
Interested in collaborating: None.
Currently working on this problem: None.
Likes this problem: None.
This problem looks difficult: None.
This problem looks tractable: None.
The results on this problem could be formalisable: None.
I am working on formalising the results on this problem: None.
Formalised statement: No.

The page also warns that OPEN records the site owner's present belief and that unlisted literature may partially or completely solve the statement.

Results currently listed on the page

[LIVE PAGE] In the page's notation:

Erdős and Rado are credited with

\[ k(n,m)\ll_m n^{m-1} \quad\text{and specifically}\quad k(n,m)\le \frac{2^{m-1}(n-1)^m+n-2}{2n-3}. \]

Larson and Mitchell are credited with improved dependence on \(m\), in

particular \(k(n,3)\le n^2\).

Zach Hunter is credited with

\[ R(n,m)\le k(n,m)\le R(n,m,m), \]

and hence \(k(n,m)\le3^{n+2m}\).

The page explicitly distinguishes a directed-path variant in the UCSD

graphs collection. For that different problem it credits Zach Hunter and Raphael Steiner with the exact value \((n-1)(m-1)\). Nothing from that path argument is used for the transitive-tournament problem here.

The page lists exactly these two references:

P. Erdős and R. Rado, *Partition relations and transitivity domains of

binary relations*, J. London Math. Soc. 42 (1967), 624--633.

J. A. Larson and W. J. Mitchell, On a problem of Erdős and Rado,

Ann. Comb. 1 (1997), 245--252.

1. Definition and notation

The modern literature denotes by \(I_a\) the independent oriented graph on \(a\) vertices and by \(L_b\) the transitive tournament on \(b\) vertices. It writes \(r(I_a,L_b)\) for the least order forcing one of them. Thus the parameters map as

\boxed{k(n,m)=r(I_n,L_m)}.

[PRIMARY SOURCE] Ihringer--Rajendraprasad--Weinert explicitly defines an “oriented graph” to be loopless and to have at most one directed edge between each unordered pair. This resolves the word “directed” on the live page in the sense used by the cited line of work. All results and code below use this oriented-graph convention.

For a vertex \(v\), write \(N^+(v)\), \(N^-(v)\), and \(I(v)\) for its out-neighbours, in-neighbours, and non-neighbours. An \((I_a,L_b)\)-free graph contains neither forbidden induced subgraph.

2. Primary-literature audit

Erdős--Rado (1967)

[PRIMARY SOURCE] The article and metadata were checked at the author's archive and the publisher:

<https://users.renyi.hu/~p_erdos/1967-19.pdf>
<https://doi.org/10.1112/jlms/s1-42.1.624>

The PDF is the stated J. London Math. Soc. paper, pages 624--633. It studies the relevant finite transitivity/partition parameters and contains the displayed explicit bound recorded on the live page.

Larson--Mitchell (1997)

[PRIMARY SOURCE] Publisher record:

<https://doi.org/10.1007/BF02558478>

The DOI resolves to Annals of Combinatorics 1, 245--252. Its abstract defines exactly the minimum order at which a digraph has an independent \(n\)-set or a transitive \(m\)-tournament, and identifies the equivalent infinite partition problem. This verifies that it is the cited problem, not the directed-path variant.

Ihringer--Rajendraprasad--Weinert (2021)

[PRIMARY SOURCE]

Ferdinand Ihringer, Deepak Rajendraprasad, and Thilo V. Weinert,

New bounds on the Ramsey number \(r(I_m,L_n)\), Discrete Mathematics 344 (2021), article 112268, <https://doi.org/10.1016/j.disc.2020.112268>.

Open final preprint: arXiv:1707.09556v3,

<https://arxiv.org/abs/1707.09556>.

The title, authors, arXiv identifier, journal, and DOI all resolve. The abstract and Theorems 1.1--1.3 state:

r(I_4,L_3)=15,\quad r(I_5,L_3)=23,\quad r(I_m,L_3)=\Theta(m^2/\log m),

and, for each fixed \(t\ge3\),

r(I_m,L_t)\le C_t\frac{m^{t-1}}{(\log m)^{t-2}}.

Accordingly, in the live page's notation:

(a) \(k(4,3)=15\) and \(k(5,3)=23\); an elementary proof plus checked

witnesses is reproduced below.

(b) \(k(n,3)=\Theta(n^2/\log n)\), modulo Alon's locally sparse

independence bound and Kim's theorem \(R(n,3)=\Theta(n^2/\log n)\).

(b) For every fixed \(m\ge3\),

\(k(n,m)\le C_m n^{m-1}/(\log n)^{m-2}\), modulo the theorems used in that paper.

These are material improvements over the results currently displayed on the live page.

Version audit: the delicate \(k(3,4)\) computation

(c) arXiv v1 (2017) included a proposition \(r(I_3,L_4)\le24\) based on a Gurobi integer program. The article gave no instance, source code, solution certificate, or independently checkable infeasibility certificate. Its footnote reported 2385.35 seconds with Gurobi 7.0.2 on an Intel i5-2400.

That proposition was removed from final arXiv v3 and from the peer-reviewed paper; the final paper instead asks for \(r(I_3,L_4)\). I therefore do not treat the v1 computation as a theorem or use \(k(3,4)\le24\). The elementary certified bound used below is \(k(3,4)\le25\).

Search coverage and honest miss statement

I searched the exact titles, DOI, arXiv identifier, the notations \(r(I_m,L_n)\), \(r(I_3,L_4)\), and the defining phrase. I also checked Crossref metadata and citing-work records in OpenAlex and Semantic Scholar. I found no later primary paper giving a newer exact determination of this same finite function. This is a search result, not a proof of absence.

3. Elementary recurrence

(a) For all \(a,b\ge2\),

k(a,b)\le 2k(a,b-1)+k(a-1,b)-1. \tag{1}

Indeed, if \(D\) is \((I_a,L_b)\)-free and \(v\in V(D)\), then each of \(N^+(v)\) and \(N^-(v)\) is \((I_a,L_{b-1})\)-free: a transitive \((b-1)\)-tournament there extends with \(v\) to a transitive \(b\)-tournament. Also \(I(v)\) is \((I_{a-1},L_b)\)-free, since an independent \((a-1)\)-set there extends with \(v\). Therefore

|V(D)| \le1+2(k(a,b-1)-1)+(k(a-1,b)-1),

which is (1).

We will also use two immediate facts.

(a) \(k(a,2)=a\): either there is an arc, which is \(L_2\), or an

edgeless \(a\)-set.

(a) \(k(2,3)=4\). A directed 3-cycle is a three-vertex lower witness.

Conversely, a graph with no independent pair is a tournament; in every four-vertex tournament a vertex of out-degree at least two and two of its out-neighbours form a transitive triple.

Equation (1) now gives

k(3,3)\le 2k(3,2)+k(2,3)-1=2\cdot3+4-1=9.

The checked eight-vertex construction below gives equality.

4. A self-contained proof that \(k(n,3)\le n^2-n+3\)

Local structure

(a) In an \((I_q,L_3)\)-free oriented graph, both \(N^+(v)\) and \(N^-(v)\) are independent, so

d^+(v),d^-(v)\le q-1. \tag{2}

Otherwise two adjacent vertices in one of these neighbourhoods, together with \(v\), form a transitive triangle.

Put

s_q=q^2-q+2,\qquad t_q=s_q+1=q^2-q+3.

We prove simultaneously, for every \(q\ge3\):

\(k(q,3)\le t_q\);
every \((I_q,L_3)\)-free graph on \(s_q\) vertices has at least

\(s_q(2q-3)/2\) arcs.

Base \(q=3\)

We proved \(k(3,3)\le9=t_3\). In any free graph on \(s_3=8\) vertices, \(I(v)\) has at most three vertices because \(k(2,3)=4\). Thus every vertex has total degree at least four. By (2) it has total degree at most four. Hence such a graph is 4-regular and has 16 arcs, which is stronger than the required lower bound \(8\cdot3/2=12\).

Exceptional 14-vertex edge lemma

(a) Every \((I_4,L_3)\)-free oriented graph on 14 vertices has at least 38 arcs.

Suppose instead that it has at most 37. Since \(k(3,3)=9\), every non-neighbourhood has size at most eight, so every total degree is at least five. By (2), every total degree is at most six. The degree sum is at most 74, so globally at most four vertices have degree six.

Choose a degree-five vertex \(v\), reversing all arcs if necessary, with \(d^-(v)=2\) and \(d^+(v)=3\). Then \(|I(v)|=8\).

Every vertex of \(I(v)\) has a neighbour in the independent 3-set

\(N^+(v)\), or it extends that set to an independent 4-set. Thus there are at least eight arcs between \(N^+(v)\) and \(I(v)\).

There are at least five arcs between \(N^-(v)\) and \(I(v)\). If there

were at most four, at least four vertices of \(I(v)\) would have no neighbour in \(N^-(v)\). Since \(k(2,3)=4\) and the graph has no transitive triangle, two of those four would be independent; together with the independent 2-set \(N^-(v)\), they give an independent 4-set.

The induced graph on \(I(v)\) is an eight-vertex

\((I_3,L_3)\)-free graph, so the base-case argument gives exactly 16 internal arcs.

The sum of the total degrees of the eight vertices in \(I(v)\) is therefore at least

8+5+2\cdot16=45.

As each of those degrees is five or six, at least five of them have degree six. This contradicts the global bound of four.

Private-neighbour estimate

(a) Suppose an \((I_{q+1},L_3)\)-free graph has \(|N^-(v)|=q\). If \(S=I(v)\), then

|E(N^-(v),S)|\ge2(|S|-q). \tag{3}

Every \(x\in S\) has a neighbour in the independent set \(N^-(v)\), or it creates an independent \((q+1)\)-set. Call \(x\) private if it has exactly one such neighbour. A fixed \(u\in N^-(v)\) has at most two private neighbours: among three of them, either all three pairs are adjacent, in which case they and \(u\) form a four-vertex tournament and hence contain a transitive triangle, or two are nonadjacent, in which case those two together with \(N^-(v)\setminus\{u\}\) form an independent \((q+1)\)-set.

There are consequently at most \(2q\) private vertices. Counting one edge from each private vertex and at least two from every other vertex gives (3). The same proof applies to \(N^+(v)\).

Induction

Assume both assertions at \(q\).

First take an \((I_{q+1},L_3)\)-free graph on

s_{q+1}=q^2+q+2

vertices. Since \(I(v)\) is \((I_q,L_3)\)-free and \(k(q,3)\le t_q\), it has at most \(s_q\) vertices. Therefore every total degree is at least

s_{q+1}-1-s_q=2q-1=2(q+1)-3.

The handshaking lemma proves the required edge lower bound at \(q+1\).

It remains to rule out a free graph on

t_{q+1}=q^2+q+3.

The local bounds \(|N^+(v)|,|N^-(v)|\le q\) and \(|I(v)|\le s_q\) sum exactly to \(t_{q+1}-1\). Hence equality holds everywhere:

d^+(v)=d^-(v)=q,\qquad |I(v)|=s_q. \tag{4}

Fix \(v\), put \(S=I(v)\), and let \(\ell\) be the number of arcs between \(S\) and \(N^+(v)\cup N^-(v)\). Applying (3) in both directions gives

\ell\ge4(s_q-q). \tag{5}

By (4), every vertex in \(S\) has total degree \(2q\), so

\ell+2e(S)=2q\,s_q. \tag{6}

There are three cases.

If \(q=3\), the base case gives \(e(S)=16\). Equation (6) gives

\(\ell=16\), whereas (5) gives \(\ell\ge20\).

If \(q=4\), the exceptional lemma gives \(e(S)\ge38\). Equation (6)

gives \(\ell\le36\), whereas (5) gives \(\ell\ge40\).

If \(q\ge5\), the inductive edge bound and (6) give

\(\ell\le3s_q\). But

\[ 4(s_q-q)-3s_q=q^2-5q+2>0 \]

for \(q\ge5\), contradicting (5).

This completes the simultaneous induction.

Therefore:

\boxed{k(n,3)\le n^2-n+3\quad(n\ge3).}

5. Exact checked values in the \(m=3\) row

The lower witnesses are:

\begin{array}{c|c|l} n & |V| & \text{arcs}\\ \hline 2&3&x\to x+1\pmod 3,\\ 3&8&x\to x+1,\ x\to x-2\pmod 8,\\ 4&14&x\to x+1,\ x\to x-2,\ \text{and } \begin{cases}x\to x+4,&x\text{ even},\\ x\to x-6,&x\text{ odd}, \end{cases}\pmod {14},\\ 5&22&x\to x+1,\ x\to x+4,\ x\to x-5,\ x\to x+10\pmod {22}. \end{array}

(d) The checker independently enumerates every relevant vertex subset. It verifies looplessness, no antiparallel pair, no forbidden independent set, and no transitive triangle. It also finds an independent set one smaller, so the reported independence numbers are exact.

Combining those checked lower witnesses with the elementary upper proof:

\boxed{ \begin{array}{c|cccc} n&2&3&4&5\\ \hline k(n,3)&4&9&15&23 \end{array}}

The upper halves of these equalities are (a); the finite witness checks are (d) under the requested taxonomy.

6. A verified \(k(3,4)\) lower bound and complete cyclic-Cayley census

Certified elementary upper cutoff

(a) The standard tournament induction gives \(k(2,4)\le8\). Applying (1) gives

k(3,4)\le2k(3,3)+k(2,4)-1 \le2\cdot9+8-1=25. \tag{7}

Thus no \((I_3,L_4)\)-free graph can have order at least 25.

Explicit order-20 witness

Let

C=\{2,4,5,7,11,14\}\subset\mathbb Z_{20}

and put an arc \(x\to x+d\) for every \(x\in\mathbb Z_{20}\) and \(d\in C\). The set \(C\) is disjoint from \(-C\), so this is an oriented graph with 120 arcs.

(d) Exhaustive checking gives

\alpha(D_{20})=2,\qquad \max\{|T|:T\text{ is a transitive tournament}\}=3.

Consequently:

\boxed{21\le k(3,4)\le25.}

The lower half is (d) and the upper half is (a).

Why the cyclic census is exhaustive

A cyclic Cayley oriented graph on \(\mathbb Z_N\) is determined by a connection set \(C\subset\mathbb Z_N\setminus\{0\}\) with \(C\cap(-C)=\varnothing\). For each inverse pair \(\{d,-d\}\), there are exactly three choices: absent, \(d\), or \(-d\). If \(N\) is even, the self-inverse difference \(N/2\) must be absent. Hence there are exactly

3^{\lfloor(N-1)/2\rfloor}

such labelled connection sets.

Translation invariance means that any forbidden independent triple or transitive 4-tournament can be translated to contain 0. The checker precomputes all anchored forbidden patterns, exhausts every ternary connection-set choice, and then cross-checks each survivor with a separate generic induced-subgraph routine.

(d) The complete counts are:

\(N\)	all connection sets	no independent triple	also no \(L_4\)
20	19,683	4,992	8
21	59,049	14,848	0
22	59,049	16,736	0
23	177,147	51,328	0
24	177,147	29,440	0

The eight order-20 connection sets are

\begin{aligned} &(1,2,4,14,15,17), &(1,2,6,12,13,15),\\ &(2,3,5,6,11,12), &(2,4,5,7,11,14),\\ &(3,5,6,16,18,19), &(5,7,8,14,18,19),\\ &(6,9,13,15,16,18), &(8,9,14,15,17,18). \end{aligned}

Together with (7), the census proves that 20 is the maximum possible order for a cyclic Cayley \((I_3,L_4)\)-free oriented graph. It says nothing about non-Cayley graphs of orders 21--24.

7. Reproduction

Run:

python3 runs/erdos112_wave5i_verify.py

The script is standalone and uses only the Python standard library. It has two independent checking paths:

generic subset enumeration with an induced-tournament acyclicity test;
a bit-mask census derived independently from inverse-difference pairs,

followed by generic cross-checking of every survivor.

Reference run on this VM:

WITNESS k(2,3)>3: order=3 arcs=3 alpha=1 max_transitive=2 sha256=5b3c695d6698d0f4fc4f40c22119f3a2aa401d94383daacdecde6f83e0c06946
WITNESS k(3,3)>8: order=8 arcs=16 alpha=2 max_transitive=2 sha256=eecd65ed9c4a9c80b3c5f9351950bbf94ac658572b0e6dc7e2c2c1558e3d11ab
WITNESS k(4,3)>14: order=14 arcs=42 alpha=3 max_transitive=2 sha256=84b1cc4787c37314091ae958405235458b4ab48166d027be6935c9b26f4a191d
WITNESS k(5,3)>22: order=22 arcs=88 alpha=4 max_transitive=2 sha256=879774bd79238d83d52ea85f4dad6e3328f6f9265bfd626ebe09bdab68eac60a
WITNESS k(3,4)>20: order=20 arcs=120 alpha=2 max_transitive=3 sha256=40dd0d86a214e996e4c5805d3fca79406ab44540d0425aa6e46f67102fdf4531
CENSUS Z_20: total=19683 alpha<3=4992 also_TT4_free=8
CENSUS Z_21: total=59049 alpha<3=14848 also_TT4_free=0
CENSUS Z_22: total=59049 alpha<3=16736 also_TT4_free=0
CENSUS Z_23: total=177147 alpha<3=51328 also_TT4_free=0
CENSUS Z_24: total=177147 alpha<3=29440 also_TT4_free=0
ARITHMETIC: all induction, recurrence, and CNF counts verified
ALL CHECKS PASSED in 3.798 seconds

8. Exact remaining wall

The first unresolved cell

The present certified interval is

21\le k(3,4)\le25.

The cyclic census proves that any order-21--24 witness must break cyclic Cayley symmetry. To determine the exact value, one needs either:

an explicit general oriented graph of one of those orders, which this

checker could immediately validate; or

a proof/certificate that no such graph exists at the relevant order.

Concrete SAT size and bounded diagnostic

Using one Boolean variable for each possible directed arc, the raw order-\(N\) CNF has:

\(N(N-1)\) variables;
\(\binom N2\) antiparallel-edge clauses;
\(\binom N3\) clauses forbidding independent triples;
\(24\binom N4\) clauses forbidding each linearly ordered transitive

4-tournament.

Thus \(N=21\) has 420 variables and 145,180 clauses, while \(N=24\) has 552 variables and 257,324 clauses. These arithmetic counts are recomputed by the standalone checker.

(d) A raw, unsymmetrised Kissat 4.0.4 probe at \(N=21\) was capped at 120 CPU-seconds and returned no answer before the cap. This is only a runtime diagnostic; it proves neither satisfiability nor unsatisfiability and is not used above.

The withdrawn v1 computation gives a useful cost anchor: a heavily structured \(N=24\) Gurobi instance reportedly used 2385.35 seconds, about 0.66 core-hours on its stated older CPU, but supplied no certificate. A responsible modern campaign should budget roughly 1--10 core-hours per hard UNSAT order for symmetry breaking, solver runs, proof logging, and independent DRAT/LRAT checking. That heavier campaign was not run here.

Uniform problem

The literature correction settles the order of growth only for the transitive-triangle row. For fixed transitive order at least four, the precise missing ingredient is a matching lower construction or a sharper upper theorem bridging the gap between ordinary off-diagonal Ramsey lower bounds and the \(O(n^{m-1}/(\log n)^{m-2})\) oriented upper bound. No such uniform lemma was found in the primary-source search.

PARTIAL: For k(3,4), every order-21 witness is reduced to six canonical root profiles, all eight cyclic order-20 witnesses are exactly nonextendable unchanged, and a checked order-21 near witness has exactly one independent triple and no transitive four-tournament; the certified interval remains 21<=k(3,4)<=25.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger