Skip to content

Erdős Problem #112

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, ramsey theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

In a directed graph, an independent set has no arcs between any two of its vertices. A transitive tournament is an orientation of a complete graph in which the vertices can be ordered so that all arcs point forward. Let \(k(n,m)\) be the least number of vertices that guarantees either an independent set of size \(n\) or a transitive tournament of size \(m\).

Erdős and Rado asked for sharp estimates for \(k(n,m)\). One must retain all directed arcs of the configuration being tested: a directed path is not a transitive tournament, and deleting a reverse arc from a bidirected pair is not a valid induced-tournament witness.

A small example

A transitive tournament on four vertices can be drawn by ordering vertices \(1,2,3,4\) and directing each arc from the smaller to the larger. Every pair is adjacent; no independent pair occurs. A directed four-vertex path has only three arcs and is not such a tournament, though its reachability relation admits the same linear order.

For ordinary simple undirected Ramsey theory, colouring present edges red and absent edges blue gives an elementary analogy. Directed orientations introduce more than two pair states, explaining why importing an undirected Ramsey number without qualification is insufficient.

What is known

The problem remains OPEN as an estimation question. Erdős and Rado [ErRa67] obtained a polynomial estimate in \(n\) for fixed \(m\), notably \(k(n,m)\ll_m n^{m-1}\). Larson and Mitchell [LaMi97] improved the dependence on \(m\), including \(k(n,3)\le n^2\).

The maintained Erdős #112 records the more recent comparison

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

which implies an exponential bound of the form \(k(n,m)\le3^{n+2m}\). Here the three-colour Ramsey number is an upper comparison; it is not a claimed exact formula. The source also records an alternative directed-path formulation with the exact answer \((n-1)(m-1)\). The path problem is not the same as the transitive-tournament problem, and transferring that exact result would be a false solution.

GCL's current state

The pinned 2025 catalogue and maintained issue classify #112 as OPEN. The original authenticated source assignment is #1381. Primary full-text proofs by Erdős–Rado and Larson–Mitchell were not independently reconstructed in this review; the explicit formulae above are attributed to the maintained research catalogue.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded task is to implement an exhaustive checker on directed graphs with at most four vertices. Count independent subsets only when neither directed arc is present, and count transitive tournaments only when every pair has exactly one arc with an acyclic orientation. Acceptance requires a hand-checkable directed path that does not accidentally pass the tournament test. Stop at these finite semantics; no new Ramsey asymptotics follow.

Sources and claim boundaries

  • Erdős #112, original Erdős–Rado and Larson–Mitchell references and path-versus-tournament distinction.
  • GCL source issue #1381; pinned catalogue revision 536408716724a2402bdfa7c1d764bf83d64a8c89.

No new exact Ramsey number, independent proof of the historic upper bound, or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1381 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction