Erdős Problem #703
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: combinatorics.
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
Define T(n,r) as the maximum number of subsets in a family of {1,...,n} such that distinct members never meet in EXACTLY r points. Erdős asked about its size, especially whether for every ε>0 there is δ>0 such that T(n,r)<(2−δ)^n whenever εn<r<(1/2−ε)n. The maintained catalogue says this positive answer was PROVED by Frankl–Rödl [FrRo87]. Distinguish r fixed from r proportional to n.
A small example
For n=4,r=1, the family {∅,{1},{2},{3},{4}} has five sets; any two distinct singleton sets are disjoint and the empty set meets none, so no pair meets in one point. Another valid construction for any r is the full family of all subsets with size strictly less than r, since no intersection can have size r.
What is known
The maintained source attributes to Frankl–Füredi [FrFu84b] exact extremal descriptions for FIXED r and sufficiently large n, subject to separate parity conditions on n+r. It attributes the crucial proportional-r exponential saving to Frankl and Rödl, 'Forbidden intersections', Transactions AMS 300 (1987), 259–286, independently corroborated in Rödl's author publication listing. It does not say that T(n,r) has one exact closed formula for arbitrary n and growing r. A source claim that the result implies exponential growth in Euclidean distance-graph chromatic number is a related consequence, not the same theorem. No GCL protected admitted FC #703 file.
GCL's current state
The authenticated original RESULT/1 source return retains its original BOUNDED_TASK_DESIGNED disposition and mathematical qualifications. This source-grounded explanation is editorially reviewed through the exact-hash EC-BULK-005-R8 protected transaction, effective on protected merge. It is not a fresh proof of the attributed mathematical theorem or an internally replayed Lean certificate.
Critical source-scope distinction: Frankl–Rödl proportional intersection excludes exactly r, fixed-r Frankl–Füredi cases separate.
What remains
Audit Frankl–Rödl 1987 Theorem and explicit allowed ε range, identify whether δ depends only on ε and the sufficiently-large-n threshold, then independently validate one finite forbidden-intersection construction with exact pair checks. Keep the fixed-r Frankl–Füredi theorem separate.
Sources and claim boundaries
Maintained Erdős #703, https://www.erdosproblems.com/703 ; https://www.math.emory.edu/~rodl/publications.html ; primary Frankl–Rödl [FrRo87] full proof not checked. Authenticated source-return evidence. Historical full proofs not independently replayed. Historical full mathematical proof replay remains an open research obligation.
Editorial provenance: protected R8 source-critical review. Original issue-level source and research-proof holds remain. Status: REVIEWED explanatory article; full historical theorem proofs, unresolved conjectures and external Lean proofs are not newly certified.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1974 — 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.