Erdős Problem #664
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (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
Erdős Problem #664 asks whether a family of large sets that overlap pairwise in at most one element always admits a small-intersection transversal. More precisely, for a fixed constant \(c\) less than one, the blocks \(A_i\) have size greater than \(c\sqrt n\) and satisfy \(|A_i\cap A_j|\leq1\) for distinct blocks. Must there be a set \(B\) meeting each block at least once but at most \(C(c)\) times, with \(C(c)\) independent of the growing system?
The maintained catalogue reports this general question DISPROVED, attributing the negative construction to Noga Alon. The stronger special version requiring every pair of ground points to lie on a block remains open; the two questions must not be conflated.
A small example
In the seven-point Fano plane, label the points by residues modulo seven and make the seven lines the translates of \(D=\{0,1,3\}\). Each line has three points, two different lines meet in exactly one point, and any two distinct points determine exactly one line. The whole ground set \(B\) is a transversal with \(|B\cap A_i|=3\) for each line.
This small positive example is NOT Alon's asymptotic counterexample. It only demonstrates the incidence vocabulary.
What is known
For prime-power \(q\), a projective plane has \(n=q^2+q+1\) points and the same number of lines, with \(q+1\) points on each line and a one-point intersection between any two distinct lines. If one replaces each line by a subset of its points, intersections can only decrease; in particular they remain of size at most one.
The maintained #664 source says Alon used random subsets of projective-plane lines to obtain blocks of size at least \((2/5)\sqrt n\) for which every hitting set \(B\) must meet SOME block in at least a constant multiple of \(\log n\) points. That would defeat any uniform upper bound \(C(c)\) for fixed \(c<2/5\). The essential logarithmic transversal lower bound is not a formal consequence of ordinary projective-plane incidence: it depends on Alon's probabilistic construction.
Primary-source limitation: despite targeted searches, the original bibliographically identified Alon proof for this precise assertion was not directly located or inspected. The logarithmic result is therefore explicitly catalogue-attributed, not independently re-proved or certified here.
The older Erdős 1981 variant requires every pair of ground points to occur in exactly one block. Randomly deleting points from lines generally destroys that property. Hence the reported general-family counterexample does not resolve the more restrictive version.
GCL's current state
The original authenticated RESULT/1 source return has historical disposition PARTIAL. This status and the original research exceptions are preserved, not silently converted into a theorem verdict. The maintained Erdős source and source-specific mathematical definitions were reviewed, and this article is editorially reviewed as a source-exception-annotated explanation under EC-BULK-005-R10, effective only after the exact-hash protected admission merges.
Source interpretation and unresolved mathematical qualification: Random projective-plane lines support an Alon-attributed logarithmic hitting obstruction; the original Erdős pair-cover statement and primary proof need inspection.
The explanation is accepted for publication of established background, examples, and explicitly attributed current claims. It does not establish or formally certify the disputed original theorem, external model-assisted proof, historical interpretation, or any unreplayed Lean kernel file. Original source-fidelity and proof-review research holds remain.
What remains
Identify and inspect Alon's original preprint or paper, with exact theorem number, probability distribution, hypothesis \(|A_i|>c\sqrt n\) and proof that EVERY transversal has a logarithmically large intersection somewhere. If the original result differs in quantifiers, constants or block assumptions, amend the article rather than promote a mistaken citation.
The original Er81 and Er97f passages and the exact stronger pair-cover variant also require source checking. Protected merge, deployed math rendering and V2 editorial admission are separate tasks.
Sources and claim boundaries
-
Maintained #664 catalogue entry and revision history: Alon attribution, quantitative parameters and unresolved stronger variant.
-
Authenticated GCL #664 source return: elementary incidence audit and exact source blocker.
-
Original Alon proof and historical Er81/Er97f: not directly inspected.
Boundary: no internally reconstructed logarithmic transversal proof, no new mathematical result, no formal certification, no newly certified theorem proof or editorial admission.
Qualified editorial critical review: R10 source-exception dossier. The source-semantic exception is visible and its original research hold remains. Publication classification: REVIEWED EXPLANATORY ARTICLE WITH UNRESOLVED SOURCE/PROOF QUALIFICATIONS. Independent theorem proof or Lean certification: NOT CLAIMED.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1935 — 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.