Erdős Problem #21
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: combinatorics, intersecting family.
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
Imagine a family of sets, each containing exactly \(n\) elements, such that every two sets intersect. How few sets can the family have while making it impossible to find a hitting set with fewer than \(n\) elements? A hitting set meets every member of the family.
If \(f(n)\) is the smallest possible size of such a family, Erdős Problem #21 asked whether \(f(n)\) grows at most linearly with \(n\), that is, \(f(n)=O(n)\). Jeff Kahn proved this in 1994.
A small example
For \(n=2\), take the three sets
They intersect pairwise. No single element meets all three sets, whereas two elements suffice. The minimum hitting-set size is therefore 2. This shows \(f(2)\le3\).
One or two distinct intersecting two-element sets always have a common element, so they admit a one-element hitting set. Consequently \(f(2)=3\). This is an exact finite calculation and does not prove the general linear upper bound.
What is known
The original Erdős–Lovász work established nontrivial lower and upper estimates. Kahn, On a problem of Erdős and Lovász. II. \(n(r)=O(r)\), Journal of the American Mathematical Society 7 (1994), 125–143, proved a linear upper bound on the number of edges in an intersecting uniform hypergraph whose minimum hitting-set size equals its uniformity. This is exactly the type of family in #21 and resolves the question.
The constant in the best linear asymptotic bound and small specific values of \(f(n)\) are separate extremal questions; one must not confuse them with whether a linear bound exists.
GCL's current state
Source audit #1290 checks the equivalence between the problem's quantification over smaller hitting sets and the hypergraph transversal number. It reconstructs the three-edge example above. The admitted frozen GCL formal-provider snapshot does not include an #21 statement; reported external Lean status is not evidence of GCL compilation or certification.
What remains
The historical existence of a linear upper bound is established. Further worthwhile work could formalize Kahn's hypotheses and proof, improve quantitative extremal estimates or certify finite cases. None should be advertised as an unresolved original Erdős #21 problem.
Sources and claim boundaries
- Erdős Problems #21: solved status, original definition and small examples.
- Kahn (1994), primary bibliographic record: published theorem, not independently reconstructed here.
- GCL source return #1290: finite hypergraph proof and precise source limits.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1290 — 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.