Skip to content

Erdős Problem #207

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: combinatorics, hypergraphs.

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

A Steiner triple system on \(n\) vertices is a collection of three-element blocks such that every unordered pair of distinct vertices lies in exactly one block. These systems can exist only when \(n\equiv1\) or \(3\pmod6\).

Erdős asked whether, for every fixed integer \(g\ge2\) and all sufficiently large admissible \(n\), there is such a system with high girth: every collection of \(j\) distinct blocks, for \(2\le j\le g\), must contain at least \(j+3\) distinct vertices. This forbids configurations in which a small number of triples are unusually concentrated.

A small example

Two distinct blocks cannot share two vertices, because that would repeat a pair, so their union contains at least five vertices, as the requirement \(j=2\) demands. A Pasch configuration has four triples on six vertices and violates the required inequality when \(j=4\) (it would demand at least seven vertices). The small-configuration condition is stricter than the basic Steiner pair-uniqueness condition.

For \(n=7\), the Fano plane is a Steiner triple system: it has seven triples and each pair lies in exactly one. Its existence illustrates the divisibility requirements but does not demonstrate arbitrarily high girth at fixed order.

What is known

PROVED. Matthew Kwan, Ashwin Sah, Mehtaab Sawhney and Michael Simkin, High-Girth Steiner Triple Systems, prove Erdős's 1973 conjecture: for every fixed girth threshold \(g\), every sufficiently large \(n\equiv1,3\pmod6\) supports a Steiner triple system avoiding all forbidden small dense configurations.

Their argument uses randomized constructions and absorbing methods. The statement is an asymptotic existence theorem; it does not say that a random Steiner triple system automatically satisfies the high-girth condition with high probability without further construction.

The maintained Erdős #207 classifies the question PROVED and cites the authors' paper. The exact \(j+3\) vertex count is crucial: changing it to \(j+2\) produces a weaker property, while demanding the property for all \(j\) without fixing \(g\) is a substantially stronger claim.

GCL's current state

Pinned and live status: PROVED. Original authenticated issue #1476. The primary preprint theorem and admissible congruence classes were checked. Its full probabilistic proof and any third-party proof-assistant translation have not been independently replayed in GCL.

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 constructs the Fano-plane blocks and checks exact pair multiplicities. Enumerate unions of \(j\) distinct blocks for \(2\le j\le4\), record violations of \(|\cup E_i|\ge j+3\), and distinguish a small finite design from the general theorem for large \(n\). Acceptance: verify every pair occurs once, demonstrate a Pasch-type obstruction when present, and never conflate fixed girth with unrestricted growing girth.

Sources and claim boundaries

No new Steiner-system construction, independent full theorem proof or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1476 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • 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