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

Date: 2026-07-26 UTC

Companion verifier: runs/erdos112_wave5i_verify.py

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

and, using named results of Alon and Kim,

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

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

four. Thus

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:

1. 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}. \]

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

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

3. 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}\).

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

[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:

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

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\),

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

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

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

Otherwise two adjacent vertices in one of these neighbourhoods, together

with \(v\), form a transitive triangle.

Put

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

1. \(k(q,3)\le t_q\);

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

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

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

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

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

It remains to rule out a free graph on

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:

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

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

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:

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

The lower witnesses are:

(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:

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

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

Explicit order-20 witness

Let

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

Consequently:

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

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

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:

1. generic subset enumeration with an induced-tournament acyclicity test;

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

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: Live page safely cleared; verified k(2,3)=4, k(3,3)=9, k(4,3)=15, k(5,3)=23, proved k(n,3)<=n^2-n+3, and certified 21<=k(3,4)<=25 with cyclic Cayley maximum order 20; the general problem and exact k(3,4) remain open.