Erdős Problem #83
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
A family of sets is 2-intersecting if every two distinct members share at least two elements. Erdős #83 asks how large such a family can be when each set has size \(2n\) and the ground set has size \(4n\).
The precise proposed bound is
All members of \(\mathcal F\) must have exactly \(2n\) elements; using sets of any size, or requiring only a nonempty intersection, is a different extremal question.
A small example
For \(n=1\), the ground set is \([4]\) and each member has two elements. Distinct two-element sets intersect in at most one element, so a 2-intersecting family has at most one member. The formula gives \((\binom42-\binom21^2)/2=(6-4)/2=1\).
For \(n=2\), divide \([8]\) into two blocks of four, and include precisely those four-element sets containing at least three elements of the first block. There are \(\binom43\binom41+\binom44=17\) such sets, and every pair intersects in at least two elements. The conjectured upper bound equals \((\binom84-\binom42^2)/2=(70-36)/2=17\).
What is known
PROVED. Rudolf Ahlswede and Levon Khachatrian solved the general complete intersection problem in The Complete Intersection Theorem for Systems of Finite Sets, European Journal of Combinatorics 18 (1997), 125–136. Their theorem identifies maximum-size \(t\) intersecting, \(k\) uniform families on an \(m\) element ground set, with a parameter controlling the optimal initial segment.
The historical Erdős case specializes to \(m=4n\), \(k=2n\), \(t=2\). The canonical source states that the extremal family is formed by sets containing at least \(n+1\) elements of one chosen \(2n\) element block; that construction is precisely the one counted above. The primary publisher bibliographic record and its connection to the complete intersection theorem have been checked. The original 1997 proof and detailed boundary-parameter substitution are not independently replayed here.
GCL's current state
The original source assignment is #1352. The pinned catalogue reports PROVED and third-party Lean availability, but the admitted protected Formal Conjectures snapshot has no #83 statement file. GCL makes no claim of independent Lean verification. The \(n=1,2\) constructions and counts are verified elementary consequences.
An authenticated RESULT/1 source report is posted on the original issue. It is unadjudicated source evidence, not independent proof certification or editorial admission.
What remains
A bounded proof task is to establish the exact family-size identity using the complement involution on middle-layer sets: among the \(\binom{4n}{2n}\) sets, those having exactly \(n\) elements of the first block number \(\binom{2n}{n}^2\); the remaining sets split into two equal classes by complement. Acceptance: exact half-count and 2-intersection of the strict-majority class, with a computational cross-check for \(n=1,2\). The deep universal upper bound requires the 1997 theorem and must not be inferred from this example.
Sources and claim boundaries
- Ahlswede and Khachatrian, European J. Combin. 18 (1997), 125–136, complete-intersection primary publication.
- Erdős #83; original source issue #1352.
No new intersection theorem, kernel-checked formal proof or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1352 — 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.